堆疊

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

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

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

堆疊可以自己用 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 就很夠了，沒什麼差。然後各種操作的複雜度依實作用的容器而異。