文章目录

1. 队列的定义和基本操作
2. 队列的两种实现方式
- 2.1 顺序队列
- 2.2 链式队列
3. 静态顺序队列
4. 动态链式队列
5. 扩展队列：双端队列
- 5.1 双端队列对序列是否合法的判断
- 5.2 小结

1. 队列的定义和基本操作

1.1 队列的定义

1. 队列：是一种操作受限的线性表，只能在队尾插入元素，在对头删除元素。

2. 特点：
	* 先进先出FIFO(first in first out)

3. 相关术语：
	1. 队头
	2. 队尾
	3. 空队列
	4. 队头元素
	5. 队尾元素

1.2 队列的基本操作

1.3 队列的分类

* 队列的物理实现分类
	1. 顺序结构
		* 静态顺序队列
		* 动态顺序队列
	2. 链式结构
		* 静态链式队列
		* 动态链式队列

1.4 小结

2. 队列的两种实现方式

2.1 顺序队列

在顺序队列中，有两种实现方式：

第一种是队列rear指向队尾元素的下一个位置
第二种是队列rear指向队尾元素。

注意：

这两种方式在队列初始化、添加元素、删除元素时的操作都不一样，特别要注意是那种实现方式。

这两种方式的front都是指向队头元素，是一样的。

2.2 链式队列

在顺序队列中，有两种实现方式：

第一种是带头节点
第二种是不带头节点

注意：注意与顺序队列区分开来。链式队列的rear都是指向队尾元素，因为，队列无法指向队尾元素的下一个位置。

3. 静态顺序队列

* 静态顺序队列按照结构分类
	1. 线性静态顺序队列
	2. 循环静态顺序队列

	* 注意：每种队列都有两种不同的实现方式，即：
		1. 队列rear指向队尾元素的下一个位置
		2. 队列rear指向队尾元素。

3.1 线性静态顺序队列

3.1.1 rear指向队尾元素的下一个位置

3.1.1.1 基本操作

3.1.1.1.1 初始化以及判空操作

front与rear分别指向队列的对头元素和队尾元素的下一个位置，如下图front = 0，rear = 5：

所以，在初始化队列时，是front = rear = 0;:

3.1.1.1.2 添加元素

3.1.1.1.3 删除元素

3.1.1.1.4 查看队头元素

3.1.2 rear指向队尾元素

3.1.2.1 基本操作

3.1.2.1.1 初始化和判空操作

3.1.2.1.2 添加元素

3.1.2.1.3 删除元素

3.1.2.1.4 查看对头元素

3.1.2.1.5 打印队列

3.1.3 小结

1. Q->rear指向队尾元素的下一个位置
	1. 判空条件： Q->front ==  Q->rear 
	2. 判断队列是否已满：MaxSize ==  Q->rear - Q->front 
	3. 得到当前队列的长度：Q->rear - Q->front

2. Q->rear指向队尾元素
	1.  判空条件： Q->front ==  Q->rear +1 
	2. 判断队列是否已满：MaxSize ==  Q->rear - Q->front +1 
	3. 得到当前队列的长度：Q->rear - Q->front +1

3.2 循环静态顺序队列

如果使用上面的非循环队列，会造成很大的空间浪费，即从队头出去的位置都不能再用，如下图所示：

这显然不是我们想要的，那么如何避免？

其实，把队列变成循环队列就可以实现，那么如何将其变为循环队列，主要用到取余操作。当队尾/队首指针指向队空间的最后一个空间时，下一次移动到队首的位置。

其实循环队列面临着一个问题，看下面一张示意图：

我们，发现循环队列面临一个问题，就是队满和队空的判断条件一样。那么显而易见的，我们该做的应该是做一些事情，使得判断队满和队空的判断条件不一样。

那么，如何去做？其实方法有很多，通常有如下几种解决方法：

牺牲一个存储单元
设置size变量
设置tag变量
…

接下来，我们介绍前三种解决方案。

3.2.1 rear指向队尾元素

注意：由于在第二节中实现了rear指向队尾元素的情况，但是这个不太常用，所以，循环静态顺序队列中，我就不展示这种情况了。

3.2.2 rear指向队尾元素的下一个位置(考研中出题常是这种情况)

