栈和队列(必备).doc

栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。栈的定义和实现#ifndefStack_H#defineStack_H#include"List.h"templateclassStack:List//栈类定义{public:voidPush(Typevalue){Insert(value);}TypePop(){Typep=*GetNext();RemoveAfter();returnp;}TypeGetTop(){return*GetNext();}List::MakeEmpty;List::IsEmpty;};#endif队列的定义和实现#ifndefQueue_H#defineQueue_H#include"List.h"templateclassQueue:List//队列定义{public:voidEnQueue(constType&value){LastInsert(value);}TypeDeQueue(){Typep=*GetNext();RemoveAfter();IsEmpty();returnp;}TypeGetFront(){return*GetNext();}List::MakeEmpty;List::IsEmpty;};#endif测试程序#ifndefStackTest_H#defineStackTest_H#include"Stack.h"voidStackTest_int(){cout<<endl<<"整型栈测试"<<endl;cout<<endl<<"构造一个空栈"<<endl;Stacka;cout<<"将1～20入栈，然后再出栈"<<endl;for(inti=1;i<=20;i++)a.Push(i);while(!a.IsEmpty())cout<<a.Pop()<<'';cout<<endl;}#endif#ifndefQueueTest_H#defineQueueTest_H#include"Queue.h"voidQueueTest_int(){cout<<endl<<"整型队列测试"<<endl;cout<<endl<<"构造一个空队列"<<endl;Queuea;cout<<"将1～20入队，然后再出队"<<endl;for(inti=1;i<=20;i++)a.EnQueue(i);while(!a.IsEmpty())cout<<a.DeQueue()<<'';cout<<endl;}#endif【后记】没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单，这也是我对于原书重复建设不满的最大原因。