# 堆疊
###### tags: `Competitive Programming Note`

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

堆疊是一種**先進後出**的結構，像是疊盤子一樣，先放下去的會最慢被拿出來。

可以把堆疊想成是一疊元素，最上面的元素稱為堆頂。

堆疊可以自己用 `vector` 來實作，堆頂是 `back()`，要把堆頂拿掉就 `pop_back()`，放一個新的東西就 `push_back()`，但是 STL 也有提供 `stack`，但如果我沒有特別需要 `vector` 的功能，我還是會選擇用 `stack`，看起來比較美觀。

`stack` 可以做的動作大致上有這些：
- `empty()` - 判斷是否為空。
- `size()` - 取得堆疊大小。
- `top()` - 取得堆頂元素的參照。
- `push(T value)` - 放入一個元素。
- `emplace(T value)` - 常數比較小的 `push`，用於實作的結構必須有實作 `emplace_back`。
- `pop()` - 把堆頂元素移除。

template：
- `stack<classtype, container>` - `container` 是一種容器，表示這個 `stack` 應該用何種容器來實作，預設是 `deque`，用於實作的容器必須有實作這幾個方法：`empty`、`size`、`back`、`push_back`、`pop_back`。

雖然可以變更它的實作容器，但用 `deque` 就很夠了，沒什麼差。然後各種操作的複雜度依實作用的容器而異。