队列¶
引入¶
什么是队列呢？我们可以联想到去游乐园玩项目需要排的队，或者去饭堂打饭排队。这个排队每一次总会从后面新来几个人，然后又从前面走了几个人，而如果你想玩某个项目，你只能排在队尾，然后等待前面的人玩完，你才能玩。
队列的在 OI 中与栈一样、也是非常重要的一种数据结构，特性是先进先出（first in first out, FIFO）。
数组模拟¶
我们在做题的时候，一般会使用数组来模拟队列。\(h\) 是队头位置，\(t\) 是队尾位置，那么 \([h,t]\) 就是当前队列里面的所有元素。
注意
使用数组模拟队列的时候，不管数组是从 \(0\) 开始还是从 \(1\) 开始，\(h\) 必须等于 \(t+1\)，这样子队列才是空的。（除非你的区间是左闭右开）
血的教训
数组 \(a\) 的长度一定要大于或等于进入队列的元素的数量，而不是当前队列的最大长度。如果是进入元素数量很多，但是实际上当前队列的最大长度并不多的话，可以参考后面的“循环队列”来进行优化。
template <class Ty>
class Queue {
protected:
int *a = new int[1 << 21], h = 1, t = 0;
public:
Queue() = default;
};
我们只需要现将位指针右移，然后将元素放入 \(a_t\) 中，一个插入操作就完成了。如果是弹出队头的话，那么只需要将 \(h\) 加一就行了。由于当前队列的区间是 \([h,t]\)，那么队列的大小就是 \(t-h+1\) 了。
void push(const Ty &x) {
a[++t] = x;
}
void pop() {
h++;
}
constexpr size_t size() {
return h - t + 1;
}
然后和栈差不多，我们只需要返回 \(a_h\) 就可以获取到队头元素。
Ty &front() {
return a[h];
}
这就是队列的数组实现。
循环队列¶
我们发现，数组模拟队列的时候，如果当前队列的最大长度很小，那么数组的空间利用率就会很低。因此，我们可以使用循环队列来优化这个问题。循环队列的原理和数组模拟队列差不多，我们只需要将第 \(n\)（\(n\) 为元素数量）个位置的下一个位置看做 \(0\)（或 \(1\)，一般为 \(0\)），就可以解决这个问题。
因此，队列的空间得到了极大的优化。
链表模拟¶
跟栈一样，队列也可以用链表来模拟。不同的是，在弹出队头的时候，我们直接对队头进行 delete 操作，这样子就可以模拟出循环队列的效果，并且不需要预先开数组来存储。
需要使用双向链表实现，实现较为复杂，在 OI 当中一般不作使用。
STL 实现¶
在标准头文件 stack 当中，STL 已经帮我们实现了队列。我们只需要引入头文件 #include <queue> 就可以直接使用了。std::stack 的具体使用可以看语言基础板块。