queue / stack / deque
超基礎のデータ構造かつ、難しいアルゴリズムでも時に有効
queue
キューと読む。
データを追加したり、古い方から削除することが可能。
先頭から削除する要素はvectorでは$ Ο(N)かかるため、頻繁に削除を行うことはあまりよろしくない(多分)。
queueを用いることでこの操作の計算量が$ Ο(1)となる。
ただし、基本的にランダムアクセス(先頭以外の要素の参照)ができない。
主な使用例
BFS
尺取り法
例題
グラフの探索をする大体の問題
random-accessible queue
これは ac-library の atcoder::internal_queue で用いられている実装だが、vectorと現在の先頭要素を指す変数を組み合わせることで、擬似的にランダムアクセスが可能なqueueを自作できる。
ただし、末尾への追加処理はメモリ確保のために比較的低数倍が重いので、事前に追加処理の合計回数を見積もれる場合にだけ使うのを推奨する。
stack
スタックと読む。
データを追加したり、新しい方から削除することが可能。
やはりランダムアクセスはできないが、いくつかのデータの列を部分的に反転させつつ順に処理するなどの操作ができる。
また、DFS を再帰処理を書かずに書くこともできる。
例題
deque
デックと読む。
先頭に追加、削除および末尾に追加、削除が$ Ο(1)で可能なデータ構造。
queueもstackも兼ね備えた上で先頭に追加まで実現している。
その性質上、先頭にも末尾にも追加するクエリの問題なんかで頻繁に用いることになる。
例題
じゃあ queue と stack はいらなくね
そんなことはない(当社調べ)。
まず、dequeでは先頭にも末尾にもそれぞれ追加と削除のメソッドがあるので、
push_back
push_front
pop_back
pop_front
という$ 4種類のメソッドがある(C++ での話)。
一方queueでは
push
pop
しかない。これは、タイプ量の大きな削減になる。
また、queueもstackも捨ててしまって名前の意味が失われたdequeだけになると、そのデータ構造が何をしているのかが若干わかりづらくなるだろう。
意外にも、いらない機能は最大限捨てた方がいいことがある。