スタック
最終更新
スタックとは、開いている端がちょうど1つだけのコレクションです。値を追加するときはトップに積み（プッシュ）、取り除くときは同じトップから外します（ポップ）。そのため、最後に入れた値がつねに最初に出てきます。これが後入れ先出し（LIFO）の意味であり、規則はこれだけです。上に載っているものを先にどけない限り、途中の値に手を伸ばす方法はありません。上の再生ボタンを押して、プッシュのたびに柱が伸び、ポップのたびに同じ端から縮んでいく様子を見てください。
この制約こそが要点です。どちらの操作もトップにしか触れないため、スタックがどれだけ高くなっても1回あたり O(1) であり、この予測しやすさこそ、スタックがこれほど多くの場面を支えている理由です。再帰 を動かす呼び出しスタック、エディタの取り消し履歴、パーサーでの括弧の対応チェック、そして再帰的な 深さ優先探索 をループに変える明示的なスタックなどです。取り除く端を入れ替えれば、代わりに キュー になります。
時間計算量と空間計算量
配列ベース、または連結リストベースの標準的なスタックについて：
| 操作 | 計算量 | 備考 |
|---|---|---|
| プッシュ（push） | O(1) | 動的配列では償却 O(1)。ときどきサイズ変更が入る。 |
| ポップ（pop） | O(1) | つねにトップの要素なので、要素をずらす必要がない。 |
| ピーク（top） | O(1) | 取り除かずにトップを読む。 |
| 検索 | O(n) | スタックの用途ではない。下まで順にポップしていく必要がある。 |
| 空間 | O(n) | 格納する値1つにつき1スロット。 |
ステップごとの手順
| ステップ | 何が起きるか |
|---|---|
| 1 | スタックは空の状態から始まり、トップは何も指していない。 |
| 2 | プッシュはトップの位置に値を書き込み、トップを1つ上へ動かす。 |
| 3 | さらにプッシュすると、直前の値のすぐ上に載る。 |
| 4 | ポップはトップにある値を読み、それからトップを1つ下へ動かす。 |
| 5 | 返ってくるのはつねに、いちばん最近プッシュした値である。 |
| 6 | 空のスタックをポップするのはエラーで、スタックアンダーフローと呼ばれる。だから実際のコードではまず is_empty() を確認する。 |
具体例
3、7、5 をプッシュし、そのあとスタックを空になるまで取り出すと：
| 操作 | スタック（下から上へ） | 返り値 |
|---|---|---|
push(3) | [3] | なし |
push(7) | [3, 7] | なし |
push(5) | [3, 7, 5] | なし |
pop() | [3, 7] | 5、いちばん新しい値 |
pop() | [3] | 7 |
pop() | [] | 3、いちばん古い値が最後 |
スタックを使うべきとき
Stackのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なStackの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのStackのコード
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)JavaScriptでのStackのコード
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);JavaでのStackのコード
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}C++でのStackのコード
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}CでのStackのコード
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}スタックに関するよくある質問
LIFO とはどういう意味ですか？
後入れ先出し、つまりいちばん最近プッシュした値が最初にポップされる、ということです。積み重ねた皿がよく使われるたとえで、いま置いたばかりの皿を取り、いちばん下の皿は取りません。キュー はこれと逆の規律、すなわち FIFO です。
スタックとキューの違いは何ですか？
どちらの端から取り除くか、それだけです。どちらも一方の端に
O(1) で追加します。スタックはその同じ端から取り除き（LIFO）、キューは反対の端から取り除きます（FIFO）。上の計算量の表を含め、それ以外はまったく同じです。スタックの主な操作は何ですか？
push は値をトップに積み、pop はトップの値を取り除いて返し、peek（top と呼ばれることもあります）は取り除かずにトップを読み、is_empty は中身が残っているかどうかを教えます。この4つはすべて O(1) です。スタックオーバーフローとは何ですか？
空きがなくなったスタックにプッシュすることです。有名な例が呼び出しスタックです。関数呼び出しのたびにフレームが積まれるため、ベースケースに到達しない 再帰 は積み続け、ランタイムのスタック上限に達したところでプログラムがクラッシュします。その裏返しのエラー、つまり空のスタックをポップすることは、スタックアンダーフローと呼ばれます。
スタックはどのように実装されますか？
よくある実装は2通りです。動的配列は末尾で追加と削除を行い、償却
O(1) でキャッシュにも優しい方式です。Pythonの list とJavaの ArrayDeque はこの方式です。連結リストは先頭で追加と削除を行い、最悪でも O(1) でサイズ変更も不要ですが、要素ごとにポインタ分のコストがかかります。C++の std::stack はアダプタで、既定では区分化された配列である std::deque の上で動き、別のコンテナを指定することもできます。関連リソース
その他の可視化
