《第三章 栈和队列》由会员分享，可在线阅读，更多相关《第三章 栈和队列（87页珍藏版）》请在金锄头文库上搜索。
1、 第 三 章栈 和 队 列1本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 栈和队列是重要的数据结构栈和队列是线性表的子集（是插入和删除受限的线性表）前言2本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的
2、类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 【学习目标学习目标】1. 掌握栈和队列这两种抽象数据类型的特点，并能 在相应的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法。3. 熟练掌握循环队列和链队列的基本操作实现算 法。4. 理解递归算法执行过程中栈的状态变化过程。【重点和难点重点和难点】栈和队列是在程序设计中被广泛使用的两种线 性数据结构，因此本章的学习重点在于掌握这两种 结构的特点，以便能在应用问题中正确使用。 3本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型
3、定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 【学习指南学习指南】在这一章中，主要是学习如何在求解应用 问题中适当地应用栈和队列，栈和队列在两种 存储结构中的实现都不难，但应该对它们了如 指掌，特别要注意它们的基本操作实现时的一 些特殊情况，如栈满和栈空、队满和队空的条 件以及它们的描述方法。4本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的
4、应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 【课前思考课前思考】 1. 什么是线性结构？简单地说，线性结构是一个数据元素的 序列。2. 你见过餐馆中一叠一叠的盘子吗？如果 它们是按1,2,n 的次序往上叠的, 那么使用 时候的次序应是什么样的？必然是依从上往下的次序，即n,2,1。 它们遵循的是“后进先出“的规律，这正是本 章要讨论的“栈“的结构特点。 3. 在日常生活中，为了维持正常的社会秩 序而出现的常见现象是什么？是“排队“。在
5、计算机程序中，模拟排队 的数据结构是“队列“。5本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 栈必须按“后进先出”的规则进行操作 队列必须按“先进先出”的规则进行操 作 和线性表相比，它们的插入和删除操作 受更多的约束和限定，故又称为限定性的 线性表结构从“数据结构”的角度看: 它们都是线性结构，即数据元素之间的关 系相同。 但它
6、们是完全不同的数据类型。除了它们 各自的基本操作集不同外，主要区别是对 插入和删除操作的“限定“。6本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 通常称，栈和队列是限定插入 和删除只能在表的“端点”进行的 线性表。线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x
7、)1in+1Delete(L, i) Delete(S, n) Delete(Q, 1)1in栈和队列是两种常用的数据类型7本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 3.1 栈8本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型
8、的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 3.1.1 栈的类型定义栈（Stack）是限定只能在表的一端 进行插入和删除操作的线性表。在表 中，允许插入和删除的一端称作“栈顶 (top)”，不允许插入和删除的一端称作 “栈底(bottom)“ 。 9本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类
9、型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 通常称往栈顶插入元素的操作为“入栈“， 称删除栈顶元素的操作为“出栈“。因为后入栈的元素先于先入栈的元素出栈，故被称为 是一种“后进先出“的结构，因此又称LIFO（ Last In First Out的缩写）表。很多书上都以如下图所示的铁路调度站形象地表示栈的这 个特点。 10本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的
10、 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 栈的类型定义ADT Stack 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack11本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列
11、数据结构数据结构 InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;21本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队 列列数据结构数据结构 实现：一维数组sMtop123450进栈A栈
12、满BCDEF设数组维数为M top=base,栈空,此时出 栈,则下溢（ underflow) top=M,栈满,此时入栈, 则上溢（overflow)toptoptoptoptop123450空栈topbasebasetop 出栈top top栈 空base栈底指针base,始终指 向栈底位置；栈顶指 针top,其初值指向栈底 ，始终在栈顶元素的 下一个位置123450ABtop22本本 章章 小小 结结 习习 题题 3.1 3.1 栈的类型定义栈的类型定义3.2 3.2 栈的应用举例栈的应用举例3.3 3.3 栈类型的实现栈类型的实现3.4 3.4 队列的类型队列的类型定义定义3.5 3.5 队列类型队列类型 的的 实现实现前前 言言第第 三三 章章栈栈 和和 队队
