清华数据结构chapter3_stack_v1_601503942.pptVIP

第三章 栈与队列（1） 数据结构电子教案 第三章 栈与队列 栈 队列 栈的应用：表达式求值 栈的应用：递归 队列的应用：打印杨辉三角形 优先级队列 栈 ( Stack ) 只允许在表的一端进行插入和删除的线性表 //考虑指针个数和栈空、栈满表示 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 （LIFO - Last In First Out) 定义ADT 栈（Stack） 特殊的线性表 插入、删除操作 只能在一端进行, 另一端禁止 严格说，查找操作也是如此 Push() / Pop() / getTop() 特点 后进先出—LIFO 儿童玩具手枪的子弹夹, 铁路调度编组站都是栈在实际生活中的应用原型 栈的抽象数据类型 栈的数组存储表示 — 顺序栈 顺序栈的构造函数 template class T SeqStackT :: SeqStack(int sz) :top(-1), maxSize(sz){ //建立一个最大尺寸为sz的空栈，若分配不成功则错误处理 elements = new T[maxSize]；//创建栈的数组空间 assert(elements != NULL)；//动态分配是否成功 } ； //断言（assert）机制—若断言语句assert参数表中给定的条件满足，则继续执行后续的语句；否则将调用stdlib.h中的函数abort,打印出错行号和文件名，出错处理，终止程序的执行。 顺序栈的操作 template class T void SeqStackT::overflowProcess() { //私有函数：当栈满则执行扩充栈存储空间处理 T *newArray = new T[2*maxSize]; //创建更大的存储数组，创建成功检查省略 for (int i = 0; i = top; i++) newArray[i] = elements[i]; maxSize += maxSize; delete [ ]elements; elements = newArray; //改变elements指针 }; template class T void SeqStackT::Push(T x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess; //栈满 elements[++top] = x; //栈顶指针先加1, 再进栈 }; template class T bool SeqStackT::Pop(T x) { //退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; //先退栈顶元, 然后指针退1 return true; //退栈成功 }; template class T bool SeqstackT::getTop(T x) { //若栈不空则函数返回该栈栈顶元素 if (IsEmpty() == true) return false; x = elements[top]; return true; }; 一个栈利用一片连续空间难免造成浪费 解决办法：双栈共享一个栈空间 栈的链接存储表示 — 链式栈 链式栈忽略栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作 链式栈 (LinkedStack)类的定义 #include iostream //具体 实现时的一种头文件形式 #include assert.h #include “stack.h” using namespace std; template class T struct StackNode { //栈结点类定义 T data; //栈结点数据 StackNodeT *link; //结点链指针 StackNode(T d = 0, StackNodeT *next = NULL) : data(d), link(next) { } //构造函数 }; //VC6.0库文件有iostream.h,编译可以通过.但是VS2005和VS2008没有这