栈和队列课件

1、数据结构数字媒体技术教研室3. 栈和队列Stack & Queue23. 栈和队列栈和队列也是线性表操作受限的线性表操作是线性表的子集广泛运用于各种软件系统3. 栈和队列栈和队列的定义和特点案例引入栈的表示和操作的实现队列的表示和操作的实现3.1.1 栈的定义和特点仅在表尾进行插入和删除操作的线性表称表尾端为栈顶（top）称表头端为栈底（bottom）不含元素的空表称为空栈3.1.1 栈的定义和特点栈的形式表示S=(a1, a2, , an)栈顶元素： an栈底元素： a1入栈：向栈顶插入元素，又叫压栈(Push)出栈：删除栈顶元素，又叫弹出(Pop)空栈：S=()67ana2a1栈顶栈底进栈

2、出栈后进先出LIFO3.1.1 栈的定义和特点栈举例泡腾片桶装薯片弹夹堆叠的盘子可以使数据反序3.1.2 队列的定义和特点只允许在一端插入元素而在另一端删除元素的线性表先进先出（FIFO，First In First Out）：排队生产流水线操作系统消息机制3.1.2 队列的定义和特点队头（front）：删除端队尾（rear）：插入端入队（enqueue）：插入操作出队（dequeue）：删除操作3.1.2 队列的定义和特点Q=(a1, a2, a3,ai-1, ai, ai+1, an)队头（front）： a1 队尾（rear）： an只能从队头删除元素，从队尾插入元素当元素a1 ai-1

3、全部退出队列后，元素ai才能退出队列（1i=n）1112a1a2a3an队首队尾出队入队先进先出FIFO3.2 案例引入案例3.2 括号匹配检验案例3.3 表达式求职【案例3.2】括号匹配检验假设表达式中包含()和两种括号正确格式：()()()，()()，错误格式：()，()，检验格式是否正确：按序列依次读入括号越后读入的左括号需要越早匹配右括号【案例3.2】括号匹配检验算法描述依次读取括号序列，并与栈顶元素匹配如果括号匹配成功，则弹出栈顶元素否则将当前读取的括号入栈括号序列读取完毕时：如果栈为空，表明括号序列格式正确否则表明括号序列匹配有错误()()()()()格式正确格式错误【案例3.3】

4、表达式求值设算术表达式仅包含加减乘除四则运算以及圆括号，则运算规则为：先乘除，后加减从左到右计算先括号内，再括号外1 + (4 + 5) * 3 10 / 5【案例3.3】表达式求值基于栈结构实现算符优先算法创建两个工作栈：OPTR：算符栈OPND：操作数栈18【案例3.3】表达式求值基于栈结构实现算符优先算法：两栈初始为空栈，OPTR栈先压入一个#依次读入表达式字符：操作数：进入OPND栈运算符：与OPTR栈顶元素比较优先级优先级高：执行计算并将结果压入OPND优先级低：将操作符压入OPTR左括号：压入OPTR；右括号：将栈顶左括号弹出当栈顶与读入字符同为#，运算结束19【案例3.3】表达式

5、求值求解：3 * (7 - 2)20*()37-2OPNDOPTR#3*(7-25153.3 栈的表示和操作实现栈的抽象数据类型定义3.3 栈的表示和操作实现栈ADT的基本操作线性表基本操作的子集23创建销毁清空判空求栈长取栈顶元素入栈出栈遍历3.3.1 栈的抽象数据类型定义InitStack(&S)操作结果：构造一个空栈SDestroyStack(&S)初始条件：栈S已存在操作结果：栈S被销毁243.3.1 栈的抽象数据类型定义ClearStack(&S)初始条件：栈S已存在操作结果：将栈S清空StackEmpty(S)初始条件：栈S已存在操作结果：栈S为空栈返回TRUE，否则返回FALSE

6、253.3.1 栈的抽象数据类型定义StackLength(S)初始条件：栈S已存在操作结果：返回栈S的长度GetTop(S, &e)初始条件：栈S已存在操作结果：用e返回栈S的栈顶元素263.3.1 栈的抽象数据类型定义Push(&S, e)初始条件：栈S已存在操作结果：将元素e入栈Pop(&S, &e)初始条件：栈S已存在操作结果：将栈S的栈顶元素出栈并由变量e返回273.3.1 栈的抽象数据类型定义StackTraverse(S)初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对栈S的每个元素进行访问2829栈底栈顶InitStack()SPush()251016235栈顶栈顶栈顶栈

7、顶栈顶Pop()DestroyStack()ClearStack()3.3.2 顺序栈的表示和实现用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素设置指针top标记栈顶部设置指针base标记栈底部3.3.2 顺序栈的表示和实现SElemType：元素类型base：栈底指针即顺序表首元素地址top：栈顶指针始终指向栈顶元素的下一位置空栈时指向栈底3.3.2 顺序栈的表示和实现顺序栈操作的实现初始化入栈出栈取栈顶元素1. 初始化为顺序栈分配一个预定义大小的数组空间算法分配一个最大容量为MAXSIZE的数组空间使栈底指针base指向此段空间栈顶指针top初始为base相同地址，表示栈为空Stacksize置为栈的最大容量MAXSIZE35topbaseSstacksize2. 入栈在栈顶插入一个新元素算法判断栈是否满，若满则返回ERROR将新元素压入栈顶，栈顶指针加13. 出栈将栈顶元素删除算法判断栈是否空，若满则返回ERROR栈顶指针减1，并将所指元素出栈41栈底栈顶InitStack()SPush()251016235栈顶栈顶栈顶栈顶栈顶Pop()DestroyStack()ClearStack()4. 取栈顶元素当栈非空时，返回栈顶元素但不删除，保持栈顶指针不变例题例1：已知一个栈S的输入序列为ABCD，下面两个序列能否通过栈的push和pop操作