《画解数据结构》|??《画解数据结构》九张动图，画解队列?? 《画解数据结构》|C

本文已收录于专栏 《画解数据结构》
零、前言

【《画解数据结构》|??《画解数据结构》九张动图，画解队列??】??「数据结构」 和 「算法」 是密不可分的，两者往往是「相辅相成」的存在，所以，在学习 「数据结构」 的过程中，不免会遇到各种「算法」。
??到底是先学数据结构，还是先学算法，我认为不必纠结这个问题，一定是一起学的。
??数据结构常用的操作一般为：「增」「删」「改」「查」。基本上所有的数据结构都是围绕这几个操作进行展开的。
??那么这篇文章，作者将用 「九张动图」 来阐述一种 「先进先出」 的数据结构

「队列」

文章图片

饭不食，水不饮，题必须刷
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
LeetCode 太难？先看简单题！ 《C语言入门100例》
数据结构难？不存在的！ 《画解数据结构》
闭关刷 LeetCode，剑指大厂Offer！ 《LeetCode 刷题指引》
LeetCode 太简单？算法学起来！ 《夜深人静写算法》
?? 队列可以用 顺序表 实现，也可以用链表实现，浓缩为以下三张图：
队列操作三部曲
队列的链表实现
队列的顺序表实现
??看不懂没有关系，我会把它拆开来一个一个讲，首先来看一下今天要学习的内容目录。

文章目录

零、前言
一、概念
- 1、队列的定义
- 2、队首
- 3、队尾
二、接口
- 1、可写接口
- - 1）数据入队
  - 2）数据出队
  - 3）清空队列
- 2、只读接口
- - 1）获取队首数据
  - 2）获取队列元素个数
  - 3）队列的判空
三、队列的顺序表实现
- 1、数据结构定义
- 2、入队
- - 1、动画演示
  - 2、源码详解
- 3、出队
- - 1、动画演示
  - 2、源码详解
- 4、清空队列
- - 1、动画演示
  - 2、源码详解
- 5、只读接口
- 6、队列的顺序表实现源码
四、队列的链表实现
- 1、数据结构定义
- 2、入队
- - 1、动画演示
  - 2、源码详解
- 3、出队
- - 1、动画演示
  - 2、源码详解
- 4、清空队列
- - 1、动画演示
  - 2、源码详解
- 5、只读接口
- 6、队列的链表实现源码
五、两种实现的优缺点
- 1、顺序表实现
- 2、链表实现
六、队列的入门
- 1、滑动窗口
- 2、广度优先搜索
七、队列的进阶
- 1、辅助队列
- 2、单调队列

一、概念 1、队列的定义 ??队列是仅限在一端进行插入，另一端进行删除的线性表。
??队列又被称为先进先出（First In First Out）的线性表，简称 FIFO 。

文章图片

2、队首 ??允许进行元素删除的一端称为队首。如下图所示：

文章图片

3、队尾 ??允许进行元素插入的一端称为队尾。如下图所示：

文章图片

二、接口 1、可写接口 1）数据入队
??队列的插入操作，叫做入队。它是将数据元素从队尾进行插入的过程，如图所示，表示的是插入两个数据（绿色和蓝色）的过程：

2）数据出队
??队列的删除操作，叫做出队。它是将队首元素进行删除的过程，如图所示，表示的是依次删除两个数据（红色和橙色）的过程：

3）清空队列
??队列的清空操作，就是一直出队，直到队列为空的过程，当队首和队尾重合时，就代表队尾为空了，如图所示：

2、只读接口 1）获取队首数据
??对于一个队列来说只能获取队首数据，一般不支持获取其它数据。
2）获取队列元素个数
??队列元素个数一般用一个额外变量存储，入队时加一，出队时减一。这样获取队列元素的时候就不需要遍历整个队列。通过O ( 1 ) O(1) O(1) 的时间复杂度获取队列元素个数。
3）队列的判空
??当队列元素个数为零时，就是一个空队，空队不允许出队操作。
三、队列的顺序表实现 1、数据结构定义

对于顺序表，在 C语言中表现为数组，在进行队列的定义之前，我们需要考虑以下几个点：
??1）队列数据的存储方式，以及队列数据的数据类型；
??2）队列的大小；
??3）队首指针；
??4）队尾指针；

