国家级精品课程—《数据结构与算法》 第3章栈与队列 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:赵海燕 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 ©版权所有，转载或翻印必究 第3章 栈与队列
主要内容 31栈(tack) 32队列( Queue) 33栈和队列的比较 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 3.1 栈(Stack) ◼ 3.2 队列(Queue) ◼ 3.3 栈和队列的比较
大纲 2.1线性表( linear list) A2.2顺序表一向量( Sequential list-- - vector 23链表 Linked list 24线性表实现方法的比较 25栈( Stack) 26队列( Queue) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 大纲 ◼ 2.1 线性表(linear list) ◼ 2.2 顺序表—向量(Sequential list—vector ) ◼ 2.3 链表(Linked list) ◼ 2.4 线性表实现方法的比较 ◼ 2.5 栈(Stack) ◼ 2.6 队列(Queue)
操作受限的线性表 栈( Stack) 口运算只在表的一端进行 队列( Queue) 口运算只在表的两端进行 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 操作受限的线性表 ◼ 栈（Stack） ❑ 运算只在表的一端进行 ◼ 队列（Queue） ❑ 运算只在表的两端进行
栈 后进先出( Last nFirstout) a一种限制访问端口的线性表 口栈存储和删除元素的顺序与元素到达的顺序相反 口也称为“下推表” 栈的主要元素 口栈顶(top)元素:栈的唯一可访问元素 元素插入栈称为“入栈”或“压栈”(push) 删除元素称为“出栈”或“弹出”(pop) 栈底:另一端 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈 ◼ 后进先出（LastInFirstOut） ❑ 一种限制访问端口的线性表 ❑ 栈存储和删除元素的顺序与元素到达的顺序相反 ❑ 也称为“下推表” ◼ 栈的主要元素 ❑ 栈顶（top）元素：栈的唯一可访问元素 ◼ 元素插入栈称为“入栈”或“压栈”（push） ◼ 删除元素称为“出栈”或“弹出”（pop） ❑ 栈底：另一端
栈的示意图 每次取出(并被删除) 的总是刚压进的元素, 出栈 进栈 而最先压入的元素则 被放在栈的底部 栈顶 当栈中没有元素时称 为“空栈” kI 栈底 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的示意图 ◼ 每次取出（并被删除） 的总是刚压进的元素， 而最先压入的元素则 被放在栈的底部 ◼ 当栈中没有元素时称 为“空栈” k0 k1 ... kn-1 栈顶 栈底 出栈 进栈
栈的主要操作 压栈(push) 出栈(pop) 读取栈顶元素(top) 判断栈是否为空( isEmpty) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 栈的主要操作 ◼ 压栈（ push ） ◼ 出栈（pop） ◼ 读取栈顶元素（ top ） ◼ 判断栈是否为空（ isEmpty ）
栈的抽象数据类型 tem plate ∥栈的元素类型为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 // 栈的元素类型为 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 arrStack: public Stack 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 arrStack : public Stack { 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; } }