第3章栈与队列详解.pptx

1 第三章 栈与队列 数据结构电子教案 殷人昆 王 宏 栈 ( Stack ) 队列 ( Queue ) 栈的应用：算术表达式求值(略) 自顶向下、逐步分解的策略 2 栈 队列 栈的应用：表达式求值 栈的应用：递归 队列的应用：打印杨辉三角形 优先级队列 第三章 栈与队列 3 只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO —Last In First Out) 栈 ( Stack ) 退栈 进栈 a0 an-1 an-2 ? top bottom 4 // Stack.h 栈类模板头文件 template class E // E是栈中每个元素的类型 class Stack { //栈类模板(抽象基类,无法实例化对象) public://栈定义所有派生子类必须原样重写的虚函数 Stack(){ }; //构造函数 virtual bool Push(E x) = 0; //进栈:元素x→新栈顶 virtual bool Pop(E x) = 0; //出栈:栈顶元素→x virtual bool getTop(E x) const=0;//取栈顶元素→x virtual bool IsEmpty() = 0; //判栈空 virtual bool IsFull() = 0; //判栈满 };//项目:Push element to or pop from the sequential stack 栈的抽象数据类型 5 // SeqStack.h 顺序栈类模板头文件 // 顺序栈继承栈类(抽象基类)，必须与基类完全 // 相同格式定义全部虚函数才能实例化定义对象 #include assert.h #include iostream using namespace std; #include stack.h template class E class SeqStack : public StackE { 栈的数组存储表示 — 顺序栈 6 protected: //顺序栈由若干栈元素组成 E* elements; //栈元素表(动态分配的首元素地址) int top; //栈顶指针(栈顶元素的下标) int maxSize; //栈最大容量(栈可容纳的元素个数) void overflowProcess(); //栈的溢出处理 public: SeqStack(int sz =10); //构造函数,默认栈容量为10 ～SeqStack() { delete []elements; } //析构函数 bool Push(E x); //若栈不满:栈顶增 1，x→新栈顶 bool Pop(E x); //出栈:栈顶元素→x，栈顶减 1 bool getTop(E x) const; //取栈顶元素→x,栈顶不变 bool IsEmpty() const { return top == -1; } bool IsFull() const { return top == maxSize-1; } }; 7 top=-1 空栈 top=0 top=1 top=4 top=4 top=3 a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 a b d e e 退栈 c 8 top=-1 c 退栈 b 退栈 a b a a 退栈 空栈 top=2 a b d d 退栈 c top=1 a b c top=0 top=-1 9 template class E //构造函数 SeqStackE::SeqStack(int sz) : top(-1) , maxSize(sz) { //分配栈元素存放数组，数组大小为maxSize elements = new E[maxSize]; } 10 顺序栈的操作 //保护函数：当栈满则执行扩充栈存储空间处理 template class E void SeqStackE::overflowProcess() { //创建原来2倍大小的存储数组 E* newArray = new E[2*maxSize]; //原栈元素逐个复制到新数组 for (int i = 0; i = top; i++) newArray[i] = elements[i]