1 基本概念
1.1 定義
スタックは、要素を一方の端に積み重ね、同じ端から取り出す抽象的なデータ構造である。日常の例では、皿を重ねた束や書類の山に近く、最後に置いたものが最初に取りやすい形で管理される。
1.2 後入れ先出しの性質
スタックの中心原理は、後に入れた要素が先に出る後入れ先出しの規則である。この性質により、取り出し順序が挿入順序の逆転になり、処理の流れが明確になる。
1.3 抽象データ構造としての位置づけ
スタックは、具体的な保存方法よりも、どのように要素を扱うかという操作規則を重視する抽象的な枠組みである。そのため、同じ論理を保ちながら、配列や連結リストなど複数の方法で実現できる。
2 操作
2.1 追加
要素をスタックの頂上に加える操作は、一般に push と呼ばれる。新しい値は既存の要素の上に載り、次回の取り出し候補となる。
2.2 削除
頂上の要素を取り除く操作は、一般に pop と呼ばれる。最後に追加された項目が優先されるため、削除は挿入の逆順で進む。
2.3 先頭要素の参照
頂上の要素を取り出さずに確認する操作は、しばしば top や peek と表される。内容を読むだけで構造を変えない点が特徴である。
2.4 判定
スタックが空かどうかを調べる操作は、利用上重要である。空の状態で削除や参照を行うと誤りにつながるため、事前確認が安全な処理を支える。
3 実装
3.1 配列による実装
配列を用いる方法では、連続した領域に要素を並べ、末尾を頂上として扱うことが多い。単純で高速に扱いやすく、基本的な実装として広く採用される。
3.1.1 固定長配列
固定長配列では、あらかじめ確保した容量の範囲内でスタックを運用する。構造は簡潔だが、上限を超えると追加できないため、容量管理が必要になる。
3.1.2 可変長配列
可変長配列では、必要に応じて内部領域を拡張しながら要素を保持する。利用者から見ると扱いやすく、平均的には効率よく動作する一方、拡張時には再配置が発生しうる。
3.2 連結リストによる実装
連結リストでは、各要素が次の要素への参照を持ち、先頭部分を頂上として扱う。追加や削除を先頭で行えば、領域の再配置を伴わずに柔軟に操作できる。
3.3 再帰呼び出しとの関係
再帰呼び出しでは、関数の呼び出し情報が暗黙に積み重なり、戻る際に逆順で処理が進む。この仕組みはスタックの動きとよく対応しており、計算機内部の制御にも深く関わる。
4 応用
4.1 構文解析
スタックは、かっこや区切り記号の対応を調べる構文解析で役立つ。入れ子構造を順に追跡できるため、式や文の整合性を確認しやすい。
4.2 再帰処理
再帰的な問題では、途中の状態を保持しながら深い段階へ進み、解決後に順次戻る必要がある。スタックはこの流れを自然に支え、分解された部分問題の管理に適している。
4.3 深さ優先探索
深さ優先探索では、未処理の候補を積み上げ、最後に追加したものから調べていく。これにより、ある経路を深くたどってから次へ進む探索順序が実現される。
4.4 履歴管理
文書編集やブラウザ操作のように、直近の行為を順に戻したい場面では、スタック的な管理が有効である。取り消し操作との相性がよく、履歴の逆順再生に向いている。
4.5 式の評価
数式や表現の評価では、演算子や値を一時的に保持しながら処理を進めることがある。スタックを使うと、優先順位や括弧の構造を反映した計算が行いやすくなる。
5 関連概念
5.1 キューとの違い
キューは先入れ先出しで動作し、先に入った要素が先に出る点でスタックと対照的である。スタックが直近の項目を優先するのに対し、キューは順番の保持を重視する。
5.2 デックとの関係
デックは両端で追加や削除ができる構造で、スタックとキューの両方の性質を含みうる。片側だけを使えばスタックとして扱え、運用の自由度が高い。
5.3 優先度付き構造との比較
優先度付き構造では、挿入順よりも優先度の値が取り出し順を決める。これに対してスタックは、順位づけを行わず、追加時刻に基づく単純な逆順規則で動作する。
6 性質と計算量
6.1 各操作の計算量
基本的な追加、削除、参照は、適切な実装であれば多くの場合きわめて少ない手順で行える。配列末尾や連結リスト先頭を利用すると、定数時間で処理できることが一般的である。
6.2 メモリ使用量
スタックの必要領域は、保持する要素数に応じて増減する。配列実装では余裕分を含めた領域が必要になり、連結リストでは参照情報の分だけ付加的な記憶域が生じる。
6.3 実用上の制約
スタックは単純で扱いやすい反面、途中の要素を任意の位置から直接扱うのは不得手である。また、実装方式によっては容量制限や拡張の負荷が問題となるため、用途に応じた選択が重要である。