队列

liweiwei1419 ... 2021-12-26 About 15 min

# 队列

队列 Queue 主要处理的问题是广度优先遍历(不论是针对树还是图,可以把树理解为图的特殊形式)。

这一节,我们对栈和数据结构这两种看似行为不同,但事实上都是对数据的缓存,只是根据需要的时机不同而设计的两种数据结构和它们的应用和扩展,做了简单的介绍。后面的几节,我们来看一下,栈和队列的具体应用,以加深我们对它们的理解。

队列就和我们平常坐公交、地铁、买票、购物的排队一样,处理数据的规则是先到先得。

队列是规定了我只在线性结构的一侧放入元素,在另一侧取出元素的抽象数据类型。

在这一章节,我将会向大家介绍一些「栈」和「队列」的应用,希望通过这些应用能够加深大家对「栈」和「队列」这两种数据结构的认识。

我们为什么要做这种限制呢?如果没有这些限制岂不是更好吗。

+ 首先,在我们的应用中的的确确有这种只需要用到一部分操作的场景,刚刚说的排队,就是先到先得;我们做研究,解决问题的顺序,在解决一个问题的过程中,会遇到新的问题,新的问题解决了,原来的问题才能解决,即是后遇到的问题先解决。我们使用这些看起来受限的数据结构的的确确能够解决很多问题;

+ 使用这些专门的数据结构,也能避免我们在编码的过程中使用了一些不安全的操作,这也是软件设计领域高内聚、低耦合的体现。即使用一种可能看似「多功能」的数据结构,有可能会带来一些不安全的操作。

如,各种高级**程序设计语言中都有「整数」类型,尽管它们在不同处理器上实现的方法不同,但对程序员而言是「相同的」,即数学特性相同。从「数学抽象」的角度看,可称它为一个「抽象数据类型**」。 [1]

抽象数据类型的特征是将使用与实现分离,从而实行**封装和隐藏信息。抽象数据类型通过一种特定的数据结构在程序的某个部分得以实现,只关心在这个数据类型**上的操作,而不关心数据结构具体实现。

这是一个名词,类似与我们说 API,请大家不要在理解这个概念上纠结。

# 队列的抽象数据类型

#

# 第 8.6 节 队列:后进先出的数据结构


# 队列简介

1、一般意义上的队列,就像我们每天上班、买东西,在食堂打饭排队一样,是一种元素「先进先出」的数据结构;

2、与栈不用的是,我通常将线性表横着摆放来展示和理解队列这个数据结构;

3、队列在计算机领域也是有着广泛的应用:

(1)在很多任务中,其实都需要遵守「先到先得」这个规则;我们平常访问网页的时候,如果同一时间有大量的用户同时向一个页面发送请求,服务器无法一下子处理完所有的请求,就会把一些来不及处理的任务放在一个队列里,一旦服务器系统里的额某个处理器(或者处理线程)完成了手头的任务,它就会到队列里取走一个未处理的请求,通常是采区先来先服务的原则;

(2)在处理树结构或者图结构结构的一些问题中,队列发挥着非常重要的作用,这种使用队列的算法叫做广度优先遍历,这一点我们将在以后的课程中向大家介绍。

4、下面我们来介绍队列的实现,同样是这些实现,对于出队和入队操作,都要是 O(1)O(1) 的。

(1)使用链表实现队列

根据我们刚才对「栈」的链表实现的讨论,可知,最普通的单链表其实是只支持在头部添加和删除元素的。那么在尾部,我们想一想哪种操作更方便一些,显然是添加结点,因为如果要在单链表的尾部删除结点,我们要找到单链表的尾部结点的上一个引用,然后切断这个引用。而如果是添加结点,我们只需要把新创建的结点添加到当前链表的尾部即可。

因此,带了虚拟头结点和尾指针的单链表实现的队列的队头是虚拟头结点的下一个结点,尾部就是尾指针所指向的那个结点。

因此,队列的链表实现可以是单链表,但是这个单链表除了虚拟头结点这个常用的技巧以外,还需要维护一个指向链表尾部的指针。

接下来,我们来看数组能不能够高效实现队列。

(2)使用数组实现队列

