C++中實現隊列類鏈式存儲與棧類鏈式存儲的代碼示例

隊列類鏈式存儲

代碼：
linkqueue.hpp

// 隊列類  #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(); }

main.cpp

// 隊列類測試程序  #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; }

棧類鏈式存儲

linkstack.hpp

// 棧類  #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(); }

main.cpp

// 鏈式存儲棧類的測試程序  #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; }

linklist.h

// 鏈表類  #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; }