【就プロ】スタックとキュー - takahiro

前回「配列とリスト」に引き続き、線形のデータ構造のスタックとキューについて説明します。

取り出し・挿入・削除をいずれも一番最後の要素のみに限るデータ構造を「スタック」と言います。
このように一番最後の要素に行う操作をLIFO（Last-In-First-Out）と呼ばれます。
取り出し・挿入・削除の操作は$O(1)$で行うことができます。

挿入は新しい要素を一番最後に加え、取り出し・削除は先頭の要素に行うデータ構造を「キュー」と言います。
このように先に挿入したものから先に取り出し・削除が行われるため、FIFO（First-In-First-Out）と呼ばれます。
取り出し・挿入・削除の操作は$O(1)$で行うことができます。

スタックとキューは、先頭の要素もしくは最後の要素に対して操作を行うため、それらを実装した両端キュークラスdequeがあります。

スタックに関しては、スタッククラスstackが用意されています。

キューに関しても、キュークラスqueueが用意されています。