通过刚才对数组实现的栈的讨论,我们知道,在头部删除元素并不高效,但事实上我们也可以使用数组中在尾部删除一个元素的策略,我们使用一个指针变量 head 指向数组的头部,我们从数组中删除一个元素,即是把这个指向头部的元素的指针 head 后移一位即可。

因此队列的数组实现中,数组的头部就是队列的头部,数组的尾部就是队列的尾部。

于是,在入队和出队的过程中,事实上,这个数组里元素的使用情况就像是一个滑动窗口,队列中的有效区域在数组中从前向后移动。这个过程,很有意思,相信大家也不难明白。

但是我说到这里,相信大家很快就能看到一个这种设计上的问题,那就是在出队入队的过程中,队列有效区域之前的空间被我们浪费了。

事实上,这个问题很容易解决,我们只要让这个滑动窗口循环滚动起来就好。因为这个滑动窗口它的有效元素的区域的移动方向是固定的,因此,在移动的过程中,只要指针变量的范围超过了数组的索引的有效范围,我们就让它回到数组的开头,在编码上,我们就对这个索引的值取一个数组长度的模即可。

那么与此同时,就带来一个问题。当队列满的时候,就是 headrear 指针重合的时候,而 headrear 重合我们一般又作为队列为空的标志。

为了解决这个问题,我们通常浪费一个数组的空间,当 head 指针从后面快要赶上 rear 指针,它们只差一个数组单位长度的时候,我们就判定这个队列已经满了。

此时当队列满的时候,我们可以采取一定的策略。

(1)像动态数组一样扩容;

(2)当新来的元素在一个备用数组里等待;

(3)或者抛弃新来的元素。

根据业务的需求,我们选择合适的策略。

这样通过有效元素在数组上「循环移动」来实现的队列,我们称之为「循环数组」。对于我上面说到的 headrear 指针变量的设计和移动、对于队列为空和队列满的判别条件,在实现上有一些细节。我们会通过解决「力扣」上第 号问题,向大家做具体的介绍,大家也可以自己尝试做一下这一题,必要的时候在纸上写写画画,相信是一个很不错的编程练习。

这里说一个题外话,使用 Java 的同学,Java 的库函数里已经提供了很多栈和数组的实现,建议大家从它的底层实现来理解这些实现的工作原理和使用场景。通常,它的底层是如何实现的,就反应在这个类的类名上,从它的底层实现,你就能更好地理解它对于队列满的时候的处理策略。

例如:

ArrayBlockingQueue:由数组支持的有界队列

从它的名字,我们就可以看出,这个队列它的底层结构是一个数组,因为数组扩容有性能消耗,因此它不支持扩容,当队列慢的时候,它的处理策略是阻塞。进而理解这个类适合应用的场景。

下面,我们介绍队列的两个扩展。

# 队列的扩展

在一些场合中,我们希望,在队列的两端都可以进行出队和入队操作,这样一种更灵活的数据结构,计算机科学家专门给它起了一个特殊的名字(Deque),称之为双端队列,发音为「迪克」。

1、双端队列

  • 双端队列是可以在线性表的两端都支持 O(1)O(1) 操作的队列。(说双端是只在两端均可高效操作)
  • 可以使用数组实现,也可以用链表实现。用数组实现的双端队列事实上用我们刚刚介绍的循环数组的技巧就可以实现。而链表实现双端队列也不难,使用双链表就可以完成。「力扣」第 641 题:设计循环双端队列 (opens new window) 就要求我们通过数组实现一个双端队列,大家也可以尝试自己实现一下。

在 Java 、C++ 和 Python 语言中,都提供了 Deque 的实现,大家可以查阅这些语言的 API 熟悉对它们的操作。

2、优先队列

如果我们希望出队的时候,不是按照时间顺序,而是按照我们认为指定的顺序,例如整个队列里的最大的元素先出队,或者最小的元素先出队,支持这种高效操作的数据结构我们称之为优先队列,优先队列也是在计算机领域非常重要的一种数据结构。我们将会在下一章专门花一个章节介绍。

好了,这就是这一节的内容。这一节,我们对栈和数据结构这两种看似行为不同,但事实上都是对数据的缓存,只是根据需要的时机不同而设计的两种数据结构和它们的应用和扩展,做了简单的介绍。后面的几节,我们来看一下,栈和队列的具体应用,以加深我们对它们的理解。


