第3章栈和队列 3.1栈 3.2栈的应用举例 3.3队列
第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列
第3章栈和队列 栈和队列是两种应用非常广泛的数据结构，它们 都来自线性表数据结构，都是“操作受限”的线性 表。与线性表相比，它们的插入和删除操作受更多 的约束和限定，故又称为限定性的线性表结构。 ◆线性表允许在表内任一位置进行插入和删除； ◆栈只允许在表尾一端进行插入和删除； ◆队列只允许在表尾一端进行插入，在表头一端进行删除
第3章 栈和队列 栈和队列是两种应用非常广泛的数据结构，它们 都来自线性表数据结构，都是“操作受限”的线性 表。与线性表相比，它们的插入和删除操作受更多 的约束和限定，故又称为限定性的线性表结构。 ◆线性表允许在表内任一位置进行插入和删除； ◆栈只允许在表尾一端进行插入和删除； ◆队列只允许在表尾一端进行插入，在表头一端进行删除
3.1栈 3.1.1栈的基本概念 1栈的概念 ◆栈(Stack):是限制在表的一端进行插入和删除 操作的线性表。 ◆也称为后进先出LIFO(Last In First Out)或先进 后出FILO(First In Last Out)线性表
3.1 栈 3.1.1 栈的基本概念 1 栈的概念 ◆栈(Stack)：是限制在表的一端进行插入和删除 操作的线性表。 ◆也称为后进先出LIFO (Last In First Out)或先进 后出FILO (First In Last Out)线性表
◆栈顶(Top):允许进行插入、删除操作的一端，又 称为表尾。用栈顶指针(top)来指示栈顶元素。 ◆栈底Base):是固定端，又称为表头。 ◆空栈：当表中没有元素时称为空栈 设栈S=(a,a2,.an), 进栈(push) 出栈pop) 则a称为栈底元素，an为栈 顶元素。 top 8 栈中元素按a1,a2, ·。。●。 .an的次序进栈，出栈的第 a ●900● 一个元素应为栈顶元素。即 a 栈的修改是按后进先出的原 base aL 则进行的
设栈S=(a1，a2，…an )， 则a1称为栈底元素，an为栈 顶元素。 栈中元素按a1，a2， …an的次序进栈，出栈的第 一个元素应为栈顶元素。即 栈的修改是按后进先出的原 则进行的。 a1 a2 ai an ⋯⋯ ⋯⋯ base top 进栈（push） 出栈(pop) ◆栈顶(Top)：允许进行插入、删除操作的一端，又 称为表尾。用栈顶指针(top)来指示栈顶元素。 ◆栈底(Base)：是固定端，又称为表头。 ◆空栈：当表中没有元素时称为空栈
例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个地拿， 一定最先拿走最上面的那只碗，而最后拿出最下 面的那只碗。 例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层一层地 拿取。 Top Stack of Coins Stack of Books Computer Stack
例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个地拿， 一定最先拿走最上面的那只碗，而最后拿出最下 面的那只碗。 例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层一层地 拿取
栈的抽象数据类型定义 ADT Stack 数据对象：D={ala:∈ElemSet,.=1,2,,n,n≥0} 数据关系：R={a1,a:∈D,=2,3,…,n} 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁
ADT Stack{ 数据对象：D ={ ai |ai∈ElemSet, i=1,2,…,n，n≥0 } 数据关系：R ={|ai-1，ai∈D, i=2,3,…,n } 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 2 栈的抽象数据类型定义
ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE,否则返回 FALSE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S中元素个数，即栈的长度。 GetTop(S,&e) 初始条件：栈S已存在且非空。 操作结果：用e返回$的栈顶元素
ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE，否则返回 FALSE。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回栈 S 中元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素
Push(&S,e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse(S,visit()) 初始条件：栈S已存在且非空，visit()为元素的 访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函 数visit(),一旦visit()失败，则操作失败。 ADT Stack
Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( )为元素的 访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函 数visit( )，一旦visit( )失败，则操作失败。 } ADT Stack
3.1.2 栈的表示和实现 和线性表类似，栈也有两种存储方法： >栈的顺序存储结构一一顺序栈； >栈的链式存储结构一一链栈
和线性表类似，栈也有两种存储方法： ➢栈的顺序存储结构——顺序栈； ➢栈的链式存储结构——链栈。 3.1.2 栈的表示和实现
3.1.2.1 栈的顺序存储表示 ◆顺序栈，即栈的顺序存储结构，是利用一组地址 连续的存储单元依次存放自栈底到栈顶的数据元素。 ◆设置指针top指向栈顶元素在顺序栈中的位置，通 常习惯做法是以top=O表示空栈。 ◆栈在使用的过程中所需最大空间的大小很难估计， 一般初始化设空栈时不限定栈的最大容量。 ◆一般先分配一个基本容量，然后应用过程中，栈 的空间不够使用时再逐段扩大
◆顺序栈，即栈的顺序存储结构，是利用一组地址 连续的存储单元依次存放自栈底到栈顶的数据元素。 ◆设置指针top指向栈顶元素在顺序栈中的位置，通 常习惯做法是以top=0表示空栈。 ◆栈在使用的过程中所需最大空间的大小很难估计， 一般初始化设空栈时不限定栈的最大容量。 ◆一般先分配一个基本容量，然后应用过程中，栈 的空间不够使用时再逐段扩大。 3.1.2.1 栈的顺序存储表示