在C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中，順序表示的棧和隊(duì)列，必須預(yù)先分配空間，并且空間大小受限，使用起來(lái)限制比較多。而且，由于限定存取位置，順序表示的隨機(jī)存取的優(yōu)點(diǎn)就沒(méi)有了，所以，鏈?zhǔn)浇Y(jié)構(gòu)應(yīng)該是***。

　　棧的定義和實(shí)現(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 

　　隊(duì)列的定義和實(shí)現(xiàn)

#ifndef Queue_H  
#define Queue_H  
#include "List.h"  
 
template <class Type> class Queue : List//隊(duì)列定義  
{  
　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 

　　測(cè)試程序

#ifndef StackTest_H  
#define StackTest_H  
#include "Stack.h"  
 
void StackTest_int()  
{  
　cout << endl << "整型棧測(cè)試" << endl;  
　cout << endl << "構(gòu)造一個(gè)空棧" << 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 << "整型隊(duì)列測(cè)試" << endl;  
　cout << endl << "構(gòu)造一個(gè)空隊(duì)列" << endl;  
　Queue<int> a;  
　cout << "將1～20入隊(duì)，然后再出隊(duì)" << endl;  
　for (int i = 1; i <= 20; i++) a.EnQueue(i);  
　while (!a.IsEmpty()) cout << a.DeQueue() << ' ';  
　cout << endl;  
}  
#endif 

　　沒(méi)什么好說(shuō)的，你可以清楚的看到，在單鏈表的基礎(chǔ)上，棧和隊(duì)列的實(shí)現(xiàn)是如此的簡(jiǎn)單。

　　如讀者希望繼續(xù)閱讀棧和隊(duì)列的應(yīng)用，請(qǐng)閱讀拓展文章C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之棧的應(yīng)用和C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之隊(duì)列的應(yīng)用 。

【編輯推薦】

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