3栈及队列(基础知识).ppt

第三章 栈和队列 3.1 栈（stack） 栈的几个概念 栈顶 栈底 空栈。 3.2 栈的应用 3.2.1 数制转换 3.4 队列 队列的几个概念 第三章习题 第三章习题 * * 3.1 栈 3.2 栈的应用举例 3.4 队列 an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an) 特点：先进后出（FILO）或后进先出（LIFO） top 1 2 3 4 5 0 进栈 A 栈满 B C D E F top top top top top 1 2 3 4 5 0 空栈 top base base top 出栈 top top 栈空 base 1 2 3 4 5 0 A B top 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 *3.2.4 迷宫求解 *3.2.5 表达式求值 十进制整数 二、八、十六进制数 1348 top top 4 top 4 0 top 4 0 5 例如： (1348)10=(2504)8，其运算过程如下： 计算顺序 输出顺序 top 4 0 5 2 168……4 21……0 2……5 0……2 3.3.2 括号匹配的检验 ——括号总是成对出现的 例如: [ ( 3 + 5 ) * 7 ] – 3 括号匹配 [ ( 3 + 5 * 7 ] – 3 [ ( 3 + 5 ]* 7 ) – 3 括号不匹配 top [ ( [ ( 3 + 5 ) * 7 ] – 3 top top top top 栈空 匹配 匹配：字符串到尾，栈空 不匹配：（1）右括号，栈空 （2）右括号，栈顶不匹配 （3）串尾，栈不为空 top [ ( [ ( 3 + 5 ]* 7 ) – 3 top top 右括号与栈顶括号不 匹配 3.2.3 行编辑程序问题 p49 如何实现？ “每接受一个字符即存入存储器” ? 不恰当! 合理的作法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。 假设从终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行： while (*s) putchar(*s++); a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 队列特点：先进先出(FIFO) 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 3.1 设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题： （1）若入栈次序为push(1)，pop()，push(2），push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？ 3.2 如果进站的车厢序列为123，可能得到的出站车厢序列是什么？ 123 132 213 231 321 3.3如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。 135426 SXSSXSSXXXSX