スタック - データサイエンス関連+αのメモ

スタック（stack） はデータの中で最後に入ったものが最初に取り出される 後入れ先出し（Last In First Out: LIFO） のデータ構造

操作：

push(x): スタックに要素xを追加する
pop(): スタックの最後の要素を取り出す

class Stack:

    def __init__(self):
        self.data = []

    def push(self, x):
        self.data.append(x)

    def pop(self):
        return self.data.pop(-1)


s = Stack()
s.push(1)
s.push(2)
s.pop()

2

計算量¶

スタックは内部的にリストや連結リストで実装されるため、末尾へのアクセスがO(1)になる。

操作	計算量	説明
`push`	$O(1)$	末尾への追加
`pop`	$O(1)$	末尾からの取り出し
peek（先頭参照）	$O(1)$	末尾要素の参照（取り出しなし）
`is_empty`	$O(1)$	空かどうかの確認
サイズ取得	$O(1)$	要素数の取得
探索	$O(n)$	特定の要素を見つけるには全走査が必要

Pythonのリストを使ったスタックでは、append と pop(-1) がともに償却 $O(1)$ 。

利用例¶

例1: 括弧の対応チェック¶

文字列中の ( と ) が正しく対応しているか確認する。

( が来たらスタックに積む
) が来たら、スタックが空なら対応なし → False、そうでなければ ( を取り出す
最後にスタックが空なら全て対応している

def is_balanced(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("((()))"))  # True
print(is_balanced("((()"))    # False
print(is_balanced(")("))      # False

True
False
False

例2: テキストエディタのUndo機能¶

文字の入力操作と 'undo' 操作をシミュレートする。入力した文字をスタックに積み、'undo' が来たら最後の文字を取り消す。

def simulate_editor(operations):
    stack = []
    for op in operations:
        if op == 'undo':
            if stack:
                stack.pop()
        else:
            stack.append(op)
    return ''.join(stack)

ops = ['h', 'e', 'x', 'undo', 'l', 'l', 'o']
print(simulate_editor(ops))  # "hello"  ('x' が取り消される)

hello