数据结构与算法（Java语言版）课件 第7、8章 栈与Stack类、队列与ArrayDeque类

第7章栈与Stack类2024/11/917.1栈的特点2024/11/92栈擅长在线性表的尾部，即栈顶操作，栈是受限的线性表。压栈时，最先进栈的节点在栈底，最后进栈的节点在栈顶（俗话说，垒墙的砖，后来者居上），弹栈时，从栈顶开始弹出节点，最后一个弹出的节点是栈底节点。栈是一种后进先出的数据结构，简称LIFO（LastInFirstout）7.2栈的创建与独特方法2024/11/93Stack<E>是Vector<E>的子类，因此Stack<E>类的实例属于顺序表，即其中的节点的逻辑结构是线性结构，节点的存储结构是顺序存储。Stack<E>泛型类的实例使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。2024/11/947.2栈的创建与独特方法●创建栈使用Stack<E>泛型类声明栈时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等），即指定栈中节点的类型。例如，指定E是String类型：Stack<String>stack=newStack<>();或Stack<String>stack=newStack<String>();Stack<E>泛型类的实例使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。空栈默认的内部数组的长度是10（可以将内部数组理解为一块连续的内存空间）。2024/11/957.2栈的创建与独特方法●独特的方法

例子1中的主类Example7_1使用了栈的独特方法。Example7_1.java例子17.3栈与回文串2024/11/96回文串是指和其反转（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。2024/11/977.3栈与回文串Example7_2.java例子2如果一个字符串的长度是偶数，只要判断字符串的前一半和后一半是否相同即可，如果一个字符串的长度是奇数，只要忽略字符串中间的字符，然后判断字符串的前一半和后一半是否相同即可。那么利用栈的特点，首先将字符串的字符逐个进栈，然后弹出一半字符压入另一个栈，然后比较两个栈中的字符是否相同，就可以判断一个字符串是否是回文串。7.4栈与递归2024/11/98递归过程就是方法地址被压栈、弹栈的一个过程，所以，也可以利用栈这种数据结构，把某些递归算法改写为迭代算法。2024/11/997.4栈与递归Example7_3.java例子3例子3主类Example7_3中利用栈输出Fibonacci序列的前16项（有关Fibonacci序列的知识点和递归算法，参见第3章例子2）。2024/11/9107.4栈与递归Example7_4.java例子4例子4主类Example7_4中利用栈描述汉诺塔搬运盘子，这里的迭代算法，尽管比第3章例子12简单，但却无法显示盘子的号码，所以不是严格意义的替代递归的迭代算法（有关汉诺塔的知识点和递归、迭代算法，参见第3章例子11和例子12）。7.5栈与undo操作2024/11/911栈的“后进先出”的特点，适合用于设计undo操作，即撤销操作。撤销操作就是取消当前操作结果、恢复到上一次操作的结果。我们经常使用撤销操作，对此并不陌生，比如我们在编辑文本时，经常单击编辑器提供的“撤销”快捷按钮撤销刚刚键入文字，让文档恢复到上一次编辑操作的样子。可以用栈来实现undo操作，即把一系列操作结果压入栈中，当用户想回到上一步骤时，进行弹栈、弹出栈顶节点的对象，刚好是上一次的操作结果，恢复这个结果即可。可以不断地进行弹栈操作，直到栈为空，即恢复到最初的操作结果。2024/11/9127.5栈与undo操作Example7_5.java例子5例子5的主类中的窗体有一个标签组件，用户单击“显示一个汉字”按钮可以在标签上显示一个汉字。但标签上只保留最后一次显示的汉字。当用户单击“撤销”按钮时，将取消用户最近一次单击“显示一个汉字”按钮产生的操作效果，即将标签上的汉字恢复为上一次单击“显示一个汉字”按钮所得到的汉字。7.6栈与括号匹配2024/11/913栈的特点使得它很适合被用来检查一个字符串中的括号是否是匹配的，即左、右括号是否是成对的。算法如下：2024/11/9147.6栈与括号匹配Match.java例子6例子6中的Match类的isMatch(Strings)方法判断一个s中的字符串中的括号是否是匹配的。例子6的主类Example7_6中，判断了几个字符串中的而括号是否匹配。Example7_6.java7.6栈与深度搜索2024/11/915深度优先搜索算法，在进行遍历或者说搜索的时候，选择一个没有被搜过的节点，按照深度优先：一直往该节点的后续路径节点进行访问，直到该路径的最后一个节点，然后再从未被访问的邻节点进行深度优先搜索，重复以上过程，直至所有点都被访问或搜索到指定的某些特殊节点，算法结束。深度优先搜索（DepthFirstSearch，DFS）和广度优先搜索（BreadthFirstSearch，BFS）都是图论里关于图的遍历的算法（见第13章13.5），但DFS算法的思想可以用于任何恰好适合使用DFS的数据搜索问题，不仅仅限于图论中的问题。7.6栈与深度搜索2024/11/916讲解DFS思想的一个很好的例子是老鼠走迷宫。2024/11/9177.6栈与深度搜索MouseStack.java例子7Example7_7.java

