push （プッシュ） およびpop （ポップ） のスタックの単純な表現スタックの単純な表現 スタック （英 : stack ）は、コンピュータ で用いられる基本的なデータ構造 のひとつで、データ を後入れ先出し （LIFO : Last In First Out; FILO : First In Last Out）の構造で保持するものである。抽象データ型 としてのそれを指すこともあれば、その具象を指すこともある。
特にその具象としては、割込み やサブルーチン を支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタ によるコールスタック をメモリ 上に持っていることが多い。
抽象データ型 としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ (push ) とポップ (pop ) を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。
よく使われる比喩として、食堂にあるバネが仕込まれた台に皿や盆を積み重ねておく様子がある。そのようなスタックでは利用者は1番上（トップ）の皿だけにアクセスすることができ、それ以外の皿は隠されている。新たに皿が追加される（Pushされる）と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る（Popする）と、それを使うことができ、2番目の皿がスタックのトップとなる。二つの重要な原則がこの比喩で示されている。第1は後入れ先出し (LIFO : Last In First Out) の原則である。第2はスタックの中身が隠されているという点である。トップの皿だけが見えているため、3番目の皿がどういうものかを見るには1番目と2番目の皿を取り除かなければならない。
多くのスタック実装では「Push」と「Pop」以外の操作をサポートしている。スタックの大きさ（長さ）の取得、「現在のスタックのトップのノードを返すが、それをスタックから取り除かない」Peek操作、トップではなくn ランダウの記号 を使ったオーダー記法で表すと、連結リスト ではO (n )配列 による実装ではO (1)
スタックが必要とするメモリ容量はスタック長すなわち要素数n O (1)
実装の詳細については別に議論する。
FIFO (First In First Out、先入れ先出し) の原則を持つデータ構造または抽象データ型はキュー である。スタックとキューの操作を組み合わせて提供するものは両端キュー (deque) と呼ぶ。例えば、探索アルゴリズム でスタックを使うかキューを使うかによって、深さ優先探索 （スタック使用）か幅優先探索 （キュー使用）になる。
ハードウェアによるスタックの実装法には、主に次の2つがある。
前者は、たとえばIntel 4004 の「3段のスタック」がそのようなものである。後者は多くのコンピュータが持っている。以下これについて述べる。
典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。「スタックポインタ」（一般にハードウェアのレジスタが使われる）はスタック内で最も後で参照された位置を指している。スタック長がゼロのとき、スタックポインタはスタックの基点を指す。
あらゆるスタックで実施可能な2つの操作は以下の通りである。
Push操作
格納したいデータのサイズのぶんだけスタックポインタをずらし、ずらした後のスタックポインタが指している場所にデータを格納する。
Pop操作
スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのサイズのぶんだけ（Pushとは逆方向に）ずらす。 スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。
昔のコンピュータで、ヒープ領域 をアドレスの小さいほうから大きいほうへ伸ばし、スタックを大きいほうから小さいほうへ伸ばす（そのようにすると、メモリが足りない場合はどちらを伸ばす余裕もなく、完全にメモリを使い切って計算続行不可能となる）という設計にした名残りから、アドレスの大きいほうから小さいほうへ伸びるものが多いが、PA-RISC は逆である。
例えば、あるスタックが1000番地から開始して、アドレスの小さい方向に延びていくとする。その場合、データは1000番地よりも小さい番地に格納され、スタックポインタはそれに伴って小さな番地を格納するようになる。そのスタックからデータをPopすると、スタックポインタに格納されているアドレスは大きくなる。
（初期状態の）スタックポインタはスタックの基点そのものではなく、その少し上か下（スタック成長方向に依存）の限界アドレスを指している場合もある。しかし、スタックポインタは基点を超えていくことはできない。換言すれば、スタックの基点が1000番地でスタックがアドレスの小さい方向（999番地、998番地など）に成長する場合、スタックポインタは決して1000番地を超えてはならない（1001番地や1002番地は不可）。Pop操作によってスタックポインタが基点を超えると「スタック・アンダーフロー」が発生する。逆にPush操作がスタックの最大許容範囲を超えてスタックポインタを操作することになるなら「スタック・オーバーフロー」が発生する。
スタックに強く依存している環境では、追加の操作を備えている場合がある。以下に例をあげる。
Dup (duplicate)
トップのアイテムを pop して2回 push する。これによって元のスタックトップのアイテムが2個スタックトップに存在することになる。
Peek
トップのアイテムを pop するが、スタックポインタを変更せず、スタックのサイズも変化しない（つまり、アイテムはスタック上に残存する）。Top 操作と呼ぶことも多い。
Swap または Exchange
スタックトップの2つのアイテム（つまり1番目と2番目）を入れ替える。
Rotate
トップの n 個のアイテムを回転するように入れ替える。例えば、n = 3 で、スタックに 1、2、3 が順に置かれているとき、この順番を 2、3、1 のように変化させる。この操作はバリエーションが多く、一般には left rotate （左回転）とright rotate （右回転）と呼ばれる操作を備えることが多い。 スタックは上に成長するようにイメージされることもあるし、左から右に成長するようにイメージされることもあり、トップという言い方ではなく右端と言ったりもする。このようなイメージはメモリ上のスタックの実際の構造とはあまり関係ない。right rotate と言ったとき、1番目の要素を3番目の位置に置き、2番目を1番目、3番目を2番目の位置に置く。これを2種類のイメージで表すと次のようになる。
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である）を使用可能なので、スタックを実装する必要は無い。
スタック専用のコンテナ （コレクション）型を使わず、動的配列やリストのような他のコンテナ型をスタック代わりに使うことも当然できるが、実装が隠蔽・抽象化されていたり、インデックスによるランダムアクセスや任意位置に対する要素の追加・削除のような一部の操作が制限されていたりする専用のコンテナ型をあえて使ったほうが、コードの意図が明瞭になり、メンテナンス性が向上するなどの利点がある。
ジェネリックプログラミング に対応したオブジェクト指向の静的型付け 言語では、任意のデータ型Tを要素とするスタックを定義できるようになっていることも多い。C++ ではStandard Template Library にstd::stack<T, Container>が用意されている。std::stackはテンプレート第2引数に内部実装コンテナを指定することができ、デフォルトでは両端キューstd::dequeが使われるが、動的配列std::vectorまたは双方向連結リストstd::listを指定することも可能である[ 1]
逆ポーランド記法 を使用している電卓（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 からコンピュータパイオニア賞 を受賞した。
