一、概念
1、队列的定义
队列是仅限在一端进行插入，另一端进行删除的线性表。
队列又被称为先进先出（First In First Out） 的线性表，简称 FIFO 。
2、队首
允许进行元素删除的一端称为队首
3、队尾
允许进行元素插入的一端称为 队尾
二、接口
1、可写接口
（1）数据入队
队列的插入操作，叫做 入队。它是将 数据元素 从 队尾 进行插入的过程
（2）数据出队
队列的删除操作，叫做 出队。它是将 队首 元素进行删除的过程
（3）清空队列
队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 重合时，就代表队尾为空了
2、只读接口
（1）获取队首数据
对于一个队列来说只能获取 队首 数据，一般不支持获取 其它数据。
（2）获取队列元素个数
队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一
（3）队列的判空
当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作
三、队列的顺序表实现
1、结构体
struct Queue { // 队列结构体
DataType data[maxn]; // 队列存储方式，数组
int head, tail; // 队首，队尾指针，head == tail代表空队
};2、入队
void QueueEnqueue(struct Queue *que, DataType dt) {
que->data[ que->tail ] = dt; // 将传参的元素入队
que->tail = que->tail + 1; // 队尾指针加一
}可以写成下面这样
void QueueEnqueue(struct Queue *que, DataType dt) {
que->data[ que->tail++ ] = dt;
}3、出队
void QueueDequeue(struct Queue* que) {
++que->head;//队首指针加一
}4、清空队列
清空队列的操作只需要将 队首指针 和 队尾指针 都归零即可
void QueueClear(struct Queue* que) {
que->head = que->tail = 0;
}5、只读接口
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); // 判空
}6、队列的顺序表实现的源码
#define DataType int
#define maxn 100005
struct 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、结构体
typedef int DataType;
struct QueueNode;
struct QueueNode { // 结点
DataType data;
struct QueueNode *next;
};
struct Queue {
struct QueueNode *head, *tail; // 队首、队尾指针
int size; // 队列元素个数
};2、入队
链表入队类似尾插法
void QueueEnqueue(struct Queue *que, DataType dt) {
struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );
insertNode->data = dt; // 给入队的元素赋值
insertNode->next = NULL;
if(que->tail) { // 不为空
que->tail->next = insertNode;
que->tail = insertNode;
}else {
que->head = que->tail = insertNode; // 为空直接首队尾指针指向新入队的元素
}
++que->size; // 元素个数加一
}3、出队
出队 操作，由于链表头结点就是 队首，其实就是删除这个链表的头结点的过程
void QueueDequeue(struct Queue* que) {
struct QueueNode *temp = que->head; // 将队首保存到temp
que->head = temp->next; // 队首指向temp的下一个结点，也就是队首的下一个结点
free(temp); // 释放temp
--que->size; // 长度减一
if(que->size == 0) { // 如果长度为0，队尾置空
que->tail = NULL;
}
}4、清空队列
对于链表而言，清空队列 的操作需要删除每个链表结点
void QueueClear(struct Queue* que) {
while(!QueueIsEmpty(que)) { // 队列不为空
QueueDequeue(que); // 出队
}
}5、只读接口
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); // 是否为空
}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 = 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),
不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容
2、链表
入队 和 出队 的常数时间复杂度略高，主要是每插入一个队列元素都需要申请空间，每删除一个队列元素都需要释放空间，且 清空队列 操作是 O(n)，直接将 队首指针 和 队尾指针 置空会导致内存泄漏
好处就是：不需要预先分配空间，且在内存允许范围内，可以一直 入队
六、队列的入门
1、滑动窗口
LeetCode933最近的请求次数：https://leetcode.cn/problems/number-of-recent-calls/
2、广度优先搜索
LeetCode542.01矩阵：https://leetcode.cn/problems/01-matrix/
LeetCode994腐烂的橘子：https://leetcode.cn/problems/rotting-oranges/
七、队列的进阶
1、辅助队列
LeetCode225用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/
2、单调队列
LeetCode 1696. 跳跃游戏 VIhttps://leetcode.cn/problems/jump-game-vi/
LeetCode 1438. 绝对差不超过限制的最长连续子数组：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
LeetCode 239. 滑动窗口最大值：https://leetcode.cn/problems/sliding-window-maximum/