数据结构与算法（Python语言版）课件 第6章 栈

第6章栈2025/6/111栈的特点

列表担当栈角色栈与递归栈与括号匹配栈与深度搜素栈与后缀表达式栈与undo操作6.1栈的特点2025/6/112栈擅长在线性表的尾部，即栈顶操作，栈是受限的线性表。压栈时，最先进栈的节点在栈底，最后进栈的节点在栈顶（俗话说，垒墙的砖，后来者居上），弹栈时，从栈顶开始弹出节点，最后一个弹出的节点是栈底节点。栈是一种后进先出的数据结构，简称LIFO（LastInFirstout）6.2列表担当栈角色2025/6/113

6.2列表担当栈角色2025/6/114回文串是指和其反转（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。2025/6/1156.2列表担当栈角色ch6_1.py例子2如果一个字符串的长度是偶数，只要判断字符串的前一半和后一半是否相同即可，如果一个字符串的长度是奇数，只要忽略字符串中间的字符，然后判断字符串的前一半和后一半是否相同即可。那么利用栈的特点，首先将字符串的字符逐个进栈，然后弹出一半字符压入另一个栈，然后比较两个栈中的字符是否相同，就可以判断一个字符串是否是回文串。利用栈判断一个字符串是否为回文串6.3栈与递归2025/6/116递归过程就是方法地址被压栈、弹栈的一个过程，所以，也可以利用栈这种数据结构，把某些递归算法改写为迭代算法。2025/6/1176.3栈与递归ch6_2.py例子2ch6_2.py中利用栈输出Fibonacci序列的前16项（有关Fibonacci序列的知识点和递归算法参见第3章中的例3-2）。利用栈输出Fibonacci序列的前几项6.4栈与括号匹配2025/6/118栈的特点使得它很适合被用来检查一个字符串中的括号是否是匹配的，即左、右括号是否是成对的。算法如下：2025/6/1196.4栈与括号匹配例子3检查括号是否匹配算法描述如下：（1）遍历字符串的每个字符，遇到左括号时压栈。（2）遇到右括号，如果此时栈为空，字符串中就出现了括号不匹配现象。如果栈不空，弹栈。如果字符串中的括号是匹配的，按着栈的特点，当遍历字符串遇到右括号时，此刻栈顶节点中的括号一定是和它相匹配的左括号，如果不是这样，字符串中的括号就出现了不匹配现象。ch6_3.py6.5栈与深度搜索2025/6/1110深度优先搜索算法，在进行遍历或者说搜索的时候，选择一个没有被搜过的节点，按照深度优先：一直往该节点的后续路径节点进行访问，直到该路径的最后一个节点，然后再从未被访问的邻节点进行深度优先搜索，重复以上过程，直至所有点都被访问或搜索到指定的某些特殊节点，算法结束。深度优先搜索（DepthFirstSearch，DFS）和广度优先搜索（BreadthFirstSearch，BFS）都是图论里关于图的遍历的算法（见第13章13.5），但DFS算法的思想可以用于任何恰好适合使用DFS的数据搜索问题，不仅仅限于图论中的问题。6.5栈与深度搜索2025/6/1111讲解DFS思想的一个很好的例子是老鼠走迷宫。2025/6/11126.5栈与深度搜索例子4模拟老鼠走迷宫ch6_4.pych6_4.py中使用move_in_maze(maze,rows,columns)函数走迷宫。老鼠走过迷宫后，列表中元素值是1表示墙，0表示老鼠未走过的路，-1表示老鼠走过的路，2表示出口。对于其中一个迷宫，老鼠无法到达路口，因为任何路都无法到达出口，对于另外一个迷宫，老鼠成功到达出口.6.6栈与后缀表达式2025/6/1113后缀表达式（也称为逆波兰表达式）是由波兰数学家JanLukasiewicz在1920年发明的（那个时候还没有计算机）。后缀表达式是一种数学表达式的表示方式，其中运算符写在操作数的后面。例如：前面的中缀表达式(13+17)*6的后缀表达式是：1317+6*6.6栈与后缀表达式2025/6/1114使用栈计算后缀表达式的步骤：2025/6/11156.6栈与后缀表达式计算后缀表达式：1317+6*按照上述步骤形成的入栈（压栈），弹栈的示意图如图：中缀表达式是(13+17)*6后缀表达式2025/6/11166.6栈与后缀表达式ALG_suffix.py例子5使用栈计算后缀表达式ch6_5.py后缀表达式ALG_suffix.py中的string_to_array(expression)函数把后缀表达式expression中的运算数和运算符号存储到列表中（后缀表达式expression中的运算符和运算数之间、运算数之间要用空格分隔）；suffix(a)函数使用栈计算后缀表达式(a是string_to_array(expression)函数返回的列表).2025/6/11176.6栈与后缀表达式中缀表达式转换为后缀表达式2025/6/11186.6栈与后缀表达式例子6把中缀表达式转换为后缀表达式ch6_6.py●中缀表达式转换为后缀表达式ALG_suffix.py将例5中的ALG_suffix.py文件和本例ch6_6.py保存在同一目录中。本例中的infix_to_suffix(infix)函数把中缀表达式infix转换为后缀表达式，本例首先把一个中缀表达式转换为后缀表达式、计算后缀表达式的值（并显示后缀表达式）,然后让有户从键盘输出一个中缀表达式转换为后缀表达式、计算后缀表达式的值（不再显示后缀表达式）.6.7栈与undo操作2025/6/1119栈的“后进先出”的特点，适合用于设计undo操作，即撤销操作。撤销操作就是取消当前操作结果、恢复到上一次操作的结果。我们经常使用撤销操作，对此并不陌生，比如我们在编辑文本时，经常单击编辑器提供的“撤销”快捷按钮撤销刚刚键入文字，让文档恢复到上一次编辑操作的样子。可以用栈来实现undo操作，即把一系列操作结果压入栈中，当用户想回到上一步骤时，进行弹栈、弹出栈顶节点的对象，刚好是上一次的操作结果，恢复这个结果即可。可以不断地进行弹栈操作，直到栈为空，即恢复到最初的操作结果。2025/6/11206.7栈与undo操作ch6_7.py例子7撤销显示的汉字ch6_7.py中的窗体有一个标签组件，用户单击“