（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第2讲 栈

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 栈定义 插入数据：入栈（Push） 删除数据：出栈（Pop） 后入先出：Last In First Out（LIFO） 应用 表达式求值 消除递归 深度优先搜索 栈 (Stack) 运算只在表的一端（栈顶，Top）进行（插入、删除等操作），属于线性表 不含元素的空表为空栈 按存储方式分为顺序栈和链式栈 . . . an . . . a2 a1 表头（栈底） 表尾（栈顶） 1 PART ONE 栈的抽象数据类型 栈定义 template <class T> class Stack { public: void clear(); bool push(const T item); bool pop(T& item); bool top(T& item); bool isEmpty(); bool isFull(); }; // 栈的运算集 // 变为空栈 // item入栈，成功返回真，否则假 // 返回栈顶内容并弹出，成功返回真，否则假 // 返回栈顶但不弹出，成功返回真，否则假 // 若栈已空返回真 // 若栈已满返回真 1 PART ONE 栈的存储 顺序栈(Array-based Stack) ：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。 通常由一个一维数组和一个记录栈顶元素位置的变量组成 链式栈（Linked Stack） 即为栈的链式存储结构，实际上就是一个单链表。插入和删除操作只能在链栈的栈顶进行，即 指针的方向是从栈顶向下链接 例：按压入先后次序，最后压入的元素编号为4，然后依次为3,2,1 1 PART ONE 栈的存储 时间效率 所有操作都只需常数时间 顺序栈和链式栈在时间效率上难分伯仲 空间效率 顺序栈须说明一个固定的长度 链式栈的长度可变，但增加结构性开销 顺序栈和链式栈的比较 实际操作 顺序栈读取内部元素的时间为O(1) 链式栈读取元素需要沿着指针链游走，显然慢些，读取第k个元素需要时间O(k) 顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素 顺序栈比链式栈用得更广泛 1 PART ONE 栈的存储——顺序栈的top指针 需要mSize-1个元素入栈，定义栈大小为mSize 满栈 top=mSize 每弹出一个元素， top减1 栈长度定义 空栈 top=0 每插入一个元素， top加1 下溢 (Underflow) 对空栈进行出栈运算时所产生的现象，即top<=0时的现象 上溢 (Overflow) 当栈中已经有mSize个元素时，如果再做进栈运算，所产生的现象 进栈 出栈 1 PART ONE template <class T> class arrStack: public Stack <T> { private: int mSize; int top; T *st; public: arrStack(int size) { mSize = size; top = -1; st = new T[mSize]; } arrStack() { top = -1; } ~arrStack() { delete [] st; } void clear() { top = -1; }}; // 栈的顺序存储 // 栈中最多可存放的元素个数 // 栈顶位置，应小于mSize // 存放栈元素的数组 // 栈的运算的顺序实现 // 创建一个给定长度的顺序栈实例 // 创建一个顺序栈的实例 // 清空栈 顺序栈的类定义 1 PART ONE 栈的基本操作 进栈：栈不满的情况下才可以进行进栈操作 清空栈：将top指向栈底，即top=0 出栈：执行出栈操作时要保证栈中有元素，此时top-- 取栈顶元素：top所指向的元素即为栈顶元素 初始化： top=0 出栈：先判断是否空栈 bool arrStack<T>::pop(T & item) {if (top == -1) { // 栈为空 cout << “空栈不能执行出栈"<< endl; return false; } else { item = st[top--]; // 返回栈顶，并缩减1 return true; }} 2 1 1 弹出元素2 进栈：先判断是否满栈 bool arrStack<T>::push(const T item) { if (top == mSize-1) { // 栈已满 c