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++编程常用工具