概要（スタックは「最後に入れたものが最初に出る」LIFOの基本構造）
スタックは LIFO（Last-In, First-Out）で要素を管理するデータ構造です。直前の操作を元に戻す「Undo」、括弧の整合チェック、深さ優先探索（DFS）、再帰の置き換えなどで活躍します。Pythonではリスト（append/pop）で簡単に作れますが、より安全・高速にしたい場面では collections.deque（両端 O(1)）や並行処理では queue.LifoQueue（スレッドセーフ）を使います。最重要ポイントは「push/pop の基本」「空スタックの扱い」「性能差の理解」の3つです。
基本の使い方（ここが重要）
リストで最短スタック（単純・高速・実用的）
stack = [] # 空スタックを作る
stack.append(1) # push
stack.append(2)
x = stack.pop() # pop → 2（最後に入れたものから出る）
print(x, stack) # 2 [1]
list.append と list.pop() は末尾の操作が平均 O(1) で高速です。空スタックで pop すると IndexError になるので、事前チェックか try/except で安全に扱います。
if stack:
val = stack.pop()
else:
# 空のときの処理
...
deque で「大量 push/pop」でも安定（両端 O(1)）
from collections import deque
stack = deque()
stack.append("A") # push
stack.append("B")
print(stack.pop()) # 'B'
deque は両端操作が O(1) で安定しています。リストでも末尾なら高速ですが、より大きなデータや両端操作を混ぜる処理には deque が安心です。
LifoQueue でスレッドセーフ（並行処理用）
from queue import LifoQueue
stack = LifoQueue(maxsize=100)
stack.put(1) # push（ブロッキング）
stack.put(2)
print(stack.get()) # 2（pop 相当）
複数スレッドからの push/pop（put/get）を安全に行いたいときに使います。空や満杯でのブロッキング、timeout、例外（Empty/Full）を理解して使い分けます。
重要ポイントの深掘り（安全性・性能・設計の癖）
空スタックの扱い（例外か条件分岐か）
- pop 前に「空でないか」をチェックするのが基本。例外を使うなら try/except で IndexError（list）や Empty（LifoQueue）を捕まえます。
- アルゴリズムでは「空なら失敗」などの定義を明示し、戻り値や例外ポリシーを統一すると読みやすくなります。
def safe_pop(stack: list):
if not stack:
return None
return stack.pop()
性能の見方（末尾操作は O(1)、先頭は避ける）
- リストで先頭を pop(0) すると前詰めが発生し O(n) で遅い。スタックは「末尾を使う」ことが鉄則。
- 大量の push/pop を繰り返すなら deque がより安定。並行処理は LifoQueue 一択。
再帰の置き換え（コールスタックの外側で制御）
- 再帰は「関数呼び出しのスタック」を使います。深い再帰で限界に当たりやすい処理は、明示的スタックで反復に置き換えると安全です。
- DFS、式評価、括弧チェックなどは「自前スタック」にするだけで制御が明快になります。
実務での使いどころ（Undo、括弧整合、探索、パース）
Undo/Redo の基本パターン
undo_stack = []
redo_stack = []
def do(action):
result = action()
undo_stack.append(action) # 実行した操作を積む
redo_stack.clear() # 新規操作で redo は無効化
def undo():
if not undo_stack:
return
action = undo_stack.pop()
action.undo()
redo_stack.append(action)
def redo():
if not redo_stack:
return
action = redo_stack.pop()
action()
undo_stack.append(action)
「実行→undo に積む」「undo→redo に積む」「redo→undo に戻す」の往復が基本線です。
括弧の整合チェック（スタックの定番）
def is_balanced(s: str) -> bool:
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_balanced("{[()]}")) # True
print(is_balanced("{[(])}")) # False
「開く括弧を積み、閉じる括弧で対応を確認して取り出す」。最後にスタックが空なら整合しています。
深さ優先探索（再帰の置き換え）
def dfs(graph, start):
seen = set()
stack = [start]
order = []
while stack:
v = stack.pop()
if v in seen:
continue
seen.add(v)
order.append(v)
# 隣接を積む（順序で探索形が変わる）
for w in reversed(graph.get(v, [])):
if w not in seen:
stack.append(w)
return order
G = {"A":["B","C"], "B":["D"], "C":[],"D":[]}
print(dfs(G, "A")) # ['A','B','D','C']
「未訪問を積む→取り出して処理」の形にすると、再帰なしで DFS を制御できます。
文字列の逆転（学習用ミニパターン）
def reverse_str(s: str) -> str:
stack = list(s)
out = []
while stack:
out.append(stack.pop())
return "".join(out)
print(reverse_str("abc")) # 'cba'
「積んでから pop で取り出す」だけで LIFO の挙動を体感できます。
よくある落とし穴の回避（設計・テスト・拡張）
取り出し順を間違えない（末尾のみ）
スタックは末尾操作に限定します。先頭を触ると性能も意味も崩れます。push=append、pop=pop() を習慣化します。
空での pop を必ずテストする
ユニットテストで「空のときの pop」「1件だけ積んだとき」「大量 push/pop」を必ず通します。境界条件のバグが最も多い箇所です。
上限サイズや監視が必要ならクラス化する
API と不変条件（空、満杯、サイズ取得など）をまとめてクラスにすると、誤用が減ります。
class Stack:
def __init__(self, limit=None):
self._data = []
self._limit = limit
def push(self, x):
if self._limit is not None and len(self._data) >= self._limit:
raise OverflowError("stack full")
self._data.append(x)
def pop(self):
if not self._data:
raise IndexError("pop from empty stack")
return self._data.pop()
def __bool__(self):
return bool(self._data)
def __len__(self):
return len(self._data)
例題で身につける（定番から一歩先まで）
例題1：括弧・演算子の簡易パース（RPN 変換の前段）
def infix_tokens(expr: str):
buf = ""
for ch in expr:
if ch.isdigit():
buf += ch
else:
if buf:
yield buf; buf = ""
if ch.strip():
yield ch
if buf:
yield buf
print(list(infix_tokens("3+(4*5)-6"))) # ['3','+','(','4','*','5',')','-','6']
例題2：Undo 風の文字列編集
text = []
undo = []
def add(ch):
text.append(ch); undo.append(("del",))
def delete():
if text: undo.append(("add", text.pop()))
def apply(action):
if action[0] == "del":
if text: text.pop()
else:
text.append(action[1])
add("A"); add("B"); delete() # text=['A']
act = undo.pop(); apply(act) # redo 的に戻す → text=['A','B']
print("".join(text))
例題3：DFS（迷路の道探索の骨格）
def path_exists(grid, start, goal):
H, W = len(grid), len(grid[0])
def inside(r, c): return 0 <= r < H and 0 <= c < W
stack, seen = [start], set()
while stack:
r, c = stack.pop()
if (r, c) == goal: return True
if (r, c) in seen: continue
seen.add((r, c))
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if inside(nr, nc) and grid[nr][nc] == 0:
stack.append((nr, nc))
return False
例題4：LifoQueue で並行安全なスタック
from queue import LifoQueue, Empty
from threading import Thread
stack = LifoQueue()
def producer():
for i in range(5):
stack.put(i)
stack.put(None) # 終了シグナル
def consumer():
while True:
x = stack.get()
if x is None:
break
print("pop:", x)
Thread(target=producer).start()
Thread(target=consumer).start()
まとめ
スタックは「最後に入れたものが最初に出る」LIFO を実現する最小の構造です。Python では list の append/pop で即戦力、量が多い・両端操作なら deque、並行処理なら LifoQueue。最重要ポイントは「末尾操作に限定」「空スタックの扱いの明文化」「必要ならクラス化して不変条件を守る」こと。Undo、括弧整合、DFS、再帰置換などの定番を手で実装して、境界条件（空・1件・大量）をテストしながら“スタック思考”を体に入れると、アルゴリズムと設計の理解が一段深まります。