Chaba Content Site

スタック (Stacks)

2025-08-17

スタックの学習ノート

スタックって「配列の機能制限版」だと最初は思ってた。でも、制限があるからこそ便利な場面があることを知って目から鱗だった。

スタックとは

LIFO（Last In First Out） - 最後に入れたものが最初に出てくる。皿の積み重ねをイメージすると分かりやすい。

     ↓ push(4)
    [4]  ← top（一番上）
    [3]
    [2]
    [1]  ← bottom（一番下）
     ↑ pop()すると4が出てくる

なぜスタックが必要？

最初「配列でよくない？」と思ったけど：

  1. 意図が明確になる：「LIFO で使う」ことが保証される
  2. 間違いを防げる：真ん中にアクセスできないから、バグりにくい
  3. 特定の問題に最適：括弧の対応、関数呼び出し、Undo機能など

基本操作

Push - 要素を追加 O(1)

class Stack:
    def __init__(self):
        self.items = []  # 内部は動的配列
    
    def push(self, item):
        """スタックの頂上に要素を追加"""
        self.items.append(item)  # O(1) amortized

Pop - 要素を取り出す O(1)

def pop(self):
    """スタックの頂上から要素を取り出す"""
    if not self.is_empty():
        return self.items.pop()  # O(1)
    raise IndexError("Pop from empty stack")

def is_empty(self):
    """スタックが空かチェック"""
    return len(self.items) == 0

Peek/Top - 要素を見るだけ O(1)

def peek(self):
    """頂上の要素を見る（取り出さない）"""
    if not self.is_empty():
        return self.items[-1]  # O(1)
    raise IndexError("Peek from empty stack")

完全なスタック実装

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """要素を追加"""
        self.items.append(item)
    
    def pop(self):
        """要素を取り出す"""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """頂上を見る"""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]
    
    def is_empty(self):
        """空かチェック"""
        return len(self.items) == 0
    
    def size(self):
        """サイズを返す"""
        return len(self.items)
    
    def __str__(self):
        return str(self.items)

# 使用例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack)         # [1, 2]

スタックの実践的な使い方

1. 文字列を逆順にする

def reverse_string(s):
    stack = Stack()
    
    # 全文字をプッシュ
    for char in s:
        stack.push(char)
    
    # ポップして逆順を作る
    reversed_str = ""
    while not stack.is_empty():
        reversed_str += stack.pop()
    
    return reversed_str

print(reverse_string("hello"))  # "olleh"

2. 括弧の対応チェック（超重要！）

def is_valid_parentheses(s):
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty():
                return False
            if stack.pop() != pairs[char]:
                return False
    
    return stack.is_empty()

# テスト
print(is_valid_parentheses("()[]{}"))    # True
print(is_valid_parentheses("([)]"))      # False
print(is_valid_parentheses("{[()]}"))    # True

3. 式の評価（逆ポーランド記法）

def eval_rpn(tokens):
    """
    逆ポーランド記法を評価
    例: ["2", "1", "+", "3", "*"] → (2+1)*3 = 9
    """
    stack = Stack()
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            
            if token == '+':
                stack.push(a + b)
            elif token == '-':
                stack.push(a - b)
            elif token == '*':
                stack.push(a * b)
            elif token == '/':
                stack.push(int(a / b))  # 整数除算
        else:
            stack.push(int(token))
    
    return stack.pop()

print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9

4. 関数呼び出しスタック（コールスタック）

def factorial(n):
    """
    再帰関数の裏側でスタックが使われてる
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# 実行時のスタックの様子：
# factorial(4)
#   → factorial(3)
#     → factorial(2)
#       → factorial(1)
#       ← 1
#     ← 2 * 1 = 2
#   ← 3 * 2 = 6
# ← 4 * 6 = 24

5. Undo機能の実装

class TextEditor:
    def __init__(self):
        self.text = ""
        self.history = Stack()
    
    def write(self, text):
        self.history.push(self.text)  # 現在の状態を保存
        self.text += text
    
    def undo(self):
        if not self.history.is_empty():
            self.text = self.history.pop()
    
    def get_text(self):
        return self.text

# 使用例
editor = TextEditor()
editor.write("Hello")
editor.write(" World")
print(editor.get_text())  # "Hello World"
editor.undo()
print(editor.get_text())  # "Hello"

よくある面接問題

Min Stack（最小値を O(1) で取得）

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []  # 最小値を記録するスタック
    
    def push(self, x):
        self.stack.append(x)
        
        # 最小値スタックを更新
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    
    def pop(self):
        if self.stack:
            x = self.stack.pop()
            if x == self.min_stack[-1]:
                self.min_stack.pop()
            return x
    
    def top(self):
        if self.stack:
            return self.stack[-1]
    
    def get_min(self):
        if self.min_stack:
            return self.min_stack[-1]

# テスト
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
min_stack.push(2)
min_stack.push(1)
print(min_stack.get_min())  # 1
min_stack.pop()
print(min_stack.get_min())  # 2

時間計算量まとめ

操作時間計算量備考
PushO(1)末尾に追加
PopO(1)*空チェック必要
Peek/TopO(1)*空チェック必要

*空のスタックに対する操作はエラー

ハマったポイント・気づき

  1. 空スタックのチェックを忘れる

    # ダメな例
def bad_pop(self):
    return self.items.pop()  # 空だとエラー！

  2. スタックで解ける問題の見分け方

    • 後入れ先出しが必要
    • ネスト構造がある（括弧、タグなど）
    • 履歴を戻る必要がある
    • 再帰をループに変換したい

  3. Pythonでスタックを使う時のTips

    # リストをスタックとして使う
stack = []
stack.append(1)  # push
stack.pop()      # pop

# collectionsのdequeも使える（両端操作が速い）
from collections import deque
stack = deque()
stack.append(1)
stack.pop()

実装の選択肢

# 1. リストを使う（最も簡単）
stack = []

# 2. dequeを使う（大量データで若干速い）
from collections import deque
stack = deque()

# 3. 自作クラス（意図が明確）
class Stack:
    # 上記の実装
    pass

まとめ

次は連結リストについて学んだことをまとめる予定

Tags: スタック LIFO 配列