第6章栈2025/6/101栈的特点列表担当栈角色栈与递归栈与括号匹配栈与深度搜素栈与后缀表达式栈与undo操作
6.1栈的特点2025/6/102栈擅长在线性表的尾部，即栈顶操作，栈是受限的线性表。压栈时，最先进栈的节点在栈底，最后进栈的节点在栈顶（俗话说，垒墙的砖，后来者居上），弹栈时，从栈顶开始弹出节点，最后一个弹出的节点是栈底节点。栈是一种后进先出的数据结构，简称LIFO（LastInFirstout）
6.2列表担当栈角色2025/6/103?
6.2列表担当栈角色2025/6/104回文串是指和其反转（倒置）相同的字符串，例如：racecar,123321，level”，toot，civic，pop，eye，rotator，pip都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。
2025/6/1056.2列表担当栈角色ch6_1.py例子2如果一个字符串的长度是偶数，只要判断字符串的前一半和后一半是否相同即可，如果一个字符串的长度是奇数，只要忽略字符串中间的字符，然后判断字符串的前一半和后一半是否相同即可。那么利用栈的特点，首先将字符串的字符逐个进栈，然后弹出一半字符压入另一个栈，然后比较两个栈中的字符是否相同，就可以判断一个字符串是否是回文串。利用栈判断一个字符串是否为回文串
6.3栈与递归2025/6/106递归过程就是方法地址被压栈、弹栈的一个过程，所以，也可以利用栈这种数据结构，把某些递归算法改写为迭代算法。
2025/6/1076.3栈与递归ch6_2.py例子2ch6_2.py中利用栈输出Fibonacci序列的前16项（有关Fibonacci序列的知识点和递归算法参见第3章中的例3-2）。利用栈输出Fibonacci序列的前几项
6.4栈与括号匹配2025/6/108栈的特点使得它很适合被用来检查一个字符串中的括号是否是匹配的，即左、右括号是否是成对的。算法如下：
2025/6/1096.4栈与括号匹配例子3检查括号是否匹配算法描述如下：（1）遍历字符串的每个字符，遇到左括号时压栈。（2）遇到右括号，如果此时栈为空，字符串中就出现了括号不匹配现象。如果栈不空，弹栈。如果字符串中的括号是匹配的，按着栈的特点，当遍历字符串遇到右括号时，此刻栈顶节点中的括号一定是和它相匹配的左括号，如果不是这样，字符串中的括号就出现了不匹配现象。ch6_3.py
6.5栈与深度搜索2025/6/1010深度优先搜索算法，在进行遍历或者说搜索的时候，选择一个没有被搜过的节点，按照深度优先：一直往该节点的后续路径节点进行访问，直到该路径的最后一个节点，然后再从未被访问的邻节点进行深度优先搜索，重复以上过程，直至所有点都被访问或搜索到指定的某些特殊节点，算法结束。深度优先搜索（DepthFirstSearch，DFS）和广度优先搜索（BreadthFirstSearch，BFS）都是图论里关于图的遍历的算法（见第13章13.5），但DFS算法的思想可以用于任何恰好适合使用DFS的数据搜索问题，不仅仅限于图论中的问题。
6.5栈与深度搜索2025/6/1011讲解DFS思想的一个很好的例子是老鼠走迷宫。
2025/6/10126.5栈与深度搜索例子4模拟老鼠走迷宫ch6_4.pych6_4.py中使用move_in_maze(maze,rows,columns)函数走迷宫。老鼠走过迷宫后，列表中元素值是1表示墙，0表示老鼠未走过的路，-1表示老鼠走过的路，2表示出口。对于其中一个迷宫，老鼠无法到达路口，因为任何路都无法到达出口，对于另外一个迷宫，老鼠成功到达出口.
6.6栈与后缀表达式2025/6/1013后缀表达式（也称为逆波兰表达式）是由波兰数学家JanLukasiewicz在1920年发明的（那个时候还没有计算机）。后缀表达式是一种数学表达式的表示方式，其中运算符写在操作数的后面。例如：前面的中缀表达式(13+17)*6的后缀表达式是：1317+6*
6.6栈与后缀表达式2025/6/1014使用栈计算后缀表达式的步骤：
2025/6/10156.6栈与后缀表达式计算后缀表达式：1317+6*按照上述步骤形成的入栈（压栈），弹栈的示意图如图：中缀表达式是(13+17)*6后缀表达式
2025/6/10166.6栈与后缀表达式ALG_suffix.py例子5使用栈计算后缀表达式ch6_5.py后缀表达式ALG_suffix.py中的string_to_array(expression)函数把后缀表达式expression中的运算数和运算符号存储到列表中（后缀表达式expression中的运算符和运算数