スタッククラス（push と pop）｜コードで実践

スタッククラス（push と pop）

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

append と pop は Python の list がもともと持っているメソッドで、それぞれ O(1) です

スタック (stack) は、最後に入れたものを最初に取り出す データ構造です

スタック に必要な要素を洗い出すと、次のとおりです

スタッククラスとは

LIFO のスタックをクラスで実装する。stackOps(ops) で push / pop の操作列を適用し、最終状態を配列で返す。

スタック (stack) は、最後に入れたものを最初に取り出す データ構造です。お皿を上から積んでいき、上から順に取り出すのと同じ。略して LIFO (Last In, First Out) と呼ばれます。第 4 章でも触れましたが、ここでは クラス を使って「データ と 操作 をまとめる」 OOP の練習をします。

スタックは「最後に入れたものが最初に出る」、つまり LIFO の代表的なデータ構造だ。

クラスでスタックを設計する

スタック に必要な要素を洗い出すと、次のとおりです。

属性 — 中身を保持する 配列 (内部リスト)
メソッド — push(x) で末尾に追加、pop() で末尾を取り出す、peek() で末尾を覗く、size() で要素数を返す

これを Python で書くとこうなります。

Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

append と pop は Python の list がもともと持っているメソッドで、それぞれ O(1) です。スタック を クラス でラップするメリットは、「使う側から見たら配列の操作を意識しない」点にあります。

スタックの動きを図で理解

diagram (will load when visible)

図のポイント (テキスト併記)

push は上に積む、pop は上から取り出す、というだけのシンプルなルール

push は上に積む、pop は上から取り出す、というだけのシンプルなルール。Undo 機能、関数呼び出しの コールスタック、括弧の対応チェック など、応用は数え切れません。

JavaScript / Java での実装

JavaScript

class Stack {
  constructor() { this.items = []; }
  push(x) { this.items.push(x); }
  pop() { return this.items.pop(); }
  size() { return this.items.length; }
}

JavaScript の Array には標準で push / pop メソッドが付いているので、ほぼそのまま使えます。

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    static class Stack {
        List<Integer> items = new ArrayList<>();
        void push(int x) { items.add(x); }
        int pop() { return items.remove(items.size() - 1); }
    }
}

Java には java.util.Stack という標準クラスもありますが、ここでは自作の Stack を static class として書きます。

このレッスンでやること

インスタンスを返すと比較しづらいので、操作列を受け取って最終的な中身を配列で返す 形にする。

関数 stackOps(ops) を実装します。ops は ["push", 1] ["pop"] などの操作列を表す 配列の配列。これを順番に Stack クラスに適用し、最後に Stack の中身を配列として返します。例として [["push", 1], ["push", 2], ["pop"], ["push", 3]] を渡すと、内部状態は [1, 3] になります。

スタックが活躍する場面

スタック は単独で使うだけでなく、他のアルゴリズムの「裏方」としても頻繁に登場します。

カッコ のバランス判定 — 開きカッコを push、閉じカッコで pop して種類を照合
式の評価 — 逆ポーランド記法 (RPN) の計算は スタック で表現できる
関数呼び出し — どの言語でも コールスタック が暗黙的に動いている
Undo / Redo 機能 — 過去の状態を スタック に積む

スタック の理解は、後の章で扱う 木の DFS や 括弧の妥当性チェック でも前提知識になります。ここでしっかり感覚を掴んでおきましょう。

配列の 末尾 を push/pop するパターンを覚えれば、どの言語でも スタック をすぐに実装できる。

よくある間違い

空の スタック で pop するとエラー / undefined になる。今回のテストでは空 pop は来ないので気にしなくて OK。
配列の先頭 を pop してしまうと O(n) になる。末尾 を push/pop するのが鉄則。
クラス を使わずに直接 配列 の push/pop を書いても答えは合うが、ここではクラス設計の練習をする。

やってみよう

stackOps(ops) を実装してください。ops の各要素は ["push", value] か ["pop"] の形です。pop の戻り値は捨てて構いません。最終的に内部の スタック を 配列 として返します。

よくある質問

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） で、FIFO のキューをクラスで実装する方法を学びます。

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

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

理解度チェック (30 秒)

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

この章のポイント

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

関連レッスン

スタッククラス（push と pop）