佇列

tags: Competitive Programming Note

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

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

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)$。