栈的示意图 每次取出(并被删除) 的总是刚压进的元素, 出栈 进栈 而最先压入的元素则 被放在栈的底部 栈顶 当栈中没有元素时称 为“空栈” kI 栈底 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的示意图 ◼ 每次取出（并被删除） 的总是刚压进的元素， 而最先压入的元素则 被放在栈的底部 ◼ 当栈中没有元素时称 为“空栈” k0 k1 ... kn-1 栈顶 栈底 出栈 进栈
栈的主要操作 压栈(push) 出栈(pop) 读取栈顶元素(top) 判断栈是否为空( isEmpty) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的主要操作 ◼ 压栈（ push ） ◼ 出栈（pop） ◼ 读取栈顶元素（ top ） ◼ 判断栈是否为空（ isEmpty ）
栈的抽象数据类型 tem plate <class t> ∥栈的元素类型为T class stack i public ∥栈的运算集 void clear(; ∥变为空栈 bool push( const T item;∥item入栈,成功则返回真,否则返回假 bool pop(T&item);∥返回栈顶内容并弹出,成功返回真,否则返回假 bool top(T&item);∥返回栈顶内容但不弹出,成功返回真,否则返回假 bool isEmpty(∥若栈已空返回真 bool isFull(: ∥若栈已满返回真 } “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的抽象数据类型 template <class T> // 栈的元素类型为 T class Stack { public: // 栈的运算集 void clear(); // 变为空栈 bool push(const T item); // item入栈，成功则返回真，否则返回假 bool pop(T & item); // 返回栈顶内容并弹出，成功返回真，否则返回假 bool top(T& item); // 返回栈顶内容但不弹出，成功返回真，否则返回假 bool isEmpty(; // 若栈已空返回真 bool isFull(); // 若栈已满返回真 };
栈的实现方式 顺序栈( Array-based Stack) 口使用向量实现,本质上是顺序表的简化版 栈的大小 口关键是确定哪一端作为栈顶 m链式栈( Linked stack) 口用单链表方式存储,其中指针的方向是从栈顶 向下链接 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的实现方式 ◼ 顺序栈（Array-based Stack） ❑ 使用向量实现，本质上是顺序表的简化版 ◼ 栈的大小 ❑ 关键是确定哪一端作为栈顶 ◼ 链式栈（Linked Stack） ❑ 用单链表方式存储，其中指针的方向是从栈顶 向下链接
顺序栈 template <class T> class arrStack: public Stack <T> private ∥栈的顺序存储 int mIze ∥栈中最多可存放的元素个数 ∥栈顶位置,应小于 mIze T ∥存放栈元素的数组 public: ∥栈的运算的顺序实现 arrStack ( int size)t ∥创建一个给定长度的顺序栈实例 sIze= size; top=-1; st= new T[mSizel; arrStack(i ∥刨建一个顺序栈的实例 top=-1; -arrStack(O[ ∥析构函数 delete I st void clear(t ∥清空栈内容 top=-1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序栈 template <class T> class arrStack : public Stack <T> { private: // 栈的顺序存储 int mSize; // 栈中最多可存放的元素个数 int top; // 栈顶位置，应小于mSize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrStack(int size) { // 创建一个给定长度的顺序栈实例 mSize = size; top = -1; st = new T[mSize]; } arrStack() { // 创建一个顺序栈的实例 top = -1; } ~arrStack() { // 析构函数 delete [] st; } void clear() { // 清空栈内容 top = -1; } }