这就是这一节的内容,在这一节我们对队列的应用和基本实现做了一个简单的介绍,下面几节我们就来看几个和队列相关的问题,以加深我们对队列问题的认识。

队列就和我们平常坐公交、地铁、买票、购物的排队一样,处理数据的规则是先到先得。

队列是规定了我只在线性结构的一侧放入元素,在另一侧取出元素的抽象数据类型。

我们为什么要做这种限制呢?如果没有这些限制岂不是更好吗。

  • 首先,在我们的应用中的的确确有这种只需要用到一部分操作的场景,刚刚说的排队,就是先到先得;我们做研究,解决问题的顺序,在解决一个问题的过程中,会遇到新的问题,新的问题解决了,原来的问题才能解决,即是后遇到的问题先解决。我们使用这些看起来受限的数据结构的的确确能够解决很多问题;
  • 使用这些专门的数据结构,也能避免我们在编码的过程中使用了一些不安全的操作,这也是软件设计领域高内聚、低耦合的体现。即使用一种可能看似「多功能」的数据结构,有可能会带来一些不安全的操作。

如,各种高级程序设计语言 (opens new window)中都有「整数」类型,尽管它们在不同处理器 (opens new window)上实现的方法不同,但对程序员而言是「相同的」,即数学特性相同。从「数学抽象」的角度看,可称它为一个「抽象数据类型 (opens new window)」。 [1]

抽象数据类型的特征是将使用与实现分离,从而实行封装 (opens new window)和隐藏信息。抽象数据类型通过一种特定的数据结构在程序的某个部分得以实现,只关心在这个数据类型 (opens new window)上的操作,而不关心数据结构具体实现。

这是一个名词,类似与我们说 API,请大家不要在理解这个概念上纠结。

![image-20200803113158602](/Users/liwei/Library/Application Support/typora-user-images/image-20200803113158602.png)

通过刚才对数组实现的栈的讨论,我们知道,在头部删除元素并不高效,但事实上我们也可以使用数组中在尾部删除一个元素的策略,我们使用一个指针变量 head 指向数组的头部,我们从数组中删除一个元素,即是把这个指向头部的元素的指针 head 后移一位即可。

因此队列的数组实现中,数组的头部就是队列的头部,数组的尾部就是队列的尾部。

这个过程,很有意思,相信大家也不难明白。

但是我说到这里,相信大家很快就能看到一个这种设计上的问题,那就是在出队入队的过程中,队列有效区域之前的空间被我们浪费了。

事实上,这个问题很容易解决,我们只要让这个滑动窗口循环滚动起来就好。因为这个滑动窗口它的有效元素的区域的移动方向是固定的,因此,在移动的过程中,只要指针变量的范围超过了数组的索引的有效范围,我们就让它回到数组的开头,在编码上,我们就对这个索引的值取一个数组长度的模即可。

那么与此同时,就带来一个问题。当队列满的时候,就是 headrear 指针重合的时候,而 headrear 重合我们一般又作为队列为空的标志。

为了解决这个问题,我们通常浪费一个数组的空间,当 head 指针从后面快要赶上 rear 指针,它们只差一个数组单位长度的时候,我们就判定这个队列已经满了。

此时当队列满的时候,我们可以采取一定的策略。

(1)像动态数组一样扩容;

(2)当新来的元素在一个备用数组里等待;

(3)或者抛弃新来的元素。

根据业务的需求,我们选择合适的策略。

这样通过有效元素在数组上「循环移动」来实现的队列,我们称之为「循环数组」。对于我上面说到的 headrear 指针变量的设计和移动、对于队列为空和队列满的判别条件,在实现上有一些细节。我们会通过解决「力扣」上第 号问题,向大家做具体的介绍,大家也可以自己尝试做一下这一题,必要的时候在纸上写写画画,相信是一个很不错的编程练习。

主要理解双向链表。因为主要在头尾两端进行操作,O(1)O(1) 复杂度。

# 双端队列(Double Ended Queue)

1、能在头尾两端添加、删除队列的数据结构

# 循环队列

容量不够的时候动态扩容

循环双端队列

Last update: December 26, 2021 18:30
Contributors: liweiwei1419