スタック
出典: フリー百科事典『ウィキペディア（Wikipedia）』
スタックは情報工学における抽象データ型であり、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し (LIFO: Last In First Out; FILO: First In Last Out) の構造で保持するものである。スタックは現代のコンピュータシステムで非常に広範囲に使われており、一般にハードウェアとソフトウェアの機能の組合せによって実装される。
「スタックベース」のコンピュータシステムとは、一時情報をまずスタックに格納するシステムを意味する。逆にCPUのレジスタに格納するシステムを「レジスタベース」のコンピュータシステムと呼ぶ。
目次 |
[編集] 抽象データ型
抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。よく使われる比喩として、食堂にあるバネが仕込まれた台に皿や盆を積み重ねておく様子がある。そのようなスタックでは利用者は一番上（トップ）の皿だけにアクセスすることができ、それ以外の皿は隠されている。新たに皿が追加される（Pushされる）と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る（Popする）と、それを使うことができ、二番目の皿がスタックのトップとなる。二つの重要な原則がこの比喩で示されている。第一は後入れ先出し (LIFO: Last In First Out) の原則である。第二はスタックの中身が隠されているという点である。トップの皿だけが見えているため、三番目の皿がどういうものかを見るには一番目と二番目の皿を取り除かなければならない。
[編集] 他の操作
現代のコンピュータ言語では、スタックには「Push」と「Pop」以外の操作もできるように実装しているものが多い。スタックの長さがしばしばパラメータとして返される。他の補助操作として、「peek（のぞき見）」は現在のスタックのトップのノードを返すが、それをスタックから取り除かない。
[編集] 実装
n個の要素のスタックが必要とするメモリ容量はO(n)である。個々の操作に要する時間を O(1) （訳注：O(1)は定数すなわち一定の時間）とする実装は配列や線形リストを使っても簡単に実現できる。
多くのコンピュータ上ではポインタを用いて実装され、関数呼び出しでの引数渡し、に加えて関数の呼び出し元 (caller)アドレスの退避、割り込み発生時のプログラムカウンタ退避、レジスタ退避、などに利用される。
[編集] 関連するデータ構造
FIFO(First In First Out、先入れ先出し)の原則を持つデータ構造または抽象データ型はキューである。スタックとキューの操作を組み合わせて提供するものは両端キュー(deque)と呼ぶ。例えば、探索アルゴリズムでスタックを使うかキューを使うかによって、深さ優先探索（スタック使用）か幅優先探索（キュー使用）になる。
[編集] スタックの基本アーキテクチャ
典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。「スタックポインタ」（一般にハードウェアのレジスタが使われる）はスタック上で最も最近参照された位置を指している。スタックのサイズがゼロのとき、スタックポインタはスタックの基点を指す。
あらゆるスタックで実施可能な2つの操作は以下の通りである。
- Push操作：スタックポインタが指す場所にデータを格納し、そのデータのサイズのぶんだけスタックポインタをずらす。
- Pop操作：スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのぶんだけ（Pushとは逆方向に）ずらす。
スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。
例えば、あるスタックが1000番地から開始して、アドレスの小さい方向に延びていくとする。その場合、データは1000番地よりも小さい番地に格納され、スタックポインタはそれに伴って小さな番地を格納するようになる。そのスタックからデータをPopすると、スタックポインタに格納されているアドレスは大きくなる。
（初期状態の）スタックポインタはスタックの基点そのものではなく、その少し上か下（スタック成長方向に依存）の限界アドレスを指している場合もある。しかし、スタックポインタは基点を超えていくことはできない。換言すれば、スタックの基点が1000番地でスタックがアドレスの小さい方向（999番地、998番地など）に成長する場合、スタックポインタは決して1000番地を超えてはならない（1001番地や1002番地は不可）。Pop操作によってスタックポインタが基点を超えると「スタック・アンダーフロー」が発生する。逆にPush操作がスタックの最大許容範囲を超えてスタックポインタを操作することになるなら「スタック・オーバーフロー」が発生する。
スタックに強く依存している環境では、追加の操作を備えている場合がある。以下に例をあげる。
- Dup(licate): トップのアイテムを pop して2回 push する。これによって元のスタックトップのアイテムが2個スタックトップに存在することになる。
- Peek: トップのアイテムを pop するが、スタックポインタを変更せず、スタックのサイズも変化しない（つまり、アイテムはスタック上に残存する）。Top 操作と呼ぶことも多い。
- Swap または Exchange: スタックトップの2つのアイテム（つまり一番目と二番目）を入れ替える。
- Rotate: トップの n 個のアイテムを回転するように入れ替える。例えば、n=3 で、スタックに 1、2、3 が順に置かれているとき、この順番を 2、3、1 のように変化させる。この操作はバリエーションが多く、一般には left rotate（左回転）とright rotate（右回転）と呼ばれる操作を備えることが多い。
スタックは上に成長するようにイメージされることもあるし、左から右に成長するようにイメージされることもあり、トップという言い方ではなく右端と言ったりもする。このようなイメージはメモリ上のスタックの実際の構造とはあまり関係ない。right rotateと言ったとき、一番目の要素を三番目の位置に置き、二番目を一番目、三番目を二番目の位置に置く。これを二種類のイメージで表すと次のようになる。
apple banana banana ==right rotate==> cucumber cucumber apple
cucumber banana apple ==right rotate==> apple cucumber banana
スタックはコンピュータ内では通常、メモリセルのブロックで構成される。そのブロックの「底」は固定の位置にあり、スタックポインタが「トップ」のセルのアドレスを格納している。「底」とか「トップ」という用語はスタックがアドレスの大きくなる方向に成長するか、小さくなる方向に成長するかに関係なく使われる。
スタックへのアイテムの push により、そのアイテムのサイズのぶんだけスタックポインタがずらされ（増減はメモリ空間内のスタックの成長方向に依存する）、次のセルを指すようにして、新たなトップとなるアイテムをスタック領域にコピーする。詳細な実装に依存するが、push 操作を完了したときのスタックポインタの値はスタック上の次の未使用領域を指しているかもしれないし、現在のトップのアイテムを指しているかもしれない。スタックポインタが現在のトップのアイテムを指している場合、次回の push のときには最初にスタックポインタをずらさなければならない。逆にスタックポインタが次の未使用領域を指しているなら、次回の push のときには最後にスタックポインタをずらすことになる。
スタックの pop 操作は push の逆となる。Push とは逆の順番でスタックのトップのアイテムが取り出され、スタックポインタが更新される。
[編集] ハードウェアによるサポート
多くのCPUはスタックポインタとして使用可能なレジスタを持っている。x86のようなCPUはスタックポインタとしてレジスタを操作する命令も持っている。他のPDP-11や68000ファミリなどは、アドレッシングモードによって任意のレジスタをスタックポインタとして使用できるようになっている。Intel 8087シリーズの数値演算コプロセッサはスタックの一部としても普通のレジスタとしてもアクセス可能なレジスタ群を持っている。一部のマイクロコントローラ（例えばいくつかのPIC）は固定サイズのスタックを内蔵しており、その任意の位置に直接アクセスすることはできない。
スタックベースのマイクロプロセッサはプログラミング言語FORTHをマイクロコードレベルで実装することが多い。スタックを基本としたメインフレームやミニコンピュータも存在した。そういったマシンはスタックマシンと呼ばれ、最も有名なものとしてバロース B5000がある。
[編集] ソフトウェアによるサポート
高級言語で書かれたアプリケーションプログラムでは、スタックは配列や線形リストを使って効率的に実装可能である。LISPでは任意のリストに対して push や pop という関数を使用可能なので、スタックを実装する必要は無い。PostScriptもスタックを中心として設計されていて、プログラマーは直接スタックを見たり操作したりできる。
またLIFOの特徴から、逆ポーランド記法を用いたプログラミング言語Forthや、Mindなどでも使われている。
[編集] 応用例
スタックは情報処理の世界ではどこにでも存在する。
[編集] 式評価と構文解析
逆ポーランド記法を使用している電卓（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 で、終了時にスタックのトップに置かれている。
[編集] 実行時メモリ管理
いくつかのプログラミング言語はスタック指向である。スタック指向言語とは、基本操作（二つの数の加算、一文字表示など）でスタックから引数を取ってくるようになっていて、結果をスタックに返すようになっている言語である。例えば、PostScriptはリターンスタックとオペランドスタックを持ち、グラフィックス状態スタックと辞書スタックも持っている。
Forthは、引数受け渡しのためのスタックとサブルーチンのリターンアドレスのためのスタックを持つ。リターンスタックの使用は極めて一般的だが、人間に解読可能なプログラミング言語で引数スタックを別に持っているのは非常に珍しいため、Forthもスタック指向言語と呼ばれる。
多くの仮想機械もスタック指向であり、例えばp-コードマシンやJava仮想マシンなどがある。
ほとんどのコンピュータは実行時メモリ環境に特殊なスタック（コールスタック）を使用し、プロシージャ/関数呼び出しに関する情報を格納するのに使っている。そして、呼び出し時のコンテキスト切り替えや呼び出し元への復帰の際に使用して、呼び出しの入れ子を可能としている。そのとき、呼び出される側と呼び出し側の間には引数や返り値をスタックにどう格納するかという規則が存在する。スタックは関数呼び出しの入れ子や再帰呼び出しを実現するための重要な要素となっている。この種のスタックはコンパイラが内部的に使用するもので、プログラマがこれを直接操作することはほとんど無い。
プログラミング言語によっては、プロシージャ内のローカルなデータをスタックに格納する。ローカルなデータの（スタック上の）領域はプロシージャに入ってきたときに割り当てられ、出て行くときに解放される。C言語はこのような手法で実装されている典型例である。データとプロシージャ呼び出しに同じスタックを使うことは重大なセキュリティ問題を引き起こす可能性があり（後述）、プログラマはそのようなバグを作りこんで深刻なセキュリティ問題を発生させないように気をつける必要がある。
[編集] 探索問題の解法
探索問題を解くとき、総当り的か最適化されているかに関わらず、スタックを多大に必要とすることが多い。総当り探索の例としては、力まかせ探索(bruteforce)やバックトラッキングがある。最適探索の例としては、分岐限定法(branch and bound)やヒューリスティックによる解法がある。いずれのアルゴリズムでも、発見してはいるが探索していない探索ノードを覚えておくのにスタックが必要となる。スタックを使う以外の手法としては再帰を使う方法があるが、これはコンパイラが生成するコードが内部的に使用するスタックで代替しているだけである。スタックを使った探索は幅広く使われており、木構造の単純な幅優先探索や深さ優先探索から、クロスワードパズルを自動的に解くプログラムやコンピュータチェスゲームでも使われている。ある種の問題はキューなどの別のデータ構造を使って解くこともでき、探索順を変えたいときに有効である。
[編集] セキュリティ
ある種のコンピュータ環境ではスタックがセキュリティ上の弱点となっている。そのような環境向けに開発をするプログラマは細心の注意を払って落とし穴にはまらないようにしなければならない。
例えば、ある種のプログラミング言語ではプロシージャ内のローカルなデータとプロシージャ呼び出しに関する情報を共通のスタックに格納している。つまりプログラムは、プロシージャ呼び出しのリターンアドレスという極めて重要な情報を保持しているスタックに対して、データを出したり入れたりしているのである。データをスタック上の間違った領域に書き込んだり、大きすぎるデータをスタックに書き込んだりして、リターンアドレスが壊されると、プログラムが異常動作することになる。
悪意ある者がこの種の実装を逆手にとって、入力データのサイズをチェックしていないプログラムに大きすぎるデータを入力したりする。そのようなプログラムはデータをスタック上に格納しようとしてリターンアドレスを壊してしまう。攻撃者は実験を繰り返し、リターンアドレスがスタック領域内（特に攻撃者の入力データが書き込まれた領域内）を指すようになる入力データのパターンを見つけ出し、許可されていない操作をするような命令列を入力データに含ませることでセキュリティを破る。
これはバッファオーバーラン攻撃の一種で、最も一般的なプログラミング言語（C言語など）がそのようなスタック使用法（データとリターンアドレスの混在、データのサイズを暗黙のうちにチェックしない）であるため、セキュリティ問題の原因となることが非常に多い。プログラマはデータのサイズをチェックしないコードを書くことが多く、そのデータがスタックに格納される場合にセキュリティ問題が発生するのである。
[編集] 歴史
スタックを使った式評価方法を最初に提案したのはドイツの初期のコンピュータ科学者フリードリッヒ・L・バウアーであり、その業績により1988年、IEEE Computer Society Pioneer Award を受賞した。