我们可以定义一个队列的结构体，C语言实现如下所示：

#define DataType int// (1) #define maxn 100005// (2)struct Queue { // (3) DataType data[maxn]; // (4) int head, tail; // (5) };

( 1 ) (1) (1) 用DataType这个宏定义来统一代表队列中数据的类型，这里将它定义为整型，根据需要可以定义成其它类型，例如浮点型、字符型、结构体等等；
( 2 ) (2) (2) maxn代表我们定义的队列的最大元素个数；
( 3 ) (3) (3) Queue就是我们接下来会用到的队列结构体；
( 4 ) (4) (4) DataType data[maxn]作为队列元素的存储方式，即数组，数据类型为DataType，可以自行定制；
( 5 ) (5) (5) head即队首指针，tail即队尾指针，head == tail代表空队；当队列非空时，data[head]代表了队首元素（而队尾元素是不需要关心的）；

2、入队 1、动画演示

文章图片

??如图所示，绿色元素 为新插入队尾的数据，执行完毕以后，队尾指针加一，队首指针不变。需要注意的是，顺序表实现时，队尾指针指向的位置是没有数据的，具体来看下代码实现。

2、源码详解

入队操作，算上函数参数列表，总共也才几句话，代码实现如下：

void QueueEnqueue(struct Queue *que, DataType dt) { // (1) que->data[ que->tail ] = dt; // (2) que->tail = que->tail + 1; // (3) }

( 1 ) (1) (1) que是一个指向队列对象的指针，由于这个接口会修改队列对象的成员变量，所以这里必须传指针，否则，就会导致函数执行完毕，传参对象没有任何改变；
( 2 ) (2) (2) 将传参的元素入队；
( 3 ) (3) (3) 将队尾指针自增 1；
注意，这个接口在调用前，需要保证队尾指针小于队列元素最大个数，即que->tail < maxn，
如果 C语言写的熟练，我们可以把( 2 ) (2) (2) 和( 3 ) (3) (3) 合成一句话，如下：

void QueueEnqueue(struct Queue *que, DataType dt) {que->data[ que->tail++ ] = dt; }

que->tail++表达式的值是自增前的值，并且自身进行了一次自增。

3、出队 1、动画演示

文章图片

??如图所示，橙色元素 为原先的队首元素，执行出队操作以后，黃色元素 成为当前的队首元素，执行完毕以后，队首指针加一。由于是顺序表实现，队首元素前面的那些元素已经变成无效的了，具体来看下代码实现。

2、源码详解

出队操作，只需要简单的改变，将队首指针加一即可，代码实现如下：

void QueueDequeue(struct Queue* que) {++que->head; }

4、清空队列 1、动画演示

文章图片

??如图所示，对于数组来说，清空队列的操作只需要将队首指针和队尾指针都置零即可，数据不需要清理，下次继续入队的时候会将之前的内存重复利用。

2、源码详解

清空队列的操作只需要将队首指针和队尾指针都归零即可，代码实现如下：

void QueueClear(struct Queue* que) {que->head = que->tail = 0; }

5、只读接口

只读接口包含：获取队首元素、获取队列大小、队列的判空，实现如下：

DataType QueueGetFront(struct Queue* que) {return que->data[ que->head ]; // (1) } int QueueGetSize(struct Queue* que) {return que->tail - que->head; // (2) } int QueueIsEmpty(struct Queue* que) {return !QueueGetSize(que); // (3) }

( 1 ) (1) (1) que->head代表了队首指针，即队首下标，所以真正的队首元素是 que->data[ que->head ]；
( 2 ) (2) (2) 因为只有在入队的时候，队尾指针加一；出队的时候，队首指针加一；所以队列元素个数就是两者的差值；
( 3 ) (3) (3) 当队列元素个数为零时，队列为空。

6、队列的顺序表实现源码

队列的顺序表实现的源码如下：

/**************************** 顺序表实现队列 ****************************/ #define DataType int #define maxn 100005struct Queue {DataType data[maxn]; int head, tail; }; void QueueClear(struct Queue* que) {que->head = que->tail = 0; } void QueueEnqueue(struct Queue *que, DataType dt) {que->data[ que->tail++ ] = dt; } void QueueDequeue(struct Queue* que) {++que->head; }DataType QueueGetFront(struct Queue* que) {return que->data[ que->head ]; } int QueueGetSize(struct Queue* que) {return que->tail - que->head; } int QueueIsEmpty(struct Queue* que) {return !QueueGetSize(que); }/**************************** 顺序表实现队列 ****************************/

四、队列的链表实现 1、数据结构定义

对于链表，在进行队列的定义之前，我们需要考虑以下几个点：
??1）队列数据的存储方式，以及队列数据的数据类型；
??2）队列的大小；
??3）队首指针；
??4）队尾指针；

我们可以定义一个队列的结构体，C语言实现如下所示：

typedef int DataType; // (1) struct QueueNode; // (2) struct QueueNode { // (3) DataType data; struct QueueNode *next; }; struct Queue {struct QueueNode *head, *tail; // (4) int size; // (5) };

( 1 ) (1) (1) 队列结点元素的数据域，这里定义为整型；
( 2 ) (2) (2) struct QueueNode;是对链表结点的声明；
( 3 ) (3) (3) 定义链表结点，其中DataType data代表数据域；struct QueueNode *next代表指针域；
( 4 ) (4) (4) head作为队首指针，tail作为队尾指针；
( 5 ) (5) (5) 由于求链表长度的算法时间复杂度是O ( n ) O(n) O(n) 的，所以我们需要记录一个size来代表现在队列中有多少元素。每次入队时size自增，出队时size自减。这样在询问队列的大小的时候，就可以通过O ( 1 ) O(1) O(1) 的时间复杂度。

2、入队 1、动画演示

文章图片

??如图所示，head 为队首元素，tail 为队尾元素，vtx 为当前需要入队的元素，即图中的 橙色结点。入队操作完成后，队尾元素变为 vtx，即图中 绿色结点。

2、源码详解

入队操作，其实就是类似尾插法，往链表尾部插入一个新的结点，代码实现如下：

void QueueEnqueue(struct Queue *que, DataType dt) {struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) ); insertNode->data = https://www.it610.com/article/dt; // (1) insertNode->next = NULL; if(que->tail) { // (2) que->tail->next = insertNode; que->tail = insertNode; }else {que->head = que->tail = insertNode; // (3) } ++que->size; // (4) }

( 1 ) (1) (1) 利用malloc生成一个链表结点insertNode，并且填充数据域和指针域；
( 2 ) (2) (2) 如果当前队尾不为空，则将insertNode作为队尾的后继结点，并且更新insertNode作为新的后继结点；
( 3 ) (3) (3) 否则，队首和队尾都为insertNode；
( 4 ) (4) (4) 队列元素加一；

3、出队 1、动画演示

文章图片

??如图所示，head 为队首元素，tail 为队尾元素，temp 为当前需要出队的元素，即图中的 橙色结点。出队操作完成后，队首元素变为之前 head 的后继结点，即图中 绿色结点。

2、源码详解

出队操作，由于链表头结点就是队首，其实就是删除这个链表的头结点的过程。代码实现如下：

void QueueDequeue(struct Queue* que) {struct QueueNode *temp = que->head; // (1) que->head = temp->next; // (2) free(temp); // (3) --que->size; // (4) if(que->size == 0) { // (5) que->tail = NULL; } }

( 1 ) (1) (1) 将队首保存到temp中；
( 2 ) (2) (2) 将队首的后继结点作为新的队首；
( 3 ) (3) (3) 释放之前队首对应的内存；
( 4 ) (4) (4) 队列元素减一；
( 5 ) (5) (5) 当队列元素为空时，别忘了将队尾指针置空；

4、清空队列 1、动画演示

??清空队列可以理解为：不断的出队，直到队列元素个数为零为止。由于链表结点是动态申请的内存，所以在没有其它结点引用时，是需要释放内存的，不像数组那样直接将队首指针和队尾指针置空就行的。

2、源码详解

对于链表而言，清空队列的操作需要删除每个链表结点，代码实现如下：

void QueueClear(struct Queue* que) {while(!QueueIsEmpty(que)) { // (1) QueueDequeue(que); // (2) } }

( 1 ) (1) (1) -( 2 ) (2) (2) 的每次操作其实就是一个出队的过程，如果队列不为空；则进行出队操作，直到队列为空；

5、只读接口

只读接口包含：获取队首元素、获取队列大小、队列的判空，实现如下：

DataType QueueGetFront(struct Queue* que) {return que->head->data; // (1) } int QueueGetSize(struct Queue* que) {return que->size; // (2) } int QueueIsEmpty(struct Queue* que) {return !QueueGetSize(que); // (3) }

( 1 ) (1) (1) que->head作为队首指针，它的数据域 data就是队首元素的值，返回即可；
( 2 ) (2) (2) size记录的是队列元素的个数；
( 3 ) (3) (3) 当队列元素个数为零时，队列为空。

6、队列的链表实现源码

/**************************** 链表实现队列 ****************************/ typedef int DataType; struct QueueNode; struct QueueNode {DataType data; struct QueueNode *next; }; struct Queue {struct QueueNode *head, *tail; int size; }; void QueueEnqueue(struct Queue *que, DataType dt) {struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) ); insertNode->data = https://www.it610.com/article/dt; insertNode->next = NULL; if(que->tail) {que->tail->next = insertNode; que->tail = insertNode; }else {que->head = que->tail = insertNode; } ++que->size; }void QueueDequeue(struct Queue* que) {struct QueueNode *temp = que->head; que->head = temp->next; free(temp); --que->size; if(que->size == 0) {que->tail = NULL; } }DataType QueueGetFront(struct Queue* que) {return que->head->data; } int QueueGetSize(struct Queue* que) {return que->size; } int QueueIsEmpty(struct Queue* que) {return !QueueGetSize(que); } void QueueClear(struct Queue* que) {que->head = que->tail = NULL; que->size = 0; }/**************************** 链表实现队列 ****************************/

五、两种实现的优缺点 1、顺序表实现 ??在利用顺序表实现队列时，入队和出队的常数时间复杂度低，且清空队列操作相比链表实现能做到O ( 1 ) O(1) O(1)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考以下文章：《C/C++ 面试 100 例》（四）vector 扩容策略。
??当然，可以采用循环队列，能够很大程度上避免扩容问题，但是当入队速度大于出队速度时，不免还是会遇到扩容的问题。
2、链表实现 ??在利用链表实现队列时，入队和出队的常数时间复杂度略高，主要是每插入一个队列元素都需要申请空间，每删除一个队列元素都需要释放空间，且清空队列操作是O ( n ) O(n) O(n) 的，直接将队首指针和队尾指针置空会导致内存泄漏。
??好处就是：不需要预先分配空间，且在内存允许范围内，可以一直入队，没有顺序表的限制。当然，链表的实现明显比数组实现要复杂，编码的时候容易出错。
??需要注意的是，本文在讲解过程中，顺序表实现的队尾和链表实现的队尾不是一个概念，顺序表实现的队尾没有实际元素值，而链表实现的则不然，请自行加以区分。
六、队列的入门

好啦，接下来，让我们做几个队列的题目练习一下吧。

1、滑动窗口 LeetCode 933. 最近的请求次数
LeetCode 346. 数据流中的移动平均值
2、广度优先搜索 LeetCode 542. 01 矩阵
LeetCode 994. 腐烂的橘子
LeetCode 116. 填充每个节点的下一个右侧节点指针
七、队列的进阶 1、辅助队列 LeetCode 225. 用队列实现栈
2、单调队列 LeetCode 1696. 跳跃游戏 VI
LeetCode 1438. 绝对差不超过限制的最长连续子数组
LeetCode 239. 滑动窗口最大值
LeetCode1425. 带限制的子序列和

关于 「队列」 的内容到这里就结束了。
如果还有不懂的问题，可以通过 「博客主页」找到作者的「联系方式」 ，线上沟通交流。

有关《画解数据结构》 的源码均开源，链接如下：《画解数据结构》

饭不食，水不饮，题必须刷
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
LeetCode 太难？先看简单题！ 《C语言入门100例》
数据结构难？不存在的！ 《画解数据结构》
闭关刷 LeetCode，剑指大厂Offer！ 《LeetCode 刷题指引》
LeetCode 太简单？算法学起来！ 《夜深人静写算法》