Overview

スタック（Stack）は「後入れ先出し（LIFO: Last In, First Out）」のデータ構造。
1.スタックの基本
 2.スタックの応用
 3.典型問題を解いてみる

1. スタックの基本

Pythonでは、list を使って簡単にスタックを実装できます。

操作名	説明	Python のリスト操作
プッシュ（push）	スタックに要素を追加	`stack.append(x)`
ポップ（pop）	スタックの一番上の要素を取り出す	`stack.pop()`
トップ（peek）	スタックの一番上の要素を参照（削除しない）	`stack[-1]`
空判定（is_empty）	スタックが空かを判定	'len(stack) == 0'

＜基本実装＞

stack = []

# プッシュ（要素の追加）
stack.append(1)
stack.append(2)
stack.append(3)

# ポップ（要素の取り出し）
print(stack.pop())  # 3
print(stack.pop())  # 2

# スタックの状態確認
print(stack)  # [1]

2. スタックの応用

逆順の処理

スタックの性質を利用してリストや文字列の逆順処理をする。

def reverse_string(s):
    stack = list(s)  # 文字列をリストに変換（スタックとして扱う）
    reversed_s = "".join(stack.pop() for _ in range(len(stack)))
    return reversed_s

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

括弧の対応判定（バランス判定）

() {} [] の括弧が正しく対応しているかを判定する。

def is_balanced(s):
    stack = []
    pair = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in "({[":
            stack.append(char)  # 開く括弧をプッシュ
        elif char in ")}]":
            if not stack or stack.pop() != pair[char]:  # 対応する括弧があるか確認
                return False
    return not stack  # スタックが空なら正しい

print(is_balanced("({[]})"))  # True
print(is_balanced("({[})"))   # False

計算式の評価（逆ポーランド記法 / RPN)

3 4 + 2 * のような後置記法の計算式を評価する。

def evaluate_rpn(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))  # 数値はスタックにプッシュ
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a // b)  # 整数除算
    return stack[0]  # 結果を返す

print(evaluate_rpn("3 4 + 2 *"))  # 14

3. 典型問題を解いてみる

例題1. スタックの基本操作

問題: N 個の操作（PUSH x / POP）が与えられる。スタックを適切に管理し、POP の際に取り出した値を出力せよ。

参考： ABC320 B - Simple Stack

回答　

N = int(input())
stack = []

for _ in range(N):
    cmd = input().split()
    if cmd[0] == "PUSH":
        stack.append(int(cmd[1]))
    elif cmd[0] == "POP" and stack:
        print(stack.pop())

例題2. 括弧のバランス判定

問題: () {} [] の括弧のペアが正しく対応しているかを判定せよ。

参考： ABC319 C - Balanced Parentheses

回答　

def is_balanced(s):
    stack = []
    pair = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack or stack.pop() != pair[char]:
                return "No"
    return "Yes" if not stack else "No"

s = input()
print(is_balanced(s))

例題3. 逆順出力

問題: N 個の整数をスタックに格納し、逆順に出力せよ。

参考： ABC318 B - Reverse Stack Output

回答　

N = int(input())
stack = list(map(int, input().split()))

while stack:
    print(stack.pop(), end=" ")

例題4. 逆ポーランド記法の計算

問題: 3 4 + 2 * のような後置記法の式を評価せよ。

参考： ABC310 C - Evaluate RPN

回答　

def evaluate_rpn(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a // b)
    return stack[0]

expression = input()
print(evaluate_rpn(expression))

例題5. 次に大きい数を見つける

問題: N 個の数列 A が与えられる。各要素について、右側で最初に現れる「自分より大きい数」を出力せよ。

参考： ABC321 D - Next Greater Element

回答　

def next_greater_element(arr):
    stack = []
    res = [-1] * len(arr)
    
    for i in range(len(arr)-1, -1, -1):
        while stack and stack[-1] <= arr[i]:
            stack.pop()
        if stack:
            res[i] = stack[-1]
        stack.append(arr[i])
    
    return res

N = int(input())
A = list(map(int, input().split()))
print(*next_greater_element(A))