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

第8章队列与ArrayDeque类2024/11/918.1队列的特点2024/11/92队列擅长在线性表的头、尾两端实施删除和添加操作，甚至可以把线性表实现成只在头、尾两端操作，所以人们也称队列是受限的线性表。入列时，最先进入的节点在队头，最后进入的节点在队尾。出列时，从队列的头开始删除节点，最后一个删除的节点是队尾的节点。队列是一种先进先出的数据结构，简称FIFO（FirstInFirstout）8.1队列的特点2024/11/93头节点（队头）在左边、尾节点（队尾）在右边。8.2队列的创建与独特方法2024/11/94ArrayDeque<E>泛型类继承了Deque泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了Deque泛型接口中的抽象方法。ArrayDeque<E>采用数组方式实现队列这种数据结构，其实例属于顺序表，即节点的逻辑结构是线性结构，节点的存储结构是顺序存储。ArrayDeque<E>泛型类的实例的节点就是对象，后面的叙述不再说节点里的对象。8.2队列的创建与独特方法2024/11/95队列由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayDeque<E>泛型类所实现。2024/11/968.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/978.2队列的创建与独特方法●独特的方法例子1中的主类Example8_1使用了队列的独特方法。Example8_1.java例子1

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

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

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

注不可以一行、一行的排雷，这样做显然没有体现广度优先。8.7队列与网络爬虫2024/11/918一个网站往往维护着很多网页，这些网页之间通过超链接实现彼此的链接。网络爬虫的意思就是从网站的某个网页开始，通过网页之间的超链接、遍历该网站的所有网页来寻找满足要求的数据或信息。网络爬虫，一般都采用广度搜索。8.7队列与网络爬虫2024/11/919广度搜索算法中使用队列，就可以实现对网站的广度搜索，算法描述如下：①将开始的网页点入列，进行②②检查队列是否是空列，如果为空（所有网页就都访问过了）进行④,否则进行③③队列进行出列操作，将出列的网页中的所有没有被访问过的超链接入列，然后按着需求检索当前出列网页中的信息，并标记此网页已被访问过，进行②。④结束。2024/11/9208.7队列与网络爬虫SaveHtml.java例子6Example8_6.java例子6的中的SaveHtml类的saveHtml(Stringsource)方法负责将网页保存为本地的文本文件。例子6的中的FindData类的findData(Filefile,Stringregex)方法，根据正则表达式regex从本地文件file中挖掘数据，比如挖掘网页中的所有超链接，所有gif图像的名字等。例子6的中的WeBSpider类的spider(Stringaddress,Stringdata)方法使用广度搜索算法搜索地址是address的网站上的多个网页中，匹配正则表达式data的数据，即WeBSpider类的spider(Stringaddress,Stringdata,intmax)方法就是所谓的网络爬虫。FindData.javaWeBSpider.java2024/11/9218.7队列与网络爬虫例子6的中的主类Example8_6使用WeBSpider类的spider(Stringaddress,Stringdata,intmax)方法爬取百度网站上20个网页上的gif图像的名字和含有百度一词的句子.8.8队列与排队2024/11/922假设一个营业厅有2个服务窗口，低峰期间有一个窗口营业，高峰期间有2个窗口营业，每个窗口为一位顾客办理业务的耗时不尽相同。程序模拟营业厅服务若干顾客，观察两个窗口分别服务了多少顾客，停止营业后，看看还有多少顾客未能办理业务。2024/11/9238.8队列与排队ServiceWindow.java例子7Example8_7.jav