例子7的主类Example7_7使用move(int[][]maze)方法走迷宫，输出该方法返回的一个二维数组，老鼠走过迷宫后，该二维数组元素值是1表示墙，0表示老师未走过的路，-1表示老鼠走过的路，2表示出口。在输出该二维数组时用☆表示老鼠走过的路，■表示墙，★表示出口，□表示老鼠未走过的路。7.7栈与后缀表达式2024/11/918后缀表达式（也称为逆波兰表达式）是由波兰数学家JanLukasiewicz在1920年发明的（那个时候还没有计算机）。后缀表达式是一种数学表达式的表示方式，其中运算符写在操作数的后面。例如：前面的中缀表达式(13+17)*6的后缀表达式是：1317+6*7.7栈与后缀表达式2024/11/919使用栈计算后缀表达式的步骤：2024/11/9207.7栈与后缀表达式计算后缀表达式：1317+6*按照上述步骤形成的入栈（压栈），弹栈的示意图如图：中缀表达式是(13+17)*6●后缀表达式2024/11/9217.7栈与后缀表达式CalculateSuffix.java例子8Example7_8.java例子8的中的Decompose类的stringToArray(Stringexpression)把参数expression表示的表达式中的操作数和运算符依次放到数组中，并返回该数组。CalculateSuffix类的doublesuffix(String[]a)方法使用栈计算后缀表达式。●后缀表达式例子8的中的主类Example7_8使用CalculateSuffix类的doublesuffix(String[]a)方法计算了几个后缀表达式的值。Decompose.java2024/11/9227.7栈与后缀表达式●中缀表达式转换为后缀表达式中缀表达式中的小括号，运算符和操作数存在一个String数组a中。例如，对于(3+7)*10-6，数组a为["(","3","+","7",")","*","10","-","6"]初始化inti=0,一个栈stack，用于求后缀表达式。一个顺序表list，用于存放后缀表达式的操作数和运算符。2024/11/9237.7栈与后缀表达式例子9Example7_9.java●中缀表达式转换为后缀表达式InfixToSuffix.java例子9中的InfixToSuffix类的String[]suffix(String[]infix)方法把中缀表达式转换为后缀表达式。例子9的主类Example7_9让用户从键盘输入中缀表达式，然后程序将其转换为后缀表达式，并计算后缀表达式（用到了例子8中的类），输出计算结果。第8章队列与ArrayDeque类2024/11/9248.1队列的特点2024/11/925队列擅长在线性表的头、尾两端实施删除和添加操作，甚至可以把线性表实现成只在头、尾两端操作，所以人们也称队列是受限的线性表。入列时，最先进入的节点在队头，最后进入的节点在队尾。出列时，从队列的头开始删除节点，最后一个删除的节点是队尾的节点。队列是一种先进先出的数据结构，简称FIFO（FirstInFirstout）8.1队列的特点2024/11/926头节点（队头）在左边、尾节点（队尾）在右边。8.2队列的创建与独特方法2024/11/927ArrayDeque<E>泛型类继承了Deque泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了Deque泛型接口中的抽象方法。ArrayDeque<E>采用数组方式实现队列这种数据结构，其实例属于顺序表，即节点的逻辑结构是线性结构，节点的存储结构是顺序存储。ArrayDeque<E>泛型类的实例的节点就是对象，后面的叙述不再说节点里的对象。8.2队列的创建与独特方法2024/11/928队列由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayDeque<E>泛型类所实现。2024/11/9298.2队列的创建与独特方法●创建队列ArrayDeque<E>采用数组方式实现队列这种数据结构，其实例属于顺序表，即节点的逻辑结构是线性结构，节点的存储结构是顺序存储。ArrayDeque<E>泛型类的实例的节点就是对象，后面的叙述不再说节点里的对象。使用ArrayDeque<E>泛型类声明队列时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定队列中节点（对象）的类型。。例如，指定E是Integer类型：ArrayDeque<Integer>queue=newArrayDeque<>();或ArrayDeque<Integer>queue=newArrayDeque<Integer>();空队列默认的内部数组的长度是8（可以将内部数组理解为一块连续的内存空间）。2024/11/9308.2队列的创建与独特方法●独特的方法例子1中的主类Example8_1使用了队列的独特方法。Example8_1.java例子1

