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 の際に取り出した値を出力せよ。
回答
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. 括弧のバランス判定
問題: () {} [] の括弧のペアが正しく対応しているかを判定せよ。
回答
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 個の整数をスタックに格納し、逆順に出力せよ。
回答
N = int(input())
stack = list(map(int, input().split()))
while stack:
print(stack.pop(), end=" ")
例題4. 逆ポーランド記法の計算
問題: 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]
expression = input()
print(evaluate_rpn(expression))
例題5. 次に大きい数を見つける
問題: N 個の数列 A が与えられる。各要素について、右側で最初に現れる「自分より大きい数」を出力せよ。
回答
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))