4-3. データ構造 スタック
本記事では、データ構造のスタックについて解説します。
スタックとは
スタック（stack)は、後から入れたデータを先に取り出すという操作で扱われるデータ構造です。
この操作は、後入れ先出し（LIFO）と呼ばれます。
スタックの基本操作
push
スタックにデータを格納することで、プッシュダウン、又は単にプッシュといいます。データは下から上に積み上げるイメージで考えると良いでしょう。
pop
スタックからデータを取り出すことで、ポップアップ、または単にポップといいます。データは上から順に取り出していくイメージで考えると良いでしょう。
配列を用いたスタックの表現
スタックも、リストと同じように配列を使って実現することができます。スタックにデータを格納したり、取り出したりする対象になるのは端のデータだけです。また、出し入れするたびに配列内のデータが増えたり減ったりしますので、その時点でどこまでデータが格納されているか（端がどこか）を示す一の情報が必要です。この位置をスタックポインタといいます。
スタックにデータを格納し続けていくと、スタック用の配列の大きさを越えてしまうことがあります。このような状態をスタックオーバーフローと呼び、エラー処理をする必要があります。
補足
スタック（Stack）の用途と具体例
スタックは 後入れ先出し（LIFO: Last In, First Out） のデータ構造であり、次のような場面でよく使われます。
① 関数呼び出しの管理（再帰処理）
用途
プログラムが関数を呼び出すとき、呼び出し元の情報（戻りアドレスや引数など）を記憶 する必要があります。これを管理するために スタックが使われます。
具体例
再帰関数（Factorialやフィボナッチ数列の計算）
関数のネストが深くなるプログラム（深い階層の関数呼び出し）
例（C言語の関数呼び出しスタック）
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
factorial(3) を呼び出すと
factorial(3) → factorial(2) → factorial(1) → factorial(0)
戻るときに、スタックのデータを順に取り出して処理
② 式の評価（逆ポーランド記法）
用途
計算機が数式を評価するとき、スタックを使って演算子の順番を管理 することが多いです。
具体例
逆ポーランド記法（RPN: Reverse Polish Notation）
数式の解析（コンパイラ、計算機）
例
(3 + 4) * 5
通常の表記（中置記法）ではなく、逆ポーランド記法では
3 4 + 5 *
3 をスタックにプッシュ
4 をスタックにプッシュ
+ で 3 と 4 を取り出して計算 → 7 をプッシュ
5 をスタックにプッシュ
* で 7 と 5 を取り出して計算 → 35
③ 戻る・進む機能（ブラウザの履歴管理）
用途
Webブラウザの「戻る」「進む」ボタンの動作をスタックで管理します。
具体例
Webブラウザの履歴
ページA → ページB → ページC へ移動
「戻る」ボタンを押すとページCをPOPし、ページBを表示
「進む」ボタンを押すとページCをPUSHし、次のページを表示
④ 深さ優先探索（DFS: Depth First Search）
用途
スタックを使うと 再帰を使わずに深さ優先探索（DFS） を実装できます。
具体例
迷路探索
グラフ探索
AIの探索アルゴリズム
例（迷路探索のスタックを用いた実装）
maze = [[0, 1, 0, 0],
[0, 1, 0, 1],
[0, 0, 0, 1],
[1, 1, 0, 0]]
stack = [(0, 0)] # スタート地点
while stack:
x, y = stack.pop()
print(f"現在の位置: ({x}, {y})")
# 移動可能ならスタックにプッシュ
⑤ Undo（元に戻す機能）
用途
テキストエディタや画像編集ソフトの 「元に戻す」 機能は、スタックを使って操作履歴を記録します。
具体例
テキストエディタ（VSCode, Word）
画像編集ソフト（Photoshop）
例（テキストエディタの動作）
「Hello」入力 → スタックに「Hello」をプッシュ
「World」入力 → スタックに「World」をプッシュ
「元に戻す（Undo）」 → 「World」をポップして消す
以上です。