スタック
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/26 07:37 UTC 版)
ソフトウェア
この節では、抽象データ型としてのスタックのソフトウェアによる実装について述べる。
高水準言語では、スタックは配列や線形リストを使って効率的に実装可能である。LISPでは任意のリストに対して push や pop に相当する関数（consがpush、cdrがpopである）を使用可能なので、スタックを実装する必要は無い。
応用例
式評価と構文解析
逆ポーランド記法を使用している電卓（Hewlett-Packardの関数電卓など）は、値を保持するためにスタック構造を使う。式は、前置記法、中置記法、後置記法のいずれかで表現される。ある記法から別の記法への変換にはスタックが必要となる。多くのコンパイラは低レベルな言語に翻訳する前の構文解析のためにスタックを使用する。多くのプログラミング言語は文脈自由言語であり、スタックベースの機械で構文解析することができる。ちなみに自然言語は文脈依存言語であり、スタックだけではその意味を解釈することはできない。
例えば、((1 + 2) * 4) + 3 という計算は、交換法則と括弧を優先するという前提で、次のように後置記法（逆ポーランド記法）に変換できる。
1 2 + 4 * 3 +
この式はオペランドスタックを使って左から右に以下のように評価できる。
- オペランド（演算数）に遭遇したら push する。
- 演算子に遭遇したら、オペランドスタックから2つのオペランドを pop して演算を行い、
- その解を push する。
具体的には以下のようになる。「オペランドスタック」は「操作」した後の状態を示している。
| 入力 | 操作 | オペランドスタック |
|---|---|---|
| 1 | オペランドをPush | 1 |
| 2 | オペランドをPush | 1, 2 |
| + | 加算 | 3 |
| 4 | オペランドをPush | 3, 4 |
| * | 乗算 | 12 |
| 3 | オペランドをPush | 12, 3 |
| + | 加算 | 15 |
最終的な演算結果は 15 で、終了時にオペランドスタックのトップに置かれている。
探索問題の解法
探索問題を解くとき、総当り的か最適化されているかに関わらず、スタックを多大に必要とすることが多い。総当り探索の例としては、力まかせ探索やバックトラッキングがある。最適探索の例としては、分枝限定法 (branch and bound) やヒューリスティックによる解法がある。いずれのアルゴリズムでも、発見してはいるが探索していない探索ノードを覚えておくのにスタックが必要となる。スタックを使う以外の手法としては再帰を使う方法があるが、これはコンパイラが生成するコードが内部的に使用するスタックで代替しているだけである。スタックを使った探索は幅広く使われており、木構造の単純な幅優先探索や深さ優先探索から、クロスワードパズルを自動的に解くプログラムやコンピュータチェスゲームでも使われている。ある種の問題はキューなどの別のデータ構造を使って解くこともでき、探索順を変えたいときに有効である。
プログラミング言語処理系の実装
ほとんどのコンパイルされたプログラムは実行時（ランタイム）環境においてコールスタックを使用し、プロシージャ/関数呼び出しに関する情報を格納するのに使っている。そして、呼び出し時のコンテキスト切り替えや呼び出し元への復帰の際に使用して、呼び出しの入れ子を可能としている。そのとき、呼び出される側と呼び出し側の間には引数や返り値をスタックにどう格納するかという規則が存在する。スタックは関数呼び出しの入れ子や再帰呼び出しを実現するための重要な要素となっている。この種のスタックはコンパイラが内部的に使用するもので、プログラマがこれを直接操作することはほとんど無い。
コールスタック内に関数の呼び出し毎に作られるフレームをスタックフレームと言い、それをたどって（トレースして）得られる呼び出しの情報をスタックトレースと言う。
プログラミング言語によっては、プロシージャ内のローカルなデータをスタックに格納する。ローカルなデータの（スタック上の）領域はプロシージャに入ってきたときに割り当てられ、出て行くときに解放される。C言語はこのような手法で実装されている典型例である。データとプロシージャ呼び出しに同じスタックを使うことは重大なセキュリティ問題を引き起こす可能性があり、プログラマはそのようなバグを作りこんで深刻なセキュリティ問題を発生させないように気をつける必要がある。
セキュリティ
たいていの場合、プロシージャ内のローカルなデータとプロシージャ呼び出しに関する情報は共通のスタックに格納されている。つまりプログラムは、プロシージャ呼び出しのリターンアドレスという極めて重要な情報を保持しているスタックに対して、データを出したり入れたりしているのである。データをスタック上の間違った領域に書き込んだり、大きすぎるデータをスタックに書き込んだりして、リターンアドレスが壊されると、プログラムが異常動作することになる（バッファオーバーラン攻撃）。
悪意ある者がこの種の実装を逆手にとって、入力データのサイズをチェックしていないプログラムに大きすぎるデータを入力したりする。そのようなプログラムはデータをスタック上に格納しようとしてリターンアドレスを壊してしまう。攻撃者は実験を繰り返し、リターンアドレスがスタック領域内（特に攻撃者の入力データが書き込まれた領域内）を指すようになる入力データのパターンを見つけ出し、許可されていない操作をするような命令列を入力データに含ませることでセキュリティを破る。こうした攻撃に対してプログラマはスタックの扱いに注意する必要がある。
スタック指向プログラミング言語
いくつかのプログラミング言語はスタック指向である。スタック指向言語は、基本操作（二つの数の加算、一文字表示など）でスタックから引数を取ってくるようになっていて、結果をスタックに返すようになっている言語である。
たいていは複数のスタックを使うよう設計されており、典型的なForthは、引数受け渡しのためのスタックとサブルーチンのリターンアドレスのためのスタックを持つ。PostScriptはリターンスタックとオペランドスタックを持ち、グラフィックス状態スタックと辞書スタックも持っている。日本語プログラミング言語のMindもForthベースである。
スタックマシン
機械語命令の体系がスタック指向プログラミング言語に類似している、すなわち、命令のオペランドがスタックであるマシンをスタックマシンと言う。最も有名なものとしてバロース B5000がある（B5000は、高水準言語（ALGOL）のサポートを目的として、前述のコールスタックもアーキテクチャでサポートしているが、コールスタックをアーキテクチャでサポートしている、という意味では「スタックマシン」の語は使わない）。
またx86等でも、スタックポインタ間接参照によってスタックマシンのように使うことはできるが、普通あまりスタックマシンとはしない。
多くの仮想機械もスタックマシンであり、例えばp-コードマシンやJava仮想マシンなどがある。x87の命令もスタックマシン的である。
これに対し、オペランドがレジスタのマシンをレジスタマシンと言う。多くの実機がレジスタマシンであるため実機に対してこの語が使われることは少ない。仮想機械ではLua 5の仮想機械がレジスタマシンである。
歴史
スタックを使った式評価方法を最初に提案したのはドイツの初期のコンピュータ科学者フリードリッヒ・L・バウアーであり、その業績により1988年、IEEE Computer Societyからコンピュータパイオニア賞を受賞した。
スタックと同じ種類の言葉
- スタックのページへのリンク
