スタック
ほとんどのコンパイルされたプログラムは実行時(ランタイム)環境においてコールスタックを使用し、プロシージャ/関数呼び出しに関する情報を格納するのに使っている。そして、呼び出し時のコンテキスト切り替えや呼び出し元への復帰の際に使用して、呼び出しの入れ子を可能としている。そのとき、呼び出される側と呼び出し側の間には引数や返り値をスタックにどう格納するかという規則が存在する。スタックは関数呼び出しの入れ子や再帰呼び出しを実現するための重要な要素となっている。この種のスタックはコンパイラが内部的に使用するもので、プログラマがこれを直接操作することはほとんど無い。
コールスタック内に関数の呼び出し毎に作られるフレームをスタックフレームと言い、それをたどって(トレースして)得られる呼び出しの情報をスタックトレースと言う。
プログラミング言語によっては、プロシージャ内のローカルなデータをスタックに格納する。ローカルなデータの(スタック上の)領域はプロシージャに入ってきたときに割り当てられ、出て行くときに解放される。C言語はこのような手法で実装されている典型例である。データとプロシージャ呼び出しに同じスタックを使うことは重大なセキュリティ問題を引き起こす可能性があり、プログラマはそのようなバグを作りこんで深刻なセキュリティ問題を発生させないように気をつける必要がある。
逆ポーランド記法を使用している電卓(Hewlett-Packardの関数電卓など)は、値を保持するためにスタック構造を使う。式は、前置記法、中置記法、後置記法のいずれかで表現される。ある記法から別の記法への変換にはスタックが必要となる。多くのコンパイラは低レベルな言語に翻訳する前の構文解析のためにスタックを使用する。多くのプログラミング言語は文脈自由言語であり、スタックベースの機械で構文解析することができる。ちなみに自然言語は文脈依存言語であり、スタックだけではその意味を解釈することはできない。
例えば、((1 + 2) * 4) + 3 という計算は、交換法則と括弧を優先するという前提で、次のように後置記法(逆ポーランド記法)に変換できる。
この式はスタックを使って左から右に以下のように評価できる。
オペランド(演算数)に遭遇したら push する。
演算子に遭遇したら、スタックから2つのオペランドを pop して演算を行い、
その解を push する。
具体的には以下のようになる。「スタック」は「操作」した後の状態を示している。
最終的な演算結果は 15 で、終了時にスタックのトップに置かれている。
トップの n 個のアイテムを回転するように入れ替える。例えば、n = 3 で、スタックに 1、2、3 が順に置かれているとき、この順番を 2、3、1 のように変化させる。この操作はバリエーションが多く、一般には left rotate(左回転)とright rotate(右回転)と呼ばれる操作を備えることが多い。
スタックは上に成長するようにイメージされることもあるし、左から右に成長するようにイメージされることもあり、トップという言い方ではなく右端と言ったりもする。このようなイメージはメモリ上のスタックの実際の構造とはあまり関係ない。right rotateと言ったとき、一番目の要素を三番目の位置に置き、二番目を一番目、三番目を二番目の位置に置く。これを二種類のイメージで表すと次のようになる。
スタックはコンピュータ内では通常、メモリセルのブロックで構成される。そのブロックの「底」は固定の位置にあり、スタックポインタが「トップ」のセルのアドレスを格納している。