スタック

スタック#

スタック（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
Contents