メインコンテンツまでスキップ

データ構造：スタック

· 約8分
tanzhuo

スタック（Stack）は先入れ後出し（LIFO）のデータ構造で、スタックトップでのみ挿入と削除の操作を許可します。スタックは配列または連結リストで実装できます。

スタックについて単独で 1 本書こうと思ったのは、これがほぼ最もシンプルなデータ構造でありながら、どこにでも存在するからです。関数呼び出し、例外スタックトレース、ブラウザの「戻る」ボタン、エディタの取り消し（Undo）操作、その背後にあるのはすべて同じモデルです。一見複雑に見える多くの問題（例えば括弧のマッチングや式の評価）も、スタックを使うことを思いつけば、途端に道筋がはっきりします。スタックを理解することは、再帰やコールスタックのオーバーフローといった問題を理解する前提でもあります。

スタックの基本概念​

スタックにおいて、挿入と削除の操作は通常プッシュ（push）とポップ（pop）と呼ばれます。要素を挿入するときはスタックトップに置かれ、要素を削除するときはスタックトップから取り除かれます。スタックトップはスタックの中で最も新しく追加された要素、スタックボトムは最も古く追加された要素です。

スタックはお皿の山にたとえられます。新しいお皿は一番上にしか置けず、取るときも一番上からしか取れません。この「口を 1 つしか開けない」という制約こそがスタックの価値です。「誰が最後に入ったか」を自然に記録してくれるので、「来た道を戻る」必要のあるシナリオの処理にとりわけ適しています。

スタックの応用は非常に幅広く、例えばコンピュータにおける関数呼び出しと再帰呼び出しは、いずれもスタックによって実現されています。ある関数が呼び出されると、その引数、リターンアドレス、ローカル変数などの情報がスタックにプッシュされ、関数が戻るときにこれらの情報がスタックからポップされます。

基本操作​

以下がスタックの基本操作です：

push(element)：要素をスタックトップにプッシュします。

pop()：スタックトップから要素を 1 つポップします。

top()：スタックトップの要素を返しますが、スタック自体は変更しません。

isEmpty()：スタックが空かどうかを判定します。

size()：スタック内の要素数を返します。

pop と top の違いに注意してください。pop はスタックトップの要素を取り除いてから返しますが、top（実装によっては peek と呼ばれます）は「一目見る」だけで、スタック自体は変わりません。コードを書くときにこの 2 つの操作を混同するのは、よくあるバグの原因です。

配列によるスタックの実装は非常に素直で、スタックトップを指すインデックスを 1 つ維持するだけです：

// 配列ベースのシンプルなスタック実装、コアロジックのみのデモ
public class ArrayStack {
    private int[] data;
    private int top = -1; // スタックトップのインデックス、-1 は空スタックを表す

    public ArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int element) {
        // 実際に使う場合はここで拡張するかスタック満杯の例外をスローすべき
        data[++top] = element; // 先にスタックトップポインタを進めてから書き込む
    }

    public int pop() {
        // 空スタックの場合は例外をスローすべきだが、ここではチェックを省略
        return data[top--]; // スタックトップの要素を返しつつポインタを戻す
    }

    public int top() {
        return data[top]; // 読み取るだけで、スタックは変更しない
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }
}

連結リストによる実装では、リストの先頭をスタックトップとみなし、push は先頭への挿入、pop は先頭ノードの削除になります。利点は容量を事前に確保する必要がないことです。

計算量の分析​

スタックの時間計算量は O(1) です。すべての操作がスタックトップで行われるためです。しかし、スタックの空間計算量は O(n) です。すべての要素を保存する必要があるためです。

別の見方をすれば、スタックの高効率はまさにその制約から来ています。中間位置での挿入や削除を許さないため、すべての操作はスタックトップへの 1 回の読み書きに帰着し、他の要素を移動する必要も走査する必要もありません。配列実装における唯一の例外は拡張時の移し替えですが、償却すればプッシュは依然として定数時間です。

スタックの典型的な応用​

コンピュータにおいて、スタック（Stack）は関数呼び出し、式の評価、コンパイラ、オペレーティングシステムなどの分野で広く応用されています。

  1. 関数呼び出し：ある関数が呼び出されると、その引数、リターンアドレス、ローカル変数などの情報がスタックにプッシュされ、関数が戻るときにこれらの情報がスタックからポップされます。このプロセスは関数コールスタックと呼ばれ、関数呼び出しを実現する基盤です。
  2. 式の評価：コンピュータが式を評価するとき、通常はスタックを使って実現します。例えば、中置記法の式を後置記法の式に変換するとき、式の値を正しく計算できるように、スタックを使って演算子を保存する必要があります。
  3. コンパイラ：コンパイラがソースコードをターゲットコードに変換する過程で、構文解析やコード生成などの機能をスタックで実現しています。例えばコンパイラでは、変数、関数、文などの情報をスタックで保存します。
  4. オペレーティングシステム：OS におけるプロセススケジューリングや割り込み処理などの機能もスタックを使って実現されています。例えばあるプロセスが割り込まれたとき、OS は現在のプロセスのコンテキスト情報（レジスタの値、プログラムカウンタの値など）をスタックにプッシュしてから、割り込みハンドラを実行します。割り込みハンドラの実行が終わると、OS はスタックからコンテキスト情報をポップし、現在のプロセスの実行を復元します。

この 4 つのシナリオには共通点があります。いずれも「入る — 処理する — 逆順に出る」というネスト構造が存在することです。関数のネスト呼び出し、括弧のネスト、割り込みのネストは、本質的にすべて同じ種類の問題であり、だからこそすべてスタックというモデルに落ち着くのです。普段の競技プログラミングで出会う括弧のマッチング、単調スタック、深さ優先探索の非再帰版なども、すべてこの考え方の延長線上にあります。

ハマりどころと注意点​

  1. 空スタックの操作：空スタックに pop や top を実行するのは未定義動作か、そのまま例外がスローされます。呼び出す前に isEmpty で判定するか、明示的に例外処理に依存するかのどちらかで、思い込みで扱ってはいけません。

  2. スタックオーバーフロー：再帰は本質的にコールスタックを消費するので、再帰の階層が深すぎるとスタックオーバーフローを引き起こします（Java では StackOverflowError）。深さがコントロールできない再帰に出会ったら、明示的なスタックとループによる反復版に書き換え、データをヒープ上に移すとよいでしょう。

ヒント

Java では java.util.Stack の使用はもうおすすめしません。Vector を継承しているため、メソッドに同期のオーバーヘッドがあり、設計も古くなっています。公式ドキュメントは ArrayDeque をスタックとして使うことを推奨しています。

  1. pop と top の混同：スタックトップを読みたいだけなのに pop を呼んでしまうと、こっそり要素を失います。この種のバグはループの中では特に見つけにくいものです。

まとめ​

スタックは「制約と引き換えに効率を得る」典型例です。スタックトップという 1 つの操作口だけを開放することで、すべての操作を O(1) のコストで実現し、同時にあらゆるネスト・バックトラック系の問題に自然にフィットします。push/pop/top というこれらの操作と LIFO のメンタルモデルを身につければ、関数コールスタックや式の評価といったメカニズムも、同じモデルが異なるレイヤーで繰り返し応用されているだけだとわかるはずです。

COMMENTS