Ch03栈与队列3.ppt

第三章 栈与队列 3.1 栈 Stack 栈可定义为只允许在表的末端进行插入和删除的线性表。 允许插入和删除 的一端称为栈顶 top ，另一端称 为栈底 bottom 特点 先进后出 FILO 栈的抽象数据类型 二、顺序栈 栈的其他成员函数的实现 template void SeqStack ::overflowProcess //私有函数：当栈满则执行扩充栈存储空间处理 T *newArray new T[maxSize+stackIncreament]; //创建更大的存储数组 if newArray NULL cerr “存储分配失败！” endl; exit 1 ; for int i 0; i top; i++ newArray[i] elements[i]; maxSize maxSize+stackIncreament; delete []elements; elements newArray; //改变elements指针 ; template void SeqStack ::Push const T x if overflowProcess; //栈满 elements[++top] x; //栈顶指针先加1, 再进栈 ; template bool SeqStack ::Pop T x if IsEmpty true return false; x elements[top--]; //取当前元素值，栈顶指针退1 return true; //退栈成功 ; template bool Seqstack ::getTop T x //若栈不空则函数返回该栈栈顶元素的地址 if IsEmpty true return false; x elements[top]; return true; ; 三、栈的链接存储表示 — 链式栈 链式栈的栈顶在链头； 插入与删除仅在栈顶处执行； 链式栈无栈满问题，空间可扩充； 1.链式栈 LinkedStack 类的定义 template class LinkedStack //链式栈类定义 private: LinkNode *top; //栈顶指针 public: LinkedStack top NULL; //构造函数 ～LinkedStack makeEmpty ; //析构函数 void Push const T x ; //进栈 bool Pop T x ; //退栈 bool getTop T x const; //取栈顶 bool IsEmpty const return top NULL ? True:false; int getSize const; void makeEmpty ; //清空栈的内容 ; 2. 链式栈类操作的实现 template LinkedStack ::makeEmpty //逐次删去链式栈中的元素直至栈顶指针为空。 LinkNode *p; while top ! NULL //逐个结点释放 p top; top top- link; delete p; ; template void LinkedStack ::Push const T x top new LinkNode x, top ; //创建新结点 assert top ! NULL ; //创建失败退出 ; template bool LinkedStack ::getTop T x const if IsEmpty true return false; //栈空返回 x top- data; //返回栈顶元素的值 return true; ; * * * * * * * * template class LinkedQueue private: LinkNode *front, *rear; //队头、队尾指针 public: LinkedQueue :rear NULL , front NULL ~LinkedQueue ; bool EnQueue T x ; bool DeQueue T x ; bool GetFront T x ; void MakeEmpty ; //实现与~LinkedQueue 同 bool IsEmpty const return front NULL; int getSize co