《アルゴリズムを学ぶ》11.Deque: 両端キューの操作を学ぶ。

# Overview
Deque（両端キュー: Double-Ended Queue） は、前後の両方で要素の追加・削除が可能なデータ構造 。
[1.Dequeの基本](#1-dequeの基本)
[2.Dequeの応用](#2-dequeの応用)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. Dequeの基本
キューやスタックの機能を統合しており、データの処理を柔軟に行うことができる。
Pythonでは`collections.deque`を使うと、高速な両端キューの操作が可能。

|操作名	|説明	|Pythonの`deque`操作|
|--|--|--|
|前に追加（appendleft）	|左端に要素を追加	|`deque.appendleft(x)`
|後ろに追加（append）	|右端に要素を追加	|`deque.append(x)`
|前から削除（popleft）	|左端の要素を削除	|`deque.popleft()`
|後ろから削除（pop）	|右端の要素を削除	|`deque.pop()`
|長さ取得（len）	|Deque の長さを取得	|`len(deque)`
|回転（rotate）	|要素を右（+n）または左（-n）へシフト	|`deque.rotate(n)`


**＜基本実装＞**
```python
from collections import deque

dq = deque()

# 右端に追加
dq.append(1)
dq.append(2)

# 左端に追加
dq.appendleft(3)

# 右端と左端の要素を削除
print(dq.pop())      # 2
print(dq.popleft())  # 3

# Deque の状態
print(dq)  # deque([1])
```
ポイント:
・スタックやキューとしても使える
・appendleft と popleft を使うと左端でも操作できる

# 2. Dequeの応用
### (1) スライディングウィンドウの最小・最大
Deque を使うと、スライディングウィンドウの最大値や最小値を $𝑂(𝑁)$で求める ことができます。

例：N 個の整数から、K 要素のウィンドウごとに最大値を求める。

```python
from collections import deque

def sliding_window_max(arr, k):
    dq = deque()
    res = []

    for i, num in enumerate(arr):
        while dq and arr[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        if dq[0] == i - k:
            dq.popleft()

        if i >= k - 1:
            res.append(arr[dq[0]])

    return res

A = [1, 3, -1, -3, 5, 3, 6, 7]
K = 3
print(sliding_window_max(A, K))  # [3, 3, 5, 5, 6, 7]
```
ポイント:
・単調デック（Monotonic Deque）を使い $𝑂(𝑁)$で解ける
・Deque を用いることで効率的に要素を管理

### (2) 回転（rotate）
Deque はリストの回転を効率的に行える。

```python
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)  # 右に2回回転
print(dq)  # deque([4, 5, 1, 2, 3])
```
ポイント:
・通常のリストの insert() を使うより速い。

### (3) 文字列の回文判定
Dequeを使うと 前後から比較しながら文字列の回文判定ができる。

```python
def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False
```
ポイント:
・前後の文字を効率的に比較
・リストよりも削除が速い


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

### 例題1. バブルソートの基本実装
**問題: N 個の整数が与えられる。それらをバブルソートで昇順に並べ替えよ。**
> [参考： ABC333 B - Basic Bubble Sort](https://atcoder.jp/contests/abc333/tasks/abc333_b)
<details><summary> 回答　</summary>

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(*bubble_sort(A))
```
</details>

### 例題1. 両端キューの基本操作
**問題: N 個の操作（APPEND x / APPENDLEFT x / POP / POPLEFT）が与えられる。Deque を適切に管理し、操作を実行せよ。**
> [参考： ABC321 B - Simple Deque](https://atcoder.jp/contests/abc321/tasks/abc321_b)
<details><summary> 回答　</summary>

```python
from collections import deque

N = int(input())
dq = deque()

for _ in range(N):
    cmd = input().split()
    if cmd[0] == "APPEND":
        dq.append(int(cmd[1]))
    elif cmd[0] == "APPENDLEFT":
        dq.appendleft(int(cmd[1]))
    elif cmd[0] == "POP" and dq:
        dq.pop()
    elif cmd[0] == "POPLEFT" and dq:
        dq.popleft()

print(*dq)
```
</details>

### 例題2. 回文判定
**問題: 文字列 S が与えられる。Deque を使って回文かどうかを判定せよ。**
> [参考： ABC319 C - Palindrome Check](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
from collections import deque

def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return "No"
    return "Yes"

S = input()
print(is_palindrome(S))
```
</details>

### 例題3. Deque を使ったスライディングウィンドウ最大値
**問題: N 個の数列 A が与えられ、各 K 要素のウィンドウごとに最大値を求めよ。**
> [参考： ABC318 B - Sliding Window Maximum](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
from collections import deque

def sliding_window_max(arr, k):
    dq = deque()
    res = []

    for i, num in enumerate(arr):
        while dq and arr[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        if dq[0] == i - k:
            dq.popleft()

        if i >= k - 1:
            res.append(arr[dq[0]])

    return res

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(*sliding_window_max(A, K))
```
</details>

### 例題4. Deque を使った回転操作
**問題: N 個の整数が与えられる。それを K 回右回転した後の配列を出力せよ。**
> [参考： ABC322 C - Rotate List](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
from collections import deque

N, K = map(int, input().split())
A = deque(map(int, input().split()))

A.rotate(K)
print(*A)
```
</details>

### 例題5. 双方向探索
**問題: グラフが与えられ、最短経路を BFS（幅優先探索）で求めよ。**
> [参考： ABC320 B - Bidirectional BFS](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = {start: 0}

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor)

    return visited

# 入力処理
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N+1)}

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

print(bfs(1, graph))
```
</details>