スタック

スタック︵英: stack︶は、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し︵LIFO: Last In First Out; FILO: First In Last Out︶の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。

抽象データ型[編集]

抽象データ型としてのスタックは、ノード︵何らかのデータを持ち、別のノードを指し示すことができる構造︶のコンテナ︵データを集めて格納する抽象データ型の総称︶であり、2つの基本操作プッシュ (push) とポップ (pop) を持つ。Pushは指定されたノードをスタックの先頭︵トップ︶に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。よく使われる比喩として、食堂にあるバネが仕込まれた台に皿や盆を積み重ねておく様子がある。そのようなスタックでは利用者は一番上︵トップ︶の皿だけにアクセスすることができ、それ以外の皿は隠されている。新たに皿が追加される︵Pushされる︶と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る︵Popする︶と、それを使うことができ、二番目の皿がスタックのトップとなる。二つの重要な原則がこの比喩で示されている。第一は後入れ先出し (LIFO: Last In First Out) の原則である。第二はスタックの中身が隠されているという点である。トップの皿だけが見えているため、三番目の皿がどういうものかを見るには一番目と二番目の皿を取り除かなければならない。

他の操作[編集]

多くのスタック実装では﹁Push﹂と﹁Pop﹂以外の操作をサポートしている。スタックの大きさ︵長さ︶、﹁現在のスタックのトップのノードを返すが、それをスタックから取り除かない﹂Peek操作、トップではなくn番目の参照・操作、入れ替え等も実装されることもある。連結リストではO(n)だが配列による実装ではO(1)、その逆、等色々な場合がある。

実装[編集]

n 個の要素のスタックが必要とするメモリ容量はO (n )、つまりスタック長に比例する。個々の操作が一定時間O (1) で完了する実装は配列や連結リストを使っても簡単に実現できる。実装の詳細については別に議論する。

ハードウェア[編集]

ハードウェアによるスタックの実装法には、主に次の2つがある。 ●シフトレジスタ等により、ハードウェア的に直接、プッシュ・ポップできるようにしたもの ●メモリ上の領域と、スタックポインタによるもの前者は、たとえば4004の﹁3段のスタック﹂がそのようなものである。後者は多くのコンピュータが持っている。以下これについて述べる。

典型的なスタック[編集]

典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。﹁スタックポインタ﹂︵一般にハードウェアのレジスタが使われる︶はスタック内で最も後で参照された位置を指している。スタック長がゼロのとき、スタックポインタはスタックの基点を指す。あらゆるスタックで実施可能な2つの操作は以下の通りである。 Push操作格納したいデータのサイズのぶんだけスタックポインタをずらし、ずらした後のスタックポインタが指している場所にデータを格納する。 Pop操作スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのサイズのぶんだけ︵Pushとは逆方向に︶ずらす。スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。昔のコンピュータで、ヒープ領域をアドレスの小さいほうから大きいほうへ伸ばし、スタックを大きいほうから小さいほうへ伸ばす︵そのようにすると、メモリが足りない場合はどちらを伸ばす余裕もなく、完全にメモリを使い切って計算続行不可能となる︶という設計にした名残りから、アドレスの大きいほうから小さいほうへ伸びるものが多いが、PA-RISCは逆である。例えば、あるスタックが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                      apple
banana    ===left rotate==>   cucumber
apple                         banana

スタックはコンピュータ内では通常、メモリセルのブロックで構成される。そのブロックの﹁底﹂は固定の位置にあり、スタックポインタが﹁トップ﹂のセルのアドレスを格納している。﹁底﹂とか﹁トップ﹂という用語はスタックがアドレスの大きくなる方向に成長するか、小さくなる方向に成長するかに関係なく使われる。スタックへのアイテムの push により、そのアイテムのサイズのぶんだけスタックポインタがずらされ︵増減はメモリ空間内のスタックの成長方向に依存する︶、次のセルを指すようにして、新たなトップとなるアイテムをスタック領域にコピーする。詳細な実装に依存するが、push 操作を完了したときのスタックポインタの値はスタック上の次の未使用領域を指しているかもしれないし、現在のトップのアイテムを指しているかもしれない。スタックポインタが現在のトップのアイテムを指している場合、次回の push のときには最初にスタックポインタをずらさなければならない。逆にスタックポインタが次の未使用領域を指しているなら、次回の push のときには最後にスタックポインタをずらすことになる。スタックの pop 操作は push の逆となる。Push とは逆の順番でスタックのトップのアイテムが取り出され、スタックポインタが更新される。

コールスタック[編集]

詳細は「コールスタック」を参照

以上のようなスタックは、特にコールスタックに使われる。

具体例[編集]

多くのプロセッサはスタックポインタとして使用可能なレジスタを持っている。x86のようなプロセッサは専用のスタックポインタレジスタを持っている。他のPDP-11や68000ファミリなどは、アドレッシングモードによって任意のレジスタをソフトウェア的にスタックポインタとして使用できるようになっているが、普通は割込みやJSR命令が操作するR6レジスタやA7レジスタを使う。RISCの多くはそのように特別扱いされるようなレジスタを持たず、どのレジスタをスタックポインタとして使うかは通常ABIで決めており、ソフトウェアでスタック処理をおこなう。Intel 8087シリーズの数値演算コプロセッサはスタックアーキテクチャである。一部のマイクロコントローラ︵例えばいくつかのPIC︶は固定サイズのスタックを内蔵しており、その任意の位置に直接アクセスすることはできない。以上のようなスタックポインタによるスタックではなく、直接ハードウェアで実現したスタックを持つコンピュータもある。 ●Computer Cowboys MuP21 ●Harris RTX line ●Novix NC4016 なお、以上のようなスタックがあるコンピュータをスタックマシンとするのは間違いである。詳細は後述のスタックマシンについての記述を参照すること。

ソフトウェア[編集]

この節では、抽象データ型としてのスタックのソフトウェアによる実装について述べる。高水準言語では、スタックは配列や線形リストを使って効率的に実装可能である。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の命令もスタックマシン的である。これに対し、オペランドがレジスタのマシンをレジスタマシンと言う。多くの実機がレジスタマシンであるため実機に対してこの語が使われることは少ない。仮想機械ではLua5の仮想機械がレジスタマシンである。

歴史[編集]

スタックを使った式評価方法を最初に提案したのはドイツの初期のコンピュータ科学者フリードリッヒ・L・バウアーであり、その業績により1988年、IEEE Computer Societyからコンピュータパイオニア賞を受賞した。