# 佇列
###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

佇列是一種先進先出的結構，也就是先放進去的元素，會先被取出來，跟排隊一樣，先排隊的人會先離開隊伍。

STL 提供了 `queue`，大致上可以做這些動作：
- `empty()` - 判斷是否為空。
- `size()` - 取得佇列大小。
- `front()` - 取得在最前面的元素。
- `back()` - 取得在最後面的元素。
- `push(T value)` - 在尾端放入一個元素。
- `emplace(T value)` - 低常數版 `push`，實作用容器必須實作 `emplace_back`。
- `pop()` - 移除最前面的元素。
- `clear()` - 移除所有元素。

template：
- `queue<classtype, container>` - `container` 是用於實作的容器類別，預設是 `deque`，實作用的容器必須有實作 `empty()`、`size()`、`front()`、`back()`、`push_back()` 和 `pop_front()`，各種操作的複雜度依實作容器而異。

## 雙向佇列

這是有兩個頭的佇列，兩邊都可以進去，也都可以出來。STL 提供了 `deque`，它也是動態陣列的一種，和 `vector` 不同的是，它不是把資料儲存在連續記憶體，而是分散在很多段記憶體中，不過它可以 $O(1)$ 隨機存取，還有 $O(1)$ 在頭和尾插入，在中間插入就和 `vector` 一樣，需要 $O(n)$ 的時間。

它大致上有這些操作：
- `empty()` - 判斷是否為空，$O(1)$。
- `size()` - 取得佇列大小，$O(1)$。
- `front()` - 取得在最前面的元素，$O(1)$。
- `back()` - 取得在最後面的元素，$O(1)$。
- `operator[]` - 取得指定位置的元素，$O(1)$。
- `push_back(T value)` - 在尾端插入元素，$O(1)$。
- `push_front(T value)` - 在前端插入元素，$O(1)$。
- `pop_back(T value)` - 移除尾端元素，$O(1)$。
- `pop_front(T value)` - 移除前端元素，$O(1)$。