数据结构与算法__第三章_清华大学出版社_赵玉兰概要.ppt

第3章 栈和队列 3.1 栈 3.2 队列 3.3 栈与队列的应用 3.1 栈——ADT栈 栈（Stack） 只允许在表的一端进行插入和删除的线性表 允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom） 不含元素的栈称为空栈 插入：进栈，入栈 删除：出栈，退栈 3.1 栈——ADT栈 问题 有三个元素按 a1, a2, a3 的次序依次进栈，其出栈次序有几种可能？ 3.1 栈——ADT栈 栈的抽象数据类型 ADT Stack { Data 数据项列表 top：栈顶位置 Operations Constructor Process：创建一个空栈 IsEmpty Process：判断栈是否为空 Output：如果栈为空，则返回true，否则返回false GetTop Process：取栈顶元素 Output：返回栈顶元素 3.1 栈——ADT栈 Length Process：求栈中元素个数 Output：返回栈中元素的个数 Push Input：要添加的数据元素 Process：向栈中添加元素x，即进栈 Pop Process：删除栈顶元素，即出栈 Output：返回栈顶元素 Clear Process：删除栈中所有元素并置新的栈顶 } //Stack 3.1 栈——栈的实现 顺序栈 顺序栈的定义 3.1 栈——栈的实现 3.1 栈——栈的实现 const int MaxStackSize=50; //栈中能容纳最大元素个数 class SeqStack { DataType StackList[MaxStackSize]; int top; public: Stack (); //构造函数，初始化top bool IsEmpty (); //判断栈的状态是否为空 bool IsFull (); DataType GetTop (); //取栈顶元素 void Push (const DataType x); //入栈 DataType Pop (); //出栈 void Clear (); //栈清空 };// SeqStack 3.1 栈——栈的实现 顺序栈的操作的实现 构造函数，初始化一个空栈 Stack ( ) { StackList = new DataType[MaxStackSize]; top=-1; }// Stack 3.1 栈——栈的实现 判断栈是否为空 bool IsEmpty ( ) { if (top==-1) return true; else return false; }// IsEmpty 3.1 栈——栈的实现 判断栈是否已满 bool IsFull( ){ if (top==MaxStackSize-1) return true; else return false; }// IsFull 3.1 栈——栈的实现 3.1 栈——栈的实现 向栈顶压入元素 void Push (DataType x) { if (IsFull( )) { cout”栈满！”endl; else StackList[++top] = x; }// Push 3.1 栈——栈的实现 删除栈顶元素 DataType Pop( ){ if (IsEmpty( )) { cou