《アルゴリズムを学ぶ》7.スタック: 後入れ先出し（LIFO）

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

# 1. スタックの基本
Pythonでは、`list` を使って簡単にスタックを実装できます。

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



**＜基本実装＞**
```python
stack = []

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

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

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

# 2. スタックの応用
### 逆順の処理
スタックの性質を利用してリストや文字列の逆順処理をする。
```Python
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"
```

### 括弧の対応判定（バランス判定）
() {} [] の括弧が正しく対応しているかを判定する。
```Python
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 * のような後置記法の計算式を評価する。
```Python
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](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
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())
```
</details>

### 例題2. 括弧のバランス判定
**問題: () {} [] の括弧のペアが正しく対応しているかを判定せよ。**
> [参考： ABC319 C - Balanced Parentheses](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題3. 逆順出力
**問題: N 個の整数をスタックに格納し、逆順に出力せよ。**
> [参考： ABC318 B - Reverse Stack Output](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

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

while stack:
    print(stack.pop(), end=" ")
```
</details>

### 例題4. 逆ポーランド記法の計算
**問題: 3 4 + 2 * のような後置記法の式を評価せよ。**
> [参考： ABC310 C - Evaluate RPN](https://atcoder.jp/contests/abc310/tasks/abc310_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題5. 次に大きい数を見つける
**問題: N 個の数列 A が与えられる。各要素について、右側で最初に現れる「自分より大きい数」を出力せよ。**
> [参考： ABC321 D - Next Greater Element](https://atcoder.jp/contests/abc321/tasks/abc321_d)
<details><summary> 回答　</summary>

```python
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))
```
</details>