《数据结构——栈与队列》由会员分享，可在线阅读，更多相关《数据结构——栈与队列（116页珍藏版）》请在金锄头文库上搜索。
1、3 栈与队列,栈与队列,2/132,主要内容,栈 栈的应用 队列 队列的应用,栈与队列,3/132,栈与队列,栈和队列是在程序设计中被广泛使用的两种线性数据结构。 与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。,栈与队列,4/132,栈,栈：限定仅只能在末端进行插入和删除的线性表。 栈顶：允许插入和删除的一端。 栈底：不允许插入和删除的一端。 时间有序表：先进后出（FILO) /后进先出（LIFO）,栈与队列,5/132,栈的基本操作, clear()清空栈。 isEmpty()判断栈是否为空。 push(el)将元素el放到栈的顶部。 pop()取出栈顶部
2、的元素。 topEl()获取栈顶部的元素，但不删除该元素。,栈与队列,6/132,栈顶指针top,指向实际栈顶 后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组大小为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,栈与队列,7/132,栈的表示和实现,顺序方式 链式方式,栈与队列,8/132,顺序表示的栈的实现,top,空栈: top = -1 MaxTop = = 4,3,1,2,0,栈与队列,9/132,栈的初始化操作,0 1 2 MaxTop-1,top,template Stack:Sta
3、ck(int MaxStackSize)MaxTop=MaxStackSize-1;stack=new TMaxStackSize;top=-1; ,栈与队列,10/132,进栈操作,0 1 2 maxSize-1,top,b,a,0 1 2 maxSize-1,top,b,a,c,template Stack ,栈与队列,11/132,出栈操作,template Stack ,0 1 2 maxSize-1,top,b,a,c,栈与队列,12/132,两个栈共享栈空间,-,link;delete top;top=next; ,栈与队列,18/132,栈的应用,数制转换 括号匹配 回文游戏 表
4、达式计算 计算中缀表带式的值 中缀、后缀表达式转换 匹配程序分隔符 大数加法（乘法） 递归,栈与队列,19/132,将一个非负十进制整数转换成八进制数并输出。 例 把十进制数159转换成八进制数。,数制转换,栈与队列,20/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,匹配情况：左括号4 右括号8左括号1 右括号11,算法：从左向右扫描字符串， (1)如果是左括号，就把它的位置编码压入栈中 (2)如果是右括号，则与栈顶的位置编码所指的左括号匹配。,栈与队列,21/132,括号匹配,匹配一个
5、字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,22/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,23/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,24/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2
6、 3 4 5 6 7 8 9 10 11,1,4,栈与队列,25/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,26/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,27/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,28/132
7、,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,8 4 匹配,栈与队列,29/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,30/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,31/132,括号匹配,匹配一个字符串中的左、右括
8、号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,32/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,11 1 匹配,栈与队列,33/132,括号匹配,匹配一个字符串中的左、右括号。如( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,8 4 匹配,11 1 匹配,栈与队列,34/132,算法思想： 读入字符串； 去掉空格（原串）； 压入
9、栈； 原串字符与出栈字符依次比较；若不等，非回文；若直到栈空都相等，回文。,回文游戏（顺读与逆读字符串一样（不含空格）,栈与队列,35/132,表达式计算,表达式都由操作数（也称运算对象）、操作符（也成运算符）和分界符组成。 算术表达式三种表示： （1）中缀(infix)表示： 例如A+B （2）前缀(prefix)表示： 例如+ AB （3）后缀(postfix)表示： 例如AB +,栈与队列,36/132,中缀表示,平时所用的表达式都是中缀表示。如A+B*(C-D)-E/F中缀表示中有操作符的优先级问题，并可以加括号改变运算顺序。用中缀表示求解表达式的值需要利用两个栈来实现，一个暂存操作数
10、，另一个暂存操作符。,栈与队列,37/132,计算中缀表达式算法思想,设置两个工作栈 运算符栈OPTR，运算符栈的栈底为表达式的起始符#。 操作数栈OPND，操作数栈为空栈。,栈与队列,38/132,计算中缀表达式算法思想,设isp(.)代表栈内优先级,icp(.)代表栈外优先级 依次读入表达式中的每个字符,若是 操作数,则进OPND栈； 运算符s1，则和OPTR中的栈顶元素s2做比较再操作。 若icp(s1)isp(s2)，则运算符入栈； 若icp(s1)isp(s2)，则从OPND栈顶弹出两个操作数，与OPTR中的栈顶元素做运算，并将运算结果入OPND； 若icp(s1)=isp(s2)，则OPTR中的栈顶元素出栈。 直至表达式扫描完毕。,栈与队列,39/132,各个算术操作符的优先级,操作符 # ( *,/,% +,- ),isp 0 1 7 5 3 8,icp 0 8 6 4 2 1,栈与队列,40/132,如： x = 3 (7-2);,OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,计算中缀表达式的值,栈与队列,41/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,计算中缀表达式的值,栈与队列,42/132,如： x = 3 (7-2),
