C++數據結構學習之棧和隊列

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

棧的定義和實現

#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 

隊列的定義和實現

#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 

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

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

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