C++中实现队列类链式存储与栈类链式存储的代码示例

// 队列类  #pragma once  #include "linklist.hpp"  template <typename T> class LinkQueue { public:   LinkQueue();   ~LinkQueue(); public:   int clear();   int append(T &t);   int retieve(T &t);   int header(T &t);   int length(); protected:   LinkList<T> *m_list; };  template <typename T> LinkQueue<T>::LinkQueue() {   m_list = new LinkList < T > ; }  template <typename T> LinkQueue<T>::~LinkQueue() {   clear();   delete m_list;   m_list = NULL; }  template <typename T> int LinkQueue<T>::clear() {   T t;   while (m_list->getLen() > 0) {     m_list->del(0, t);   }   return 0; }  template <typename T> int LinkQueue<T>::append(T &t) {   return m_list->insert(t, m_list->getLen()); }  template <typename T> int LinkQueue<T>::retieve(T &t) {   return m_list->del(m_list->getLen() - 1, t); }  template <typename T> int LinkQueue<T>::header(T &t) {   return m_list->get(0, t); }  template <typename T> int LinkQueue<T>::length() {   return m_list->getLen(); } 

// 队列类测试程序  #include <iostream> #include <cstdio> #include "linkqueue.hpp"  using namespace std;  struct Student {   char name[32];   int age; };  void play() {   Student s1, s2, s3;   s1.age = 21;   s2.age = 22;   s3.age = 23;    LinkQueue<Student> lq; // 创建队列   lq.append(s1); // 入队列   lq.append(s2);   lq.append(s3);    Student tmp;   lq.header(tmp);   cout << "header of queue: " << tmp.age << endl;   cout << "length of queue: " << lq.length() << endl;    while (lq.length() > 0) {     lq.retieve(tmp);     cout << tmp.age << " ";   }   cout << endl;    lq.clear();  }  int main() {   play();    return 0; } 

// 栈类  #pragma once  #include "linklist.hpp"  template <typename T> class LinkStack { public:   LinkStack();   ~LinkStack(); public:   int clear();   int push(T &t);   int pop(T &t);   int top(T &t);   int size(); protected:   LinkList<T> *m_list; };  template <typename T> LinkStack<T>::LinkStack() {   m_list = new LinkList < T > ; }  template <typename T> LinkStack<T>::~LinkStack() {   clear();   delete m_list;   m_list = NULL; }  template <typename T> int LinkStack<T>::clear() {   T t;   while (m_list->getLen() > 0) {     m_list->del(0, t);   }    return 0; }  template <typename T> int LinkStack<T>::push(T &t) {   return m_list->insert(t, 0); }  template <typename T> int LinkStack<T>::pop(T &t) {   return m_list->del(0, t); }  template <typename T> int LinkStack<T>::top(T &t) {   return m_list->get(0, t); }  template <typename T> int LinkStack<T>::size() {   return m_list->getLen(); } 

// 链式存储栈类的测试程序  #include <iostream> #include <cstdio> #include "linkstack.hpp"  using namespace std;  struct Student {   char name[32];   int age; };  void play() {   Student s1, s2, s3;   s1.age = 21;   s2.age = 22;   s3.age = 23;    LinkStack<Student> ls; // 创建栈    // 入栈   ls.push(s1);   ls.push(s2);   ls.push(s3);    // 获取栈顶元素   Student tmp;   ls.top(tmp);   cout << "top of stack: " << tmp.age << endl;   cout << "size of stack: " << ls.size() << endl;    // 出栈   while (ls.size() > 0) {     ls.pop(tmp);   }    ls.clear();  }  int main() {   play();    return 0; } 

// 链表类  #pragma once  #include <iostream> #include <cstdio> using namespace std;  template <typename T> struct Node {   T t;   Node<T> *next; };  template <typename T> class LinkList { public:   LinkList();   ~LinkList();  public:   int clear();   int insert(T &t, int pos);   int get(int pos, T &t);   int del(int pos, T &t);   int getLen();  protected:   Node<T> *header;   int length; };  template <typename T> LinkList<T>::LinkList() {   header = new Node < T > ;   header->next = NULL;   length = 0; }  template <typename T> LinkList<T>::~LinkList() {   Node<T> *tmp = NULL;    while (header) {     tmp = header->next;     delete header;     header = tmp;   } }  template <typename T> int LinkList<T>::clear() {   ~LinkList();   LinkList();   return 0; }  template <typename T> int LinkList<T>::insert(T &t, int pos) {   Node<T> *cur = NULL;    // 对pos的容错处理   if (pos >= length) {     pos = length;   }    cur = header;   for (int i = 0; i < pos; ++i) {     cur = cur->next;   }    // 把上层应用的t结点缓存到容器中   Node<T> *node = new Node < T > ;   node->next = NULL;   node->t = t; // 把t缓存到容器中    node->next = cur->next;   cur->next = node;    ++length;    return 0; }  template <typename T> int LinkList<T>::get(int pos, T &t) {   Node<T> *cur = NULL;    if (pos >= length) {     return -1;   }    cur = header;   for (int i = 0; i < pos; ++i) {     cur = cur->next;   }    t = cur->next->t; // 把pos位置的结点赋值给t    return 0; }  template <typename T> int LinkList<T>::del(int pos, T &t) {   Node<T> *cur = NULL;    if (pos >= length) {     return -1;   }    cur = header;   for (int i = 0; i < pos; ++i) {     cur = cur->next;   }   Node<T> *ret = NULL;   ret = cur->next;   t = ret->t; // 把缓存的结点给上层应用t    // 删除操作   cur->next = ret->next;   --length;   delete ret; // 注意释放内存，因为insert的时候new Node<T>    return 0; }  template <typename T> int LinkList<T>::getLen() {   return length; }