8.3队列与回文串2024/11/931回文串是指和其反转（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我们曾在第3章例子4，使用递归方法判断一个字符串是否是回文串。2024/11/9328.3队列与回文串Example8_2.java例子2使用队列也可以判断一个字符串是否是回文串。将字符串中的全部字符按顺序依次入列，然后开始分别从头、尾出列，如果字符串是回文串，那么从头出列的节点一定和从尾出列的节点相同，当队列中剩余的节点数目不足2个时，停止出列。例子2主类Example8_2中利用队列判断几个字符串是否是回文串，读者可以和第7章例子2进行比较，体会栈和队列的各自特点。8.4队列与加密解密2024/11/933用队列可以方便地对字符串实施加密（解密）操作。出列的对象参与加密字符串中一个字符（出列的对象参与解密字符串中一个字符），然后再重新入列，一直到字符串中的字符全部被加密完毕（字符串中的全部字符被解密完毕）。2024/11/9348.4队列与加密解密EncryptionDecryption.java例子3Example8_3.javaExample8_3中的主类Example8_3使用EncryptionDecryption类的方法对字符串了加密，然后再解密8.5队列与约瑟夫问题2024/11/935简单再重复一下约瑟夫问题：若干个人围成一圈，从某个人开始顺时针（或逆时针）数到第3个人，该人从圈中退出，然后继续顺时针（或逆时针）数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的一个人。

2024/11/9368.5队列与约瑟夫问题Joseph.java例子4和第4章的例子9以及第5章的例子12相比较，使用队列的算法不仅更加容易理解，而且所实现的代码也具有很好的可读性。例子4的Joseph类的solveJoseph(intperson[])方法使用队列，解决约瑟夫问题.Example8_4.java8.6队列与广度搜索2024/11/937广度优先搜索（BreadthFirstSearch，BFS）是图的另一种遍历方式，与深度搜索（DFS）相对，是以广度优先进行搜索。其特点是先访问图的顶点，然后广度优先：依次进行被访问点的邻接点，一层一层访问，直至访问完所有节点或搜索到指定的节点，算法结束。栈的特点是后进先出，恰好能体现深度优先。队列的特点是，先进先出，恰好体现广度优先。8.6队列与广度搜索2024/11/938

8.6队列与广度搜索2024/11/939排雷算法描述如下：①将开始的排雷点入列，进行②②检查队列是否是空列，如果为空（雷就都被排除了）进行④，否则进行③③队列进行出列操作，将出列点的东西南北方向，没有被排雷的点入列，然后检查出列点是否是雷，并标记此点已排雷：如果是雷给出一个排雷的标记，如果是路给出一个路的标记，进行②④结束。2024/11/9408.6队列与广度搜索Deminers.java例子5Example8_5.java

注不可以一行、一行的排雷，这样做显然没有体现广度优先。8.7队列与网络爬虫2024/11/941一个网站往往维护着很多网页，这些网页之间通过超链接实现彼此的链接。网络爬虫的意思就是从网站的某个网页开始，通过网页之间的超链接、遍历该网站的所有网页来寻找满足要求的数据或信息。网络爬虫，一般都采用广度搜索。8.7队列与网络爬虫2024/11/942广度搜索算法中使用队列，就可以实现对网站的广度搜索，算法描述如下：①将开始的网页点入列，进行②②检查队列是否是空列，如果为空（所有网页就都访问过了）进行④,否则进行③③队列进行出列操作，将出列的网页中的所有没有被访问过的超链接入列，然后按着需求检索当前出列网页中的信息，并标记此网页已被访问过，进行②。④结束。2024/11/9438.7队列与网络爬虫SaveHtml.java例子6Example8_6.java例子6的中的SaveHtml类的saveHtml(Stringsource)方法负责将网页保存为本地的文本文件。例子6的中的FindData类的findData(Filefile,Stringregex)方法，根据正则表达式regex从本地文件file中挖掘数据，