《数据结构资料课件》由会员分享，可在线阅读，更多相关《数据结构资料课件（82页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3.1 栈,3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现,3.2 栈的应用举例,3.4 队列,3.4.1 抽象数据类型队列的定义 3.4.2 链队列队列的链式表示和实现 3.3.3 循环队列队列的顺序表示和实现,3.1 栈 3.1.1 抽象数据类型栈
2、的定义,1、栈(Stack)的定义 栈是限定仅在表尾进行插入和删除操作的线性表。 术语 栈底(bottom) 栈的表头 栈顶(top)栈的表尾 空栈没有元素的栈 入栈(push) 向栈顶压入元素 出栈(pop) 从栈顶弹出元素,栈的特点 栈的修改是按后进先出的原则进行的。因此，栈称为后进先出的线性表（LIFO）。,3.1.1 抽象数据类型栈的定义,2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。,DCBA,3.1.1抽象数据类型栈的定义,2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2
3、)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,ABCDE,操作序列：,出栈序列：, 元素A入栈,A,A, 元素B入栈,B,B, 元素C入栈,C,C,3.1.1抽象数据类型栈的定义,2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,DE,操作序列：,出栈序列：, 元素A入栈,A, 元素B入栈,B, 元素C入栈, 元素C出栈,C,C, 元素B出栈,B,3.1.1 抽象数据类型栈的定义,2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出
4、序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,DE,操作序列：,出栈序列：, 元素A入栈,A, 元素B入栈, 元素C入栈, 元素C出栈,C, 元素B出栈,B, 元素D入栈,D,D, 元素D出栈,D, 元素A出栈,A,3.1.1 抽象数据类型栈的定义,2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,E,操作序列：,出栈序列：, 元素A入栈, 元素B入栈, 元素C入栈, 元素C出栈,C, 元素B出栈,B, 元素D入栈, 元素D出栈,D, 元素A出栈
5、,A, 元素E入栈,E,E, 元素E出栈,E,请大家思考如下问题,结合书上图3.1（b）铁路调度站示意图，如果有编号分别为1，2，3，4的四列火车顺序开过来，如果你是调度，有多少种出站顺序？分别是什么？ 14种出站顺序 1234、1243、1324、1342、1432、 2134、2143、2314、2341、2431、 3214、3241、3421、4321 推广到一般情况：,例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹
6、出一个即可。,435612中到了12顺序不能实现； 135426可以实现。,例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,答：,答：,例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,3.1.1 抽象数据类型栈的定义 3、栈的抽
7、象数据类型定义,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,顺序栈的C语言描述,Status InitStack (SqStack ,Status GetTop (SqStack S, SEle
8、mType ,Status Push (SqStack ,Status Pop (SqStack ,栈顶指针,链栈,a1,an,注意: 链栈中指针的方向,an-1,栈底元素,3.2 栈的应用举例,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.3 行编辑程序,3.2.4 迷宫求解,3.2.5 表达式求值,3.2.1 数制转换 算法基于原理：除d取余 N = (N div d)d + N mod d,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,vo
9、id conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,3.2.2 括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 ( ) 均为不正确的格式。,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧不是所“期待”的;,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7
10、8,到来的是“不速之客”;,直到结束，也没有到来所“期待”的括弧;,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,Status matching(string .,3.2.3 行编辑程序,如何实现？,“每接受一个字符即存入存储器” ?,并不恰当！,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允
11、许 用户输入出差错，并在发现有误时 可以及时更正。,合理的作法是：,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,相应算法的基本思想,可设这个输入缓冲区为一个栈结构，每当从终端接受一个字符之后先作如下判别： （1）非#和 则压入栈 （2）# 删除栈顶元素 （3） 清空栈,Void LineEdit() InitStack(S); ch = getchar(); DestroyStack(S); /LineEdit,while (ch != EOF / 从终
12、端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的 数据区；,3.2.4 迷宫求解,通常用的是“穷举求解”的方法,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方
13、块为 新的当前位置； 否则 while (栈不空）；,求迷宫中一条从入口到出口的路径的算法：, ,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ,若栈空，则表明迷宫没有通路。,typedef struct int ord; /在路径上的序号 int i, j; /坐标 int dir; /当前位置下一方向 SElemType;,ord i j dir 1 (1, 1) 1 2
14、 (1, 2) 2 3 (2, 2) 2 4 (3, 2) 1 5 (3, 3) 1 6 (3, 4) 4 7 (2, 4) 1 8 (2, 5) 1 9 (2, 6) 4 10 (1, 6) 3 11 (1, 5) 3 (1, 4) X (3, 1) 2 14 (4, 1) 2,5 (3, 3) 1 6 (3, 4) 4 7 (2, 4) 1 8 (2, 5) 1 9 (2, 6) 4 10 (1, 6) 3 11 (1, 5) 3 12 (1, 4) X,4 (3, 2) 3,一、算符优先法: 1、问题的提出 2、正确解释表达式是解决这个问题的关键，如何给计算机解释表达式？ 例如：4+2*
15、3-10/5 3、正确解释的实质在于算符的优先级别 4、表达式包括操作数（operand）、运算符（operator）和界限符（delimiter） 5、任意两个相继出现算符1和2的关系,3.2.5 表达式求值,书上表3.1所示优先关系说明,（1）算符相同，左遇到右时,（2）由规则三，运算符遇到“（”和“）”,（3）“#”是表达式的结束符，左边也虚设一个,（4）“（” = “）”表示当左右括号相遇时，括号内运算已经完成,（5）“#” = “#”表示,（6） “）”和“（” 相遇，或“#”和“（”相遇，语法错,二、算符优先法的实现,注：算法中两个函数： Precede（ 1，2）和Operate（a，theta，b）,算法思想 设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符 栈顶元素，压入OPTR栈。,表达式求值示意图：5+6(1+2)-4,#,+,(,+,-,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18
