队列

名称

队列(queue)是一种先进先出(FIFO, first in first out)的数据结构，这是一种非常基础的数据结构，在很多地方，尤其是BFS和单调队列中有广泛的应用。

可以使用C++ STL中的queue实现
https://zh.cppreference.com/w/cpp/container/queue
也可以自己模拟

通常用一个数组和两个指针模拟一个队列，数组用于存储元素，指针front和back分别表示队首和队尾，入队时将back向后移动，出队时将front向后移动。

队列并不需要支持访问任意元素，所以在某些情况下会用链表模拟队列。（比如NOIP初赛）

为了节约空间还可以使用循环队列，即将整个队列看做一个环，位置x的下一个位置是(x + 1) % size，虽然这一般并没有用，因为如果会MLE，基本也会TLE。

队列在BFS（搜索）和图论相关的算法中有广泛的应用。

值得注意的是，一般所说的单调队列，实际上并不是队列，而是双端队列（一端进，两端出）

全部BFS的题目都需要使用队列。

Luogu P1090
用堆进行贪心，可以优化成队列。

Luogu P2827
用堆进行贪心，需要优化成队列以卡常数。

[USACO06NOV]Fence Repair G

use priority_queue

Merge the smallest two, every time

sort the n integers.

sort:Introsort

use merge sort to count the number of inversions.