スタックとキューの基本きほん

date2026-07-14document_iddoc_8f494f7c9e0522ea22b8df5937f1940cdescriptionスタックとキューを抽象データ型として定義し、操作契約、実装、計算量、DFSとBFSへの接続を説明する。prerequisites計算量の基本 / 配列の基本操作 / 抽象データ型と実装の区別type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1導入どうにゅう

この講義こうぎでは、スタックとキューを抽象ちゅうしょうデータ型がたとして定義ていぎし、操作そうさの契約けいやく、空からの構造こうぞうに対たいする挙動きょどう、代表的だいひょうてきな実装じっそう、計算量けいさんりょうを説明せつめいする。さらに、両者りょうしゃの取出順序とりだしじゅんじょがDFSとBFSの探索順序たんさくじゅんじょを規定きていすることを確認かくにんする。

2スタックの契約けいやく

スタック（stack）は、最後さいごに追加ついかした要素ようそを最初さいしょに除去じょきょするLIFO（last in, first out）のADTである。基本操作きほんそうさを次つぎのように定さだめる。

push(x) は要素ようそ $x$ を頂上ちょうじょうへ追加ついかする。
pop() は頂上ちょうじょうの要素ようそを除去じょきょして返かえす。
top() は頂上ちょうじょうの要素ようそを除去じょきょせずに返かえす。
isEmpty() は要素数ようそすうが $0$ であるかを返かえす。

空からのスタックに pop() または top() を適用てきようした結果けっかは、ADTの契約けいやくで明示めいじする必要ひつようがある。本講義ほんこうぎでは、この操作そうさを事前条件違反じぜんじょうけんいはんとし、呼出側よびだしがわが isEmpty() によって回避かいひする。

push(a), push(b), pop() を順じゅんに実行じっこうすると、pop() は $b$ を返かえし、 $a$ が残のこる。

3キューの契約けいやく

キュー（queue）は、最初さいしょに追加ついかした要素ようそを最初さいしょに除去じょきょするFIFO（first in, first out）のADTである。追加側ついかがわを末尾まつび、除去側じょきょがわを先頭せんとうと呼よぶ。

enqueue(x) は $x$ を末尾まつびへ追加ついかする。
dequeue() は先頭せんとうの要素ようそを除去じょきょして返かえす。
front() は先頭せんとうの要素ようそを除去じょきょせずに返かえす。
isEmpty() は要素数ようそすうが $0$ であるかを返かえす。

空からのキューに dequeue() または front() を適用てきようすることも事前条件違反じぜんじょうけんいはんとする。enqueue(a), enqueue(b), dequeue() を順じゅんに実行じっこうすると、dequeue() は $a$ を返かえし、 $b$ が残のこる。

4実装じっそうと計算量けいさんりょう

スタックは動的配列どうてきはいれつの末尾まつびを頂上ちょうじょうとすれば実装じっそうできる。容量ようりょうを定数倍ていすうばいに拡張かくちょうする動的配列どうてきはいれつでは、push は償却しょうきゃく $O (1)$ 、pop、top、isEmpty は最悪時さいあくじ $O (1)$ である。固定容量配列こていようりょうはいれつでは、満杯時まんぱいじの挙動きょどうを契約けいやくに追加ついかする必要ひつようがある。

キューは循環配列じゅんかんはいれつと先頭せんとう・末尾まつびの添字そえじ、または両端りょうたんへの参照さんしょうをもつ連結れんけつリストで実装じっそうできる。固定容量こていようりょうの循環配列じゅんかんはいれつでは、満杯まんぱいでないことを enqueue の事前条件じぜんじょうけんとすれば、すべての操作そうさは最悪時さいあくじ $O (1)$ である。容量ようりょうを定数倍ていすうばいに拡張かくちょうする循環配列じゅんかんはいれつでは、enqueue は償却しょうきゃく $O (1)$ であるが、拡張時かくちょうじの最悪時間さいあくじかんは $O (n)$ である。連結れんけつリストでは、要素ようその割当わりあてを $O (1)$ とする計算模型けいさんもけいの下もとで、すべての操作そうさが最悪時さいあくじ $O (1)$ となる。ただし、通常つうじょうの配列はいれつで dequeue のたびに全要素ぜんようそを左ひだりへ移動いどうする実装じっそうは $O (n)$ 時間じかんを要ようする。したがって、 $O (1)$ という評価ひょうかはADT自体じたいではなく、選択せんたくした実装じっそうに依存いぞんする。

いずれも $n$ 要素ようそを保持ほじする領域りょういきは $O (n)$ である。

5DFSとBFSへの接続せつぞく

深ふかさ優先探索ゆうせんたんさく（DFS）は、発見済はっけんずみで未処理みしょりの頂点ちょうてんをスタックで管理かんりする。最後さいごに追加ついかした候補こうほを優先ゆうせんするため、一方向いちほうこうの探索たんさくを継続けいぞくしてから後戻あともどりする。再帰実装さいきじっそうでは、関数呼出かんすうよびだしのスタックがこの役割やくわりを担になう。

幅優先探索はばゆうせんたんさく（BFS）は候補頂点こうほちょうてんをキューで管理かんりする。先さきに発見はっけんした候補こうほを先さきに処理しょりするため、始点してんからの探索たんさくレベルが非減少順ひげんしょうじゅんになる。このFIFO順序じゅんじょが、無重むおもみグラフにおけるBFSの最短距離計算さいたんきょりけいさんを支ささえる。

data/lecture/information/algorithm/search/dfs-and-bfs-basics.lecture.n.md

6まとめ

スタックはLIFO、キューはFIFOの操作契約そうさけいやくをもつADTである。
空構造くうこうぞうへの除去操作じょきょそうさと参照操作さんしょうそうさの挙動きょどうは、契約けいやくで明示めいじする。
操作そうさの計算量けいさんりょうは具体的ぐたいてきな実装じっそうに依存いぞんする。
DFSはスタック、BFSはキューによって候補こうほを管理かんりする。