在C++數(shù)據(jù)結構學習中，順序表示的棧和隊列，必須預先分配空間，并且空間大小受限，使用起來限制比較多。而且，由于限定存取位置，順序表示的隨機存取的優(yōu)點就沒有了，所以，鏈式結構應該是***。

　　棧的定義和實現(xiàn)

#ifndef Stack_H  
#define Stack_H   
#include "List.h"  
 
template <class Type> class Stack : List//棧類定義  
{  
　public:  
　　void Push(Type value)  
　　{  
　　　Insert(value);  
　　}  
 
　Type Pop()  
　{  
　　Type p = *GetNext();  
　　RemoveAfter();  
　　return p;  
　}  
 
　Type GetTop()  
　{  
　　return *GetNext();  
　}  
 
　List ::MakeEmpty;  
　List ::IsEmpty;  
 
};  
 
#endif 

　　隊列的定義和實現(xiàn)

#ifndef Queue_H  
#define Queue_H  
#include "List.h"  
 
template <class Type> class Queue : List//隊列定義  
{  
　public:  
　　void EnQueue(const Type &value)  
　　{  
　　　LastInsert(value);  
　　}  
 
　Type DeQueue()  
　{   
　　Type p = *GetNext();  
　　RemoveAfter();  
　　IsEmpty();  
　　return p;  
　}  
 
　Type GetFront()  
　{  
　　return *GetNext();  
　}  
 
　List ::MakeEmpty;  
　List ::IsEmpty;  
 
};  
#endif 

　　測試程序

#ifndef StackTest_H  
#define StackTest_H  
#include "Stack.h"  
 
void StackTest_int()  
{  
　cout << endl << "整型棧測試" << endl;  
　cout << endl << "構造一個空棧" << endl;  
　Stack<int> a;  
　cout << "將1～20入棧，然后再出棧" << endl;  
　for (int i = 1; i <= 20; i++) a.Push(i);  
　　while (!a.IsEmpty()) cout << a.Pop() << ' ';  
　　cout << endl;  
}  
#endif  
 
#ifndef QueueTest_H  
#define QueueTest_H  
#include "Queue.h"  
 
void QueueTest_int()  
{  
　cout << endl << "整型隊列測試" << endl;  
　cout << endl << "構造一個空隊列" << endl;  
　Queue<int> a;  
　cout << "將1～20入隊，然后再出隊" << endl;  
　for (int i = 1; i <= 20; i++) a.EnQueue(i);  
　while (!a.IsEmpty()) cout << a.DeQueue() << ' ';  
　cout << endl;  
}  
#endif 

　　沒什么好說的，你可以清楚的看到，在單鏈表的基礎上，棧和隊列的實現(xiàn)是如此的簡單。

　　如讀者希望繼續(xù)閱讀棧和隊列的應用，請閱讀拓展文章C++數(shù)據(jù)結構學習之棧的應用和C++數(shù)據(jù)結構學習之隊列的應用 。

【編輯推薦】

1. 淺析C++棧使用方法
2. 18.3.1 隊列的概念
3. 數(shù)據(jù)庫使用C++數(shù)據(jù)結構
4. 程序員必看 c++筆試題匯總
5. c++編程常用工具