スタック — Project Hematite

プログラムが関数を呼び出すとき、テキストエディタで直前の操作を取り消すとき、ブラウザが前のページに戻るとき — これらすべてが同じシンプルな仕組みに依存している。それがスタック（stack）だ。

スタックとは何か

スタックは要素のコレクションで、後入れ先出し（Last-In, First-Out / LIFO）の原則に従う。最後に追加した要素が、常に最初に取り出される。皿の積み重ねをイメージするとわかりやすい。新しい皿は上に乗せ、取り出すときも常に一番上から取る。途中から皿を抜き取ることはできない。

スタックが持つ基本操作はちょうど 2 つだ：

push — スタックの先頭に要素を追加する。
pop — 先頭の要素を取り出して返す。

もう 1 つ、必須ではないが頻繁に使われる補助操作がある：

peek（または top）— 先頭の要素を取り出さずに読む。

スタックの動作を順に追う

空のスタックから始めて次の操作を行うとする：

push(1)   →  [1]
push(2)   →  [1, 2]
push(3)   →  [1, 2, 3]
pop()     →  returns 3, stack is [1, 2]
pop()     →  returns 2, stack is [1]

最後に push した要素（3）が最初に pop される。これが LIFO の性質だ。

配列でスタックを実装する

配列は $O(1)$ のインデックスアクセスを持つため、スタックのバッキングストア（backing store）として最もよく使われる。現在の先頭要素を指す top インデックスという値を 1 つ追加で管理する。

push: top インデックスをインクリメントしてから新しい要素を書き込む。
pop: top インデックスの位置にある要素を読み取り、インデックスをデクリメントする。
peek: top インデックスの要素を読むだけで変更しない。

3 つの操作はいずれも $O(1)$ で動作する。

以下は Rust で Vec（可変長配列）をバッキングストアとして使ったシンプルなスタック実装だ：

pub struct Stack<T> {
    data: Vec<T>,
}

impl<T> Stack<T> {
    /// 空のスタックを作る。
    pub fn new() -> Self {
        Stack { data: Vec::new() }
    }

    /// `value` をスタックの先頭に積む。
    pub fn push(&mut self, value: T) {
        self.data.push(value);
    }

    /// 先頭の要素を取り出して返す。スタックが空なら `None` を返す。
    pub fn pop(&mut self) -> Option<T> {
        self.data.pop()
    }

    /// 先頭の要素への参照を取り出さずに返す。
    pub fn peek(&self) -> Option<&T> {
        self.data.last()
    }

    /// スタックが空なら `true` を返す。
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
}

Vec::push と Vec::pop はどちらもベクターの末尾を操作するため、この実装はすべての操作が $O(1)$ だ（push は内部配列の拡張が発生することがあるため、ならし計算量（amortized）での $O(1)$ ）。

LIFO の順序が重要な理由

LIFO という性質は単なる珍しい特性ではなく、決定の列を逆順に処理する必要があるときや、来た道を覚えておく必要があるときに自然に現れる：

関数呼び出しの管理。 プログラムが関数を呼び出すたびに、戻りアドレスとローカル変数がコールスタック（call stack）に push される。関数が戻るとそれらが pop される。これは Calling Stack で詳しく扱う。
アンドゥ/リドゥシステム。 編集のたびに push する。Ctrl+Z を押すと最後の編集が pop されて取り消される。
括弧の対応チェック。 開き括弧を push し、閉じ括弧が来たら pop して対応を確認する。
深さ優先探索（DFS）。 木やグラフを走査するとき、再帰の代わりに明示的なスタックを使える。

オーバーフローとアンダーフロー

常に防ぐべき 2 つのエラー条件がある：

スタックオーバーフロー（stack overflow） — 満杯のスタックに push しようとすること（固定サイズ配列では直接問題になる。Vec ベースのスタックは自動的に拡張されるが、無制限に拡張するとメモリを使い果たす可能性がある）。
スタックアンダーフロー（stack underflow） — 空のスタックに対して pop や peek を呼ぶこと。上の Rust 実装では両方が Option<T> を返すため、空の場合を明示的に処理せざるを得ず、パニックを防げる。

まとめ

スタックは LIFO の順序で要素を保持する。最後に push した要素が最初に pop される。
基本操作は push、pop、peek の 3 つで、配列バックの実装ではすべて $O(1)$ 。
Rust の Vec は自然なバッキングストアだ。末尾への push と pop でそのままスタックのセマンティクスが得られる。
スタックは、操作の履歴を追跡したり、逆順に処理すべき仕事を積み上げたりする場面でコンピューティング全体に登場する。