栈与队列的基本操作及其应用.pptVIP

int main( ){ int i; Queuechar que; //缺省为18元素队列，可用17 char str1[]=abcdefghijklmnop; //17个元素，包括串结束符 for(i=0;i17;i++) que.EnQue(str1[i]); for(i=0;i17;i++) coutque.DeQue(); //先进先出 coutendl; if(que.IsEmpty()) cout“队空”endl; return 0; } 【例7.11】链队类模板 【例7.11】链队类模板 templatetypename Tvoid QueueT::MakeEmpty(){ NodeT *temp; while(front!=NULL){ temp=front; front=front-link;delete temp; } } templatetypename TQueueT::~Queue(){ MakeEmpty(); } templatetypename T void QueueT::EnQue(const T data){ if(front==NULL) front=rear=new NodeT(data,NULL); else rear=rear-link=new NodeT(data,NULL); } //链队向后生成 【例7.11】链队类模板 templatetypename TT QueueT::DeQue(){ assert(!IsEmpty()); NodeT *temp=front; T data=temp-info; //取队头结点中的数据 front=front-link; //队头出队 delete temp; //释放内存空间 return data; } templatetypename TT QueueT::GetFront(){ assert(!IsEmpty()); return front-info; } * * * * * * * * * * * * * * * * * * * * * * * * * * * * * C++程序设计 7.3 栈与队列的基本操作及应用 东南大学VC++课程06级 copyright: 柏毅 版本号：V2005.08-06.01 7.3 栈与队列的基本操作及其应用 　栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。 7.　3.　1 栈 7.　3.　3　　队　列 7.　3.　2 栈　的　应　用 7.3.1 栈 　 栈定义为只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做栈顶(top)，而另一端叫栈底(bottom)。栈中没有任何元素时，称为空栈。进栈时最先进栈的在最下面，最后的在最上面，后来居上。而出栈时顺序相反，最后进栈的最先出栈，而最先进栈的最后出栈。所以栈又称作后进先出的线性表。 栈可以用顺序表实现，称顺序栈；也可以用链表实现，称链栈。 　参见下图，设给定栈s=(a0，a1，……，an-1)，称a0为栈底，an-1为栈顶。进栈时最先进栈的a0在最下面，an-1在最上面。而出栈时顺序相反，最后进栈的an-1最先出栈，而最先进栈的a0最后出栈。 a0 an-2 …… a1 an-1 bottom 进栈 top top top top top 出栈 图示为顺序栈。其中栈底bottom是指向栈数据区的下一单元，这样判断是否为空栈会更方便，只需top与bottom相同就是空栈。通常只有栈顶与操作有关。 templatetypename Tclass Stack{ int top; //栈顶指针（下标） T *elements; //动态建立的元素 int maxSize; //栈最大容纳的元素个数 public: Stack(int=20); //构造函数，栈如不指定大小，设为20元素 ~Stack( ){delete[ ] elements;} void Push(const T data); //压栈 T Pop( ); //弹出，top-- T