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

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はキューによって候補こうほを管理かんりする。

Stack and Queue Basics

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

1Introduction

This lecture defines stacks and queues as abstract data types and explains their operation contracts, behavior on empty structures, representative implementations, and complexity. It then shows how their removal orders determine the traversal order of DFS and BFS.

2Stack contract

A stack is a last-in, first-out (LIFO) ADT: the most recently inserted element is removed first. Its basic operations are as follows.

push(x) inserts $x$ at the top.
pop() removes and returns the top element.
top() returns the top element without removing it.
isEmpty() reports whether the number of elements is zero.

The contract must specify the result of applying pop() or top() to an empty stack. In this lecture, either operation on an empty stack violates a precondition, and the caller must prevent it with isEmpty().

After push(a), push(b), and pop(), in that order, pop() returns $b$ and $a$ remains.

3Queue contract

A queue is a first-in, first-out (FIFO) ADT: the earliest inserted element is removed first. The insertion side is the rear, and the removal side is the front.

enqueue(x) inserts $x$ at the rear.
dequeue() removes and returns the front element.
front() returns the front element without removing it.
isEmpty() reports whether the number of elements is zero.

Applying dequeue() or front() to an empty queue also violates a precondition. After enqueue(a), enqueue(b), and dequeue(), in that order, dequeue() returns $a$ and $b$ remains.

4Implementations and complexity

A stack can use the end of a dynamic array as its top. With geometric capacity growth, push takes amortized $O (1)$ time, while pop, top, and isEmpty take worst-case $O (1)$ time. A fixed-capacity array requires the contract to specify behavior when the array is full.

A queue can use a circular array with front and rear indices or a linked list with references to both ends. In a fixed-capacity circular array, all operations take worst-case $O (1)$ time if enqueue requires that the array is not full. In a circular array whose capacity grows geometrically, enqueue takes amortized $O (1)$ time but $O (n)$ time in a resizing operation. In a linked list, all operations take worst-case $O (1)$ time under a computational model in which allocating one node takes $O (1)$ time. In contrast, an ordinary array implementation that shifts every element left after each dequeue takes $O (n)$ time. Thus, an $O (1)$ bound belongs to a chosen implementation, not to the ADT itself.

Both structures require $O (n)$ space to store $n$ elements.

5Connection to DFS and BFS

Depth-first search (DFS) manages discovered but unprocessed vertices with a stack. Prioritizing the most recently added candidate continues traversal in one direction before backtracking. In a recursive implementation, the function-call stack serves this purpose.

Breadth-first search (BFS) manages candidate vertices with a queue. Processing earlier discoveries first makes traversal levels from the start vertex nondecreasing. This FIFO order supports the shortest-distance property of BFS in an unweighted graph.

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

6Summary

A stack is a LIFO ADT, and a queue is a FIFO ADT.
The contract must specify behavior of removal and access operations on an empty structure.
Operation complexity depends on the concrete implementation.
DFS manages candidates with a stack, whereas BFS uses a queue.