markdown
スタックとキューの基本
lecture/information/algorithm/data-structures/スタックとキューの基本-講義.n.md
スタックとキューの基本
algorithmdata-structuresundergraduatelecture
導入
この講義で最重要なのは、データ構造は値を入れる箱ではなく、どの順番で取り出すかを決める規則だと見ることです。
同じ要素を持っていても、最後に入れたものを先に出すのか、最初に入れたものを先に出すのかで、探索や処理の流れは大きく変わります。
用語と定義
スタック とは、最後に入れた要素を最初に取り出すデータ構造です。
キュー とは、最初に入れた要素を最初に取り出すデータ構造です。
方針
まず取り出し順だけを見ます。そのあと、その順が探索や状態管理にどう効くかを考えます。
直感的な説明
スタックは皿を重ねた山のようなもので、上からしか取れません。キューは列のようなもので、先頭から出て末尾へ入ります。
厳密な説明
1. スタック
スタックでは push で要素を追加し、pop で最後の要素を取り出します。したがって最新の状態へ戻る処理と相性がよく、再帰の呼び出しや DFS の管理に使われます。
2. キュー
キューでは enqueue で末尾へ追加し、dequeue で先頭から取り出します。したがって到着順を保ったまま処理したい場面に向き、BFS の管理に使われます。
3. 計算量
適切に実装すれば、スタックの push / pop もキューの enqueue / dequeue も基本的に O(1) で行えます。
見分け方
- 最後に見たものへ戻りたいなら、スタックを疑います。
- 先に来たものから順に処理したいなら、キューを疑います。
- DFS と結びつくのはスタック、BFS と結びつくのはキューです。
最終形
\boxed{\text{stack = LIFO,\quad queue = FIFO}}
一言でいうと
- データ構造の違いは、取り出し順の違いとして見ると整理しやすくなります。