スタック（Stack）：上に積む、上から取る
LIFO（後入れ先出し）という約束 — undo・関数呼び出し・括弧チェックでの使いどころと、C・Java・C#・Python での書き方
スタックとは：皿の山
スタックは「積む」と「上から取る」だけができる、制限つきの入れ物です。皿の山を想像してください。新しい皿は一番上に置き（push）、取るときも一番上から取ります（pop）。途中の皿を抜くことはできません。
push(40) pop() -> 40 | ^ v | +------+ top -> | 40 | <- 最後に入れたものが、最初に出る +------+ | 30 | +------+ | 20 | +------+ | 10 | <- 最初に入れたものは、最後まで残る +------+ LIFO: Last-In, First-Out（後入れ先出し）
最後に入れたものが最初に出てくる — この規律を LIFO（Last-In, First-Out：後入れ先出し）と呼びます。push も pop も山の一番上だけを見ればよいので、どちらも O(1) です。
「途中の皿を抜けない」のは不便に聞こえますが、むしろ逆です。できることを絞ったおかげで、「直前にやったことへ戻る」という動きを、間違いようのない形で表現できます。
どこで使われているか
いちばん身近な例は関数呼び出しです。関数が関数を呼ぶたびに「呼び出し元へ戻る場所」がスタックに積まれ、return のたびに上から降ろされます。再帰（関数が自分自身を呼ぶこと）が深すぎたときに起きる「スタックオーバーフロー」は、この山が積み上がりすぎたというエラーです。
エディタの undo やブラウザの「戻る」も、「直前の状態を積んでおき、上から戻す」スタックそのものです。アルゴリズムでは、深さ優先探索（DFS）の「行けるところまで行き、行き止まりなら一歩戻る」という動きを支えます。
小さな実例として、括弧の対応チェックを見てみましょう。開き括弧が来たら積み、閉じ括弧が来たら上から降ろして、対応が取れているかを確かめます。
"( [ ] ( ) )" を左から 1 文字ずつ読む: 読む 操作 スタックの中身 ( push '(' ( [ push '[' ( [ ] pop '[' と対応 ( ( push '(' ( ( ) pop '(' と対応 ( ) pop '(' と対応 （空） 読み終えたときに空 -> すべての括弧が正しく対応している
実装：中身は配列でも連結リストでもよい
前のページで見たどちらの構造でも、スタックは作れます。動的配列なら末尾を「山の上」にすれば push / pop ともならし O(1)。連結リストなら先頭を「山の上」にすれば、どちらも O(1) です。
つまりスタックは「どう持つか」ではなく「どう使わせるか」の決まりです。中身の構造と、外に見せる約束（インターフェース）が別物だという関係が、ここにも現れています。
各言語での書き方：C・Java・C#・Python
C の例
/* C: 標準のスタックはない — 配列と添字で自作する */ int stack[100]; int top = 0; /* 次に積む場所 */ void push(int v) { stack[top++] = v; } int pop(void) { return stack[--top]; }
C には標準のスタックがありません。配列と「次に積む場所」を指す添字だけで自作します — スタックがいかに小さな約束でできているかが分かります（あふれ・空の検査は省略しています）。
Java の例
// 定石: Deque インターフェース + ArrayDeque 実装 Deque<String> stack = new ArrayDeque<>(); stack.push("a"); // 積む stack.push("b"); String top = stack.pop(); // "b" — 最後に積んだものが出る // java.util.Stack は Vector（同期付きの旧式動的配列）の遺産。 // 公式ドキュメントも Deque の使用を推奨している。
注意点が 1 つあります。Java には java.util.Stack という名前そのままのクラスがありますが、これは初期の Java の遺産です。このクラスは Vector（全メソッドが同期化された旧式の動的配列）を継承していて、公式ドキュメント自身が「Deque インターフェースを使うほうがよい」と案内しています。
現在の定石は、ArrayDeque を push / pop で使うことです。中身は次のページで見るリングバッファで、高速で、余計な同期コストもありません。
C# の例
// C#: 専用の Stack<T> クラスがある（中身は配列） var stack = new Stack<string>(); stack.Push("a"); // 積む stack.Push("b"); string top = stack.Pop(); // "b" — 最後に積んだものが出る
C# には専用の Stack<T> クラスが標準で用意されています（中身は配列）。メソッド名も Push / Pop / Peek と、概念そのままです。
Python の例
# Python: list をそのままスタックとして使う（中身は動的配列） stack = [] stack.append("a") # push stack.append("b") top = stack.pop() # "b" — 末尾（山の上）から取り出す
Python では list をそのままスタックとして使うのが、公式ドキュメントも推奨する定石です。末尾への append / pop はならし O(1) — 動的配列の末尾を「山の上」にする、上の「実装」の節で見た構成です。
まとめ
スタックは push / pop だけの制限つきの入れ物。規律は LIFO（後入れ先出し）で、どちらの操作も O(1)。
「直前に戻る」動きの標準部品：関数呼び出し・undo・深さ優先探索・括弧チェック。
中身は配列でも連結リストでも作れる — スタックは構造そのものではなく「使わせ方の約束」。
多くの言語に定番がある：Java は ArrayDeque（java.util.Stack は遺産）、C# は Stack<T>、Python は list。C では配列と添字で自作する。