スタック (push/pop) を実装する｜コードで実践

スタック (push/pop) を実装する

このレッスンで分かること

配列の末尾を「スタックの上 (top)」とみなすのが定番です

ここから第 4 章「データ構造 (基本)」に入ります

このレッスンでは、空のスタックに対して push 5 push 3 pop のような操作列を順番に実行し、最後に残った状態を配列として返す関数を作ります

スタック (push/pop) を実装するとは

後入れ先出し (LIFO) の代表選手であるスタックを、push と pop の操作シーケンスで動かす。

ここから第 4 章「データ構造 (基本)」に入ります。最初に扱うのは スタック (stack) です。スタックは皿を積み重ねるのと同じイメージで、一番最後に入れたもの が 一番最初に出てくる データ構造です。この性質を LIFO (Last In, First Out) と呼びます。実装はとてもシンプルなのに、関数呼び出しの履歴管理、ブラウザの戻るボタン、Undo / Redo、式の評価など、応用範囲はとても広い縁の下の力持ちです。

このレッスンでは、空のスタックに対して push 5 push 3 pop のような操作列を順番に実行し、最後に残った状態を配列として返す関数を作ります。スタックの動きを 手で追える ことが、第 4 章全体を理解する基礎になります。

スタックは LIFO。最後に積んだ皿を最初に取る、これが全て。

操作は 2 つだけ

スタックの操作は push と pop の 2 つだけです。push x は値 x を一番上に積む操作、pop は一番上の値を取り除く操作です。今回の課題では ["push", 5] や ["pop"] という配列を要素にもつ操作列 operations が渡されます。空のスタックに対して pop が来たら何もしない (無視) というルールにします。これは現実のスタックでも スタックアンダーフロー を防ぐ安全策としてよく用いられる方針です。

配列の末尾を「スタックの上 (top)」とみなすのが定番です。push は末尾追加、pop は末尾削除なので、Python なら list.append / list.pop、JavaScript なら Array.push / Array.pop がそのまま使えます。どちらも平均 O(1) で動きます。

push と pop は両方とも末尾操作。配列の末尾を top にすれば計算量 O(1) で動く。

動きを図で追う

diagram (will load when visible)

手順は次のとおりです。最初は []、push 5 で [5]、push 3 で [5, 3]、pop で [5]、push 9 で [5, 9] です。配列の 左端が底、右端が top という向きを最後まで崩さないことが、混乱しないコツです。

Python での実装

Python

def stackOps(initial, operations):
    stack = list(initial)
    for op in operations:
        if op[0] == 'push':
            stack.append(op[1])
        elif op[0] == 'pop':
            if stack:
                stack.pop()
    return stack

ポイントは list(initial) で コピー を作ることです。元の配列を直接書き換えると、呼び出し側で予期せぬバグが起きます。for ループで 1 つずつ操作を見て、pop か push かで分岐します。空スタックでの pop は単に無視します。

JavaScript での実装

JavaScript

function stackOps(initial, operations) {
  const stack = [...initial];
  for (const op of operations) {
    if (op[0] === 'push') {
      stack.push(op[1]);
    } else if (op[0] === 'pop') {
      if (stack.length > 0) stack.pop();
    }
  }
  return stack;
}

...initial で配列のコピーを作っています。push と pop は JavaScript の配列メソッドにそのまま用意されているので、ロジックが宣言的に書けます。

計算量

操作数を n とすると、各 push / pop は O(1) で完了するので、全体で O(n) です。配列の末尾 を top にする限り、コピーや要素のずらしは発生しません。逆に、配列の先頭を top にしてしまうと、push のたびに全要素をずらす必要があり O(n) 操作になります。配列を使うときは「どっちが top か」で性能が大きく変わります。

スタックの計算量は push / pop ともに 均し O(1)。配列の末尾を top にすると素直に成立する。

よくある間違い

1 つ目は 空スタックの pop を考えていない ケースです。stack.pop() が None や undefined を返すことに気づかず、null pointer 系のエラーを引き起こします。今回は「空なら無視」ルールで対応しています。

2 つ目は 入力配列を直接書き換える ケースです。Python の stack = initial だと参照を共有してしまい、stack.append が呼び出し元の配列にも反映されてしまいます。必ず list(initial) などでコピーを取ります。

3 つ目は push と pop の 順番を逆に解釈する ケースです。pop は 必ず末尾 から行います。先頭から取り出してしまうとそれは キュー の挙動になり、後のレッスンで扱う別物になります。

やってみよう

initial = [1, 2]、operations = [["push", 3], ["pop"], ["pop"]] を手で追って、結果が [1] になることを確認する。
operations が空配列のとき、initial がそのまま返ることを確認する。
pop だけが連続したとき、空になっても落ちずに [] を返せるか試す。
スタックを 配列の先頭 を top にして書き直し、計算量がどう変わるか考える。

よくある質問

Q. スタックの主な用途は何ですか？

A. 「最後に入れたものから取り出す」LIFO 構造で、関数呼び出しの履歴・式の評価・括弧のマッチング・undo 機能などに使います。配列で push / pop すれば実装でき、Java は ArrayDeque、Python は list、JS は配列が事実上のスタックとして使えます。

Q. Java の Stack クラスは使うべきですか？

A. 古い Vector を継承していて非推奨気味です。代わりに ArrayDeque を使ってください。push / pop / peek が同じインターフェースで使え、同期化のオーバーヘッドがない分高速です。並行アクセスが必要なら ConcurrentLinkedDeque を選びます。

Q. スタックオーバーフローはどう防ぐ？

A. 再帰深さを浅くするか、再帰を明示的なスタック（ArrayDeque）に書き換えます。後者は深さ制限がメモリ次第になるため、大規模グラフ探索などで重宝します。tail call 最適化のある言語（Scala/Scheme）なら再帰のままで OK です。

次のレッスン

次は キュー (enqueue / dequeue) を実装する に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

スタックの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. スタックとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

スタック (push/pop) を実装する