3.2.2.1 牺牲一个存储单元

当队列牺牲一个存储单元时，队满的条件就变成了 (Q->rear + 1)%MaxSize == Q->front，避免了与判断队空操作的重复。

注意：这种是头指针指向对头元素，尾指针指向对尾元素的下一个位置的情况。如果是其他情况，式子稍微有一定变换，但是思想还是不变。

注意：这里需要取模，主要是因为一种情况与常规情况不统一，就是当 rear=9 与 front 不符合公式rear + 1 == front，所以需要取模。

3.2.2.1.1 基本操作

3.2.2.1.1.1 初始化以及判空操作

3.2.2.1.1.2 添加元素

3.2.2.1.1.3 删除元素

3.2.2.1.1.4 查看元素

3.2.2.1.1.5 得到循环队列的长度

为什么求队列的公式是这个？

因为，当rear > front时，此时队列的长度为rear-front。但当rear < front时，队列长度分为两段，一段是MaxSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + MaxSize。此时，需要一个式子将这两个式子统一，由此得到式子(rear-front + MaxSize) % MaxSize。因此通用的计算队列长度公式为：
(rear—front + MaxSize) % MaxSize

3.2.2.2 使用size

通过一个变量记录队列的长度也可以避免循环队列判空和判满相同的情况，队列为空时size=0, 队列满时size=MaxSize。其示意图如下：

3.2.2.2.1 基本操作

3.2.2.2.1.1 初始化以及判空操作

3.2.2.2.1.2 添加元素

3.2.2.2.1.3 删除元素

3.2.2.2.1.4 查看对头元素

3.2.2.2.1.5 打印整个队列

3.2.2.3 使用tag

如何使用tag避免循环队列判空和判满相同的情况？其实是利用了一个队列的特性：队列满时，最近的一次操作必定为添加元素，而队列为空时，最近的一次操作必定为删除元素。可以用如下一张图描述：

3.2.2.3.1 基本操作

3.2.2.3.1.1 初始化以及判空操作

3.2.2.3.1.2 添加元素

3.2.2.3.1.3 删除元素

3.2.2.3.1.4 查看队头元素

3.2.2.3.1.5 打印队列

3.2.2.4 小结

1. 牺牲一个存储单元
	1. 判空：Q->front == Q->rear
	2. 判满：(Q->rear + 1)%MaxSize == Q->front
2. 使用size标识队列长度
	1. 判空：size == 0
	2. 判满：size == MaxSize
3. 使用tag标识队列最近操作
	* 记0：最近为删除操作；1：最近为添加操作
	1. 判空：Q->front == Q->rear && tag == 0
	2. 判满：Q->front == Q->rear && tag == 1

3.3 小结

4. 动态链式队列

动态链式队列是在链表的基础上进行了限制，只允许在一端插入元素，另一端删除元素。通常，我们取头指针/头节点的一端作为删除元素的一端，链尾作为添加元素的一端。

由此，动态链式队列和队列一样也有两种实现方式：**一是带头节点；二是不带头节点。**如下图所示：

4.1 基本操作

4.1.1 初始化和判空

注意：

带头节点的队列

判空条件为 Q->front == Q->rear

初始化条件 Q->front = Q->rear = 头节点地址或者Q->front->next == NULL

不带头节点的队列

初始化条件：Q->front = Q->rear = NULL

判空条件: Q->front == NULL

4.1.2 添加元素

注意：

不带头节点的队列，在添加元素时，应该分两种情况。第一种，添加该元素作为第一个节点。第二种，添加该元素作为非第一个节点。

由于链式存储是链式的存放数据，所以只要内存空间够，就能一直开辟，不需要考虑队列满的情况。

4.1.3 删除元素

4.1.4 查看队首元素

4.2 小结

5. 扩展队列：双端队列

5.1 双端队列对序列是否合法的判断

* 双端队列
	* 分类
		1. 双端队列
		2. 输入受限的双端队列
		3. 输出受限的双端队列

各种双端队列的示意图如下：

常见的考点是，判断输出序列的合法性：

输出受限的双端队列：

输入受限的双端队列：

5.2 小结

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84622.html

数据结构4-队列知识点大全，干货满满(C语言)