スタック

抽象データ型

抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、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) で完了する実装は配列や連結リストを使っても簡単に実現できる。
実装の詳細については別に議論する。

関連するデータ構造

FIFO(First In First Out、先入れ先出し)の原則を持つデータ構造または抽象データ型はキューである。スタックとキューの操作を組み合わせて提供するものは両端キュー(deque)と呼ぶ。例えば、探索アルゴリズムでスタックを使うかキューを使うかによって、深さ優先探索（スタック使用）か幅優先探索（キュー使用）になる。

コールスタック

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

ソフトウェア

この節では、抽象データ型としてのスタックのソフトウェアによる実装について述べる。
高水準言語では、スタックは配列や線形リストを使って効率的に実装可能である。LISPでは任意のリストに対して push や pop に相当する関数（consがpush、cdrがpopである）を使用可能なので、スタックを実装する必要は無い。

探索問題の解法

探索問題を解くとき、総当り的か最適化されているかに関わらず、スタックを多大に必要とすることが多い。総当り探索の例としては、力まかせ探索やバックトラッキングがある。最適探索の例としては、分枝限定法(branch and bound)やヒューリスティックによる解法がある。いずれのアルゴリズムでも、発見してはいるが探索していない探索ノードを覚えておくのにスタックが必要となる。スタックを使う以外の手法としては再帰を使う方法があるが、これはコンパイラが生成するコードが内部的に使用するスタックで代替しているだけである。スタックを使った探索は幅広く使われており、木構造の単純な幅優先探索や深さ優先探索から、クロスワードパズルを自動的に解くプログラムやコンピュータチェスゲームでも使われている。ある種の問題はキューなどの別のデータ構造を使って解くこともでき、探索順を変えたいときに有効である。

プログラミング言語処理系の実装

ほとんどのコンパイルされたプログラムは実行時（ランタイム）環境においてコールスタックを使用し、プロシージャ/関数呼び出しに関する情報を格納するのに使っている。そして、呼び出し時のコンテキスト切り替えや呼び出し元への復帰の際に使用して、呼び出しの入れ子を可能としている。そのとき、呼び出される側と呼び出し側の間には引数や返り値をスタックにどう格納するかという規則が存在する。スタックは関数呼び出しの入れ子や再帰呼び出しを実現するための重要な要素となっている。この種のスタックはコンパイラが内部的に使用するもので、プログラマがこれを直接操作することはほとんど無い。
コールスタック内に関数の呼び出し毎に作られるフレームをスタックフレームと言い、それをたどって（トレースして）得られる呼び出しの情報をスタックトレースと言う。
プログラミング言語によっては、プロシージャ内のローカルなデータをスタックに格納する。ローカルなデータの（スタック上の）領域はプロシージャに入ってきたときに割り当てられ、出て行くときに解放される。C言語はこのような手法で実装されている典型例である。データとプロシージャ呼び出しに同じスタックを使うことは重大なセキュリティ問題を引き起こす可能性があり、プログラマはそのようなバグを作りこんで深刻なセキュリティ問題を発生させないように気をつける必要がある。

セキュリティ

たいていの場合、プロシージャ内のローカルなデータとプロシージャ呼び出しに関する情報は共通のスタックに格納されている。つまりプログラムは、プロシージャ呼び出しのリターンアドレスという極めて重要な情報を保持しているスタックに対して、データを出したり入れたりしているのである。データをスタック上の間違った領域に書き込んだり、大きすぎるデータをスタックに書き込んだりして、リターンアドレスが壊されると、プログラムが異常動作することになる（バッファオーバーラン攻撃）。
悪意ある者がこの種の実装を逆手にとって、入力データのサイズをチェックしていないプログラムに大きすぎるデータを入力したりする。そのようなプログラムはデータをスタック上に格納しようとしてリターンアドレスを壊してしまう。攻撃者は実験を繰り返し、リターンアドレスがスタック領域内（特に攻撃者の入力データが書き込まれた領域内）を指すようになる入力データのパターンを見つけ出し、許可されていない操作をするような命令列を入力データに含ませることでセキュリティを破る。こうした攻撃に対してプログラマはスタックの扱いに注意する必要がある。

スタック指向プログラミング言語

いくつかのプログラミング言語はスタック指向である。スタック指向言語は、基本操作（二つの数の加算、一文字表示など）でスタックから引数を取ってくるようになっていて、結果をスタックに返すようになっている言語である。
たいていは複数のスタックを使うよう設計されており、典型的なForthは、引数受け渡しのためのスタックとサブルーチンのリターンアドレスのためのスタックを持つ。PostScriptはリターンスタックとオペランドスタックを持ち、グラフィックス状態スタックと辞書スタックも持っている。日本語プログラミング言語のMindもForthベースである。

スタックマシン

機械語命令の体系がスタック指向プログラミング言語に類似している、すなわち、命令のオペランドがスタックであるマシンをスタックマシンと言う。最も有名なものとしてバロース B5000がある（B5000は、高水準言語（ALGOL）のサポートを目的として、前述のコールスタックもアーキテクチャでサポートしているが、コールスタックをアーキテクチャでサポートしている、という意味では「スタックマシン」の語は使わない）。
またx86等でも、スタックポインタ間接参照によってスタックマシンのように使うことはできるが、普通あまりスタックマシンとはしない。
多くの仮想機械もスタックマシンであり、例えばp-コードマシンやJava仮想マシンなどがある。x87の命令もスタックマシン的である。
これに対し、オペランドがレジスタのマシンをレジスタマシンと言う。多くの実機がレジスタマシンであるため実機に対してこの語が使われることは少ない。仮想機械ではLua 5の仮想機械がレジスタマシンである。

歴史

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