Solves

队列

队列是一种先进先出（FIFO）的线性数据结构。它允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作。即队列的两种基本操作：

入队（push）：将一个元素放入队列的尾部。
出队（pop）：从队列的头部删除一个元素。

队列的实现

队列可以使用数组模拟：

cpp

int q[MAX_SIZE]; // 队列数组
int head = 0, tail = -1; // 队头指针和队尾指针

q[++tail] = x; // 入队
head++; // 出队
q[head] // 队头元素
q[tail] // 队尾元素
head <= tail // 队列不为空

双栈模拟队列

这种方法是使用两个栈 $F, S$ 来模拟队列。其中 $F$ 栈表示队尾， $S$ 栈表示队头。

入队（push）：将元素插入到栈 $F$ 中。
出队（pop）：如果栈 $S$ 为空，则将栈 $F$ 中的所有元素弹出到栈 $S$ 中，然后弹出栈 $S$ 的栈顶元素，否则直接弹出栈 $S$ 的栈顶元素。

STL中的队列：

cpp

#include <queue>
queue<int> q; // 队列

q.push(x); // 入队
q.pop(); // 出队
q.front(); // 队头元素
q.back(); // 队尾元素
q.empty(); // 队列是否为空
q.size(); // 队列大小

特殊的队列

双端队列

双端队列（deque）是一种允许在两端进行插入和删除操作的队列。相当于结合了栈与队列的功能。

双端队列支持以下四个操作：

push_front(x)：在队头插入元素 x。
push_back(x)：在队尾插入元素 x。
pop_front()：删除队头元素。
pop_back()：删除队尾元素。

STL中的双端队列：

cpp

#include <deque>
deque<int> dq; // 双端队列

dq.push_front(x); // 入队
dq.push_back(x); // 入队
dq.pop_front(); // 出队
dq.pop_back(); // 出队
dq.insert(it, x); // 插入元素 x 到迭代器 it 处
dq.erase(it); // 删除迭代器 it 处的元素
dq.front(); // 队头元素
dq.back(); // 队尾元素
dq.empty(); // 队列是否为空
dq.size(); // 队列大小

循环队列

数组模拟队列时存在一个问题：随着时间的推移，整个队列会向着数组的尾部移动，一旦到达数组的末端，即使数组的前端还有空闲位置，也没办法利用这个空间了。

循环队列（circular queue）是一种解决这个问题的队列。它是一种特殊的队列，它的容量是有限的，当队尾到达数组的末端时，它又回到数组的前端，形成一个循环。

循环队列的实现：

cpp

int q[MAX_SIZE]; // 队列数组
int head = 0, tail = 0; // 队头指针和队尾指针

// 入队
q[tail++] = x;
if (tail == MAX_SIZE) tail = 0;

// 出队
head++;
if (head == MAX_SIZE) head = 0;

q[head] // 队头元素
q[tail] // 队尾元素

head != tail // 队列不为空

队列 ​

队列的实现 ​

特殊的队列 ​

双端队列 ​

循环队列 ​

队列

队列的实现

特殊的队列

双端队列

循环队列