女性向けエンジニアスクール
3秒でわかる
最後に入れたものを最初に取り出すデータ構造。積んだ順に戻る性質を使い、関数の呼び出し管理や取り消し操作、括弧の対応確認に使われます。
30秒図解
もう少し詳しく
どういうものか
スタックは、データを積み上げて、上から順に取り出すデータ構造です。積む操作を push、取り出す操作を pop と呼びます。取り出せるのは常に一番上、つまり最後に入れた要素です。この性質を LIFO（Last In First Out、後入れ先出し）と言います。
途中の要素を直接抜くことはできません。制限が強い代わりに、実装が単純で、push と pop はどちらも O(1) で終わります。
なぜ必要か
「直前に戻る」処理は、そのままスタックの形になります。関数を呼ぶと現在地を積み、終わったら取り出して戻る。エディタの取り消しは、操作を積んでおいて上から戻す。ブラウザの戻るボタンも同じです。
プログラムの実行中に出る RecursionError や StackOverflowError は、この積み上げ場所が上限を超えた状態です。スタックを知っていると、エラーメッセージの意味がそのまま読めます。
具体例
stack = []
stack.append("a") # push
stack.append("b")
stack.append("c")
print(stack.pop()) # c 最後に入れたものが出る
print(stack[-1]) # b 取り出さずに一番上を見る (peek)
def is_balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(is_balanced("a(b[c]{d})")) # True
print(is_balanced("a(b[c)]")) # False括弧の対応確認は、スタックが最も自然に効く例です。
つまずきやすいところ
IndexError になります。pop の前に空かどうかを確かめますlist.pop(0) は要素をずらすため O(n) です。末尾を使うか collections.deque を使います似た用語との違い
| 構造 | 取り出す順 | 主な用途 |
|---|---|---|
| スタック | 後入れ先出し | 呼び出し管理、取り消し、括弧照合 |
| キュー | 先入れ先出し | 順番待ち、幅優先探索 |
| 優先度付きキュー | 優先度の高い順 | 最短経路、スケジューリング |
覚え方
食堂の重ねたトレーです。最後に置いたトレーが一番上にあり、次に取られるのもそれです。
