class ArrayStack:
    """動的配列ベースのスタック実装"""
 
    def __init__(self):
        self._data = []
 
    def push(self, value):
        """要素をトップに追加する: O(1) 償却"""
        self._data.append(value)
 
    def pop(self):
        """トップの要素を削除して返す: O(1) 償却"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()
 
    def peek(self):
        """トップの要素を参照する: O(1)"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]
 
    def is_empty(self):
        """空かどうか: O(1)"""
        return len(self._data) == 0
 
    def size(self):
        """要素数: O(1)"""
        return len(self._data)
 
    def __repr__(self):
        return f"ArrayStack({self._data})"
 
 
# 動作確認
if __name__ == "__main__":
    s = ArrayStack()
    s.push(10)
    s.push(20)
    s.push(30)
    print(s)            # ArrayStack([10, 20, 30])
    print(s.peek())     # 30
    print(s.pop())      # 30
    print(s.pop())      # 20
    print(s.size())     # 1
    print(s.is_empty()) # False
    print(s.pop())      # 10
    print(s.is_empty()) # True

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAX_SIZE 1024
 
typedef struct {
    int data[MAX_SIZE];
    int top;  /* 次に push する位置（=要素数） */
} Stack;
 
void stack_init(Stack *s) {
    s->top = 0;
}
 
bool stack_is_empty(const Stack *s) {
    return s->top == 0;
}
 
bool stack_is_full(const Stack *s) {
    return s->top == MAX_SIZE;
}
 
void stack_push(Stack *s, int value) {
    if (stack_is_full(s)) {
        fprintf(stderr, "Error: stack overflow\n");
        exit(EXIT_FAILURE);
    }
    s->data[s->top++] = value;
}
 
int stack_pop(Stack *s) {
    if (stack_is_empty(s)) {
        fprintf(stderr, "Error: stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->data[--s->top];
}
 
int stack_peek(const Stack *s) {
    if (stack_is_empty(s)) {
        fprintf(stderr, "Error: peek from empty stack\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top - 1];
}
 
int main(void) {
    Stack s;
    stack_init(&s);
 
    stack_push(&s, 10);
    stack_push(&s, 20);
    stack_push(&s, 30);
 
    printf("peek: %d\n", stack_peek(&s));  /* 30 */
    printf("pop:  %d\n", stack_pop(&s));   /* 30 */
    printf("pop:  %d\n", stack_pop(&s));   /* 20 */
    printf("empty: %s\n", stack_is_empty(&s) ? "true" : "false"); /* false */
 
    return 0;
}

class Node:
    """単方向連結リストのノード"""
    __slots__ = ('value', 'next')
 
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node
 
 
class LinkedStack:
    """連結リストベースのスタック実装"""
 
    def __init__(self):
        self._top = None
        self._size = 0
 
    def push(self, value):
        """新しいノードを先頭に追加: O(1) 最悪"""
        self._top = Node(value, self._top)
        self._size += 1
 
    def pop(self):
        """先頭ノードを削除して値を返す: O(1) 最悪"""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self._top.value
        self._top = self._top.next
        self._size -= 1
        return value
 
    def peek(self):
        """先頭ノードの値を参照: O(1)"""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._top.value
 
    def is_empty(self):
        return self._size == 0
 
    def size(self):
        return self._size
 
    def __iter__(self):
        """トップからボトムへの走査"""
        current = self._top
        while current is not None:
            yield current.value
            current = current.next
 
    def __repr__(self):
        return f"LinkedStack([{', '.join(str(v) for v in self)}])"
 
 
# 動作確認
if __name__ == "__main__":
    s = LinkedStack()
    for v in [10, 20, 30]:
        s.push(v)
    print(s)            # LinkedStack([30, 20, 10])
    print(s.peek())     # 30
    print(s.pop())      # 30
    print(s.size())     # 2

def factorial(n):
    """再帰的に階乗を計算する"""
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
print(factorial(5))  # 120

import sys
print(sys.getrecursionlimit())  # 1000
 
# 再帰上限の変更（推奨しない。末尾再帰最適化か反復に書き換えるべき）
# sys.setrecursionlimit(10000)

def is_valid_parentheses(s: str) -> bool:
    """
    括弧が正しく対応しているかを検証する。
    対応する括弧: (), [], {}
 
    アルゴリズム:
    1. 開き括弧が来たらスタックに push
    2. 閉じ括弧が来たら:
       a. スタックが空なら False（対応する開き括弧がない）
       b. トップの開き括弧と対応しなければ False
       c. 対応すれば pop
    3. 最後にスタックが空なら True（すべて対応した）
 
    計算量: O(n) 時間、O(n) 空間
    """
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
 
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # 対応する開き括弧がない
            if stack[-1] != pairs[char]:
                return False  # 括弧の種類が不一致
            stack.pop()
        # 括弧以外の文字は無視
 
    return len(stack) == 0  # 未対応の開き括弧が残っていないか
 
 
# テストケース
assert is_valid_parentheses("()") == True
assert is_valid_parentheses("()[]{}") == True
assert is_valid_parentheses("(]") == False
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("{[()]}") == True
assert is_valid_parentheses("") == True
assert is_valid_parentheses("(") == False
assert is_valid_parentheses(")") == False
print("All tests passed!")

def eval_rpn(tokens: list) -> int:
    """
    逆ポーランド記法の式を評価する。
 
    例: ["2", "1", "+", "3", "*"] → (2 + 1) * 3 = 9
 
    アルゴリズム:
    1. 数値ならスタックに push
    2. 演算子なら、スタックから2つ pop して計算し、結果を push
    3. 最後にスタックに残った1つの値が答え
 
    計算量: O(n) 時間、O(n) 空間
    """
    stack = []
    operators = {'+', '-', '*', '/'}
 
    for token in tokens:
        if token in operators:
            b = stack.pop()  # 2番目のオペランド（後に push されたもの）
            a = stack.pop()  # 1番目のオペランド（先に push されたもの）
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # C 言語風のゼロ方向への切り捨て
                stack.append(int(a / b))
        else:
            stack.append(int(token))
 
    return stack[0]
 
 
# テストケース
assert eval_rpn(["2", "1", "+", "3", "*"]) == 9
assert eval_rpn(["4", "13", "5", "/", "+"]) == 6
assert eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]) == 22
print("All RPN tests passed!")

class NaiveArrayQueue:
    """
    素朴な配列ベースキュー（問題あり）
    dequeue が O(n) であり、大量のデータには不適切
    """
 
    def __init__(self):
        self._data = []
 
    def enqueue(self, value):
        """末尾に追加: O(1) 償却"""
        self._data.append(value)
 
    def dequeue(self):
        """先頭から削除: *** O(n) *** — 全要素のシフトが発生"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.pop(0)  # これが O(n) のボトルネック！
 
    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self._data[0]
 
    def is_empty(self):
        return len(self._data) == 0
 
    def size(self):
        return len(self._data)

class CircularQueue:
    """
    循環バッファベースのキュー実装。
    固定サイズの配列で enqueue/dequeue を O(1) で実現する。
    """
 
    def __init__(self, capacity=16):
        self._data = [None] * capacity
        self._capacity = capacity
        self._front = 0   # 先頭要素のインデックス
        self._size = 0     # 現在の要素数
 
    def enqueue(self, value):
        """末尾に追加: O(1)"""
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        rear = (self._front + self._size) % self._capacity
        self._data[rear] = value
        self._size += 1
 
    def dequeue(self):
        """先頭から削除: O(1)"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._front]
        self._data[self._front] = None  # メモリリーク防止
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return value
 
    def peek(self):
        """先頭要素を参照: O(1)"""
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self._data[self._front]
 
    def is_empty(self):
        return self._size == 0
 
    def size(self):
        return self._size
 
    def _resize(self, new_capacity):
        """配列を拡張し、要素を再配置"""
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[(self._front + i) % self._capacity]
        self._data = new_data
        self._front = 0
        self._capacity = new_capacity
 
    def __repr__(self):
        items = []
        for i in range(self._size):
            items.append(str(self._data[(self._front + i) % self._capacity]))
        return f"CircularQueue([{', '.join(items)}])"
 
 
# 動作確認
if __name__ == "__main__":
    q = CircularQueue(capacity=4)
    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)
    print(q)           # CircularQueue([10, 20, 30])
    print(q.dequeue()) # 10
    print(q.dequeue()) # 20
    q.enqueue(40)
    q.enqueue(50)
    print(q)           # CircularQueue([30, 40, 50])

class Node:
    __slots__ = ('value', 'next')
 
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node
 
 
class LinkedQueue:
    """
    連結リストベースのキュー実装。
    head が先頭（dequeue 側）、tail が末尾（enqueue 側）。
    """
 
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
 
    def enqueue(self, value):
        """末尾に追加: O(1)"""
        new_node = Node(value)
        if self.is_empty():
            self._head = new_node
        else:
            self._tail.next = new_node
        self._tail = new_node
        self._size += 1
 
    def dequeue(self):
        """先頭から削除: O(1)"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._head.value
        self._head = self._head.next
        if self._head is None:
            self._tail = None  # キューが空になった
        self._size -= 1
        return value
 
    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self._head.value
 
    def is_empty(self):
        return self._size == 0
 
    def size(self):
        return self._size
 
 
# 動作確認
if __name__ == "__main__":
    q = LinkedQueue()
    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)
    print(q.dequeue())  # 10
    print(q.peek())     # 20
    print(q.size())     # 2

from collections import deque
 
# 基本操作
dq = deque()
 
# 右端の操作（スタック的・キュー的）
dq.append(1)       # 右に追加: O(1)
dq.append(2)
dq.append(3)
print(dq)           # deque([1, 2, 3])
 
val = dq.pop()      # 右から取出: O(1) → 3
print(dq)           # deque([1, 2])
 
# 左端の操作
dq.appendleft(0)    # 左に追加: O(1)
print(dq)           # deque([0, 1, 2])
 
val = dq.popleft()  # 左から取出: O(1) → 0
print(dq)           # deque([1, 2])
 
# 固定長 deque（古い要素を自動で捨てる）
history = deque(maxlen=3)
history.append("page1")
history.append("page2")
history.append("page3")
history.append("page4")  # "page1" が自動的に消える
print(history)      # deque(['page2', 'page3', 'page4'], maxlen=3)
 
# 回転
dq2 = deque([1, 2, 3, 4, 5])
dq2.rotate(2)       # 右に2つ回転
print(dq2)          # deque([4, 5, 1, 2, 3])
dq2.rotate(-2)      # 左に2つ回転
print(dq2)          # deque([1, 2, 3, 4, 5])

class MinHeap:
    """
    最小ヒープの完全な実装。
    配列で二分木を表現する。
 
    親: i → 子: 2i+1, 2i+2
    子: i → 親: (i-1)//2
    """
 
    def __init__(self):
        self._data = []
 
    def insert(self, value):
        """要素を追加: O(log n)"""
        self._data.append(value)
        self._sift_up(len(self._data) - 1)
 
    def extract_min(self):
        """最小要素を取り出す: O(log n)"""
        if not self._data:
            raise IndexError("extract from empty heap")
        min_val = self._data[0]
        last = self._data.pop()
        if self._data:
            self._data[0] = last
            self._sift_down(0)
        return min_val
 
    def peek(self):
        """最小要素を参照: O(1)"""
        if not self._data:
            raise IndexError("peek from empty heap")
        return self._data[0]
 
    def _sift_up(self, idx):
        """追加した要素を適切な位置まで上に移動"""
        while idx > 0:
            parent = (idx - 1) // 2
            if self._data[idx] < self._data[parent]:
                self._data[idx], self._data[parent] = self._data[parent], self._data[idx]
                idx = parent
            else:
                break
 
    def _sift_down(self, idx):
        """ルートの要素を適切な位置まで下に移動"""
        n = len(self._data)
        while True:
            smallest = idx
            left = 2 * idx + 1
            right = 2 * idx + 2
 
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
 
            if smallest != idx:
                self._data[idx], self._data[smallest] = self._data[smallest], self._data[idx]
                idx = smallest
            else:
                break
 
    def size(self):
        return len(self._data)
 
    def is_empty(self):
        return len(self._data) == 0
 
 
# 動作確認
if __name__ == "__main__":
    heap = MinHeap()
    for v in [5, 3, 8, 1, 2, 7]:
        heap.insert(v)
 
    result = []
    while not heap.is_empty():
        result.append(heap.extract_min())
    print(result)  # [1, 2, 3, 5, 7, 8] — ヒープソート

import heapq
 
# 最小ヒープ
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
 
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 1
print(heap[0])               # 3 (peek)
 
# 最大ヒープ（値を反転して格納）
max_heap = []
for val in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -val)
 
print(-heapq.heappop(max_heap))  # 5
print(-heapq.heappop(max_heap))  # 4
 
# n個の最大/最小要素
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(heapq.nlargest(3, data))   # [9, 6, 5]
print(heapq.nsmallest(3, data))  # [1, 1, 2]
 
# 既存のリストをヒープ化: O(n)
data = [5, 3, 8, 1, 2, 7]
heapq.heapify(data)
print(data)  # [1, 2, 7, 5, 3, 8]（ヒープ性質を満たす）

import heapq
from collections import defaultdict
 
def dijkstra(graph: dict, start: str) -> dict:
    """
    ダイクストラ法: 単一始点最短経路。
    graph: {node: [(neighbor, weight), ...]}
    戻り値: {node: 最短距離}
 
    計算量: O((V + E) log V)  （二分ヒープ使用時）
    """
    distances = {start: 0}
    pq = [(0, start)]  # (距離, ノード)
    visited = set()
 
    while pq:
        dist, node = heapq.heappop(pq)
 
        if node in visited:
            continue
        visited.add(node)
 
        for neighbor, weight in graph.get(node, []):
            new_dist = dist + weight
            if neighbor not in distances or new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
 
    return distances
 
 
# テスト用グラフ
#
#     A ---2--- B ---3--- D
#     |         |         |
#     4         1         1
#     |         |         |
#     C ---5--- E ---2--- F
#
graph = {
    'A': [('B', 2), ('C', 4)],
    'B': [('A', 2), ('D', 3), ('E', 1)],
    'C': [('A', 4), ('E', 5)],
    'D': [('B', 3), ('F', 1)],
    'E': [('B', 1), ('C', 5), ('F', 2)],
    'F': [('D', 1), ('E', 2)],
}
 
result = dijkstra(graph, 'A')
print(result)
# {'A': 0, 'B': 2, 'E': 3, 'C': 4, 'D': 5, 'F': 5}

import heapq
from collections import Counter
 
def top_k_frequent(nums: list, k: int) -> list:
    """
    出現頻度が高い上位 K 個の要素を返す。
 
    方法: サイズ K のミニヒープを維持する。
    計算量: O(n log k) — 全ソート O(n log n) より効率的（k << n の場合）
    """
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)
 
 
# テスト
nums = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4]
print(top_k_frequent(nums, 2))  # [3, 1] — 3が4回、1が3回

def next_greater_element(arr: list) -> list:
    """
    各要素について、右側にある最初の「より大きい要素」を求める。
    見つからなければ -1。
 
    例: [4, 2, 3, 5, 1] → [5, 3, 5, -1, -1]
 
    アルゴリズム:
    - スタックにインデックスを格納
    - スタックのトップより大きい要素が来たら、それがトップの NGE
    - 各要素は最大1回 push、1回 pop されるため O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # インデックスのスタック（値は単調減少に維持）
 
    for i in range(n):
        # 現在の要素がスタックのトップより大きい間、答えを確定
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
 
    return result
 
 
# テスト
print(next_greater_element([4, 2, 3, 5, 1]))
# [5, 3, 5, -1, -1]
 
print(next_greater_element([1, 3, 2, 4]))
# [3, 4, 4, -1]

def largest_rectangle_area(heights: list) -> int:
    """
    ヒストグラムにおける最大長方形の面積を求める。
 
    アルゴリズム: 単調増加スタック
    - 各バーについて、そのバーを高さとした長方形がどこまで
      左右に伸びるかを効率的に求める
    - スタックには単調増加のインデックスを維持
    - 現在のバーがスタックのトップより低い場合、トップを pop して
      面積を計算する
 
    計算量: O(n)
    """
    stack = []  # インデックスの単調増加スタック
    max_area = 0
    # 番兵として末尾に 0 を追加
    heights_ext = heights + [0]
 
    for i, h in enumerate(heights_ext):
        while stack and heights_ext[stack[-1]] > h:
            height = heights_ext[stack.pop()]
            # 幅: スタックが空なら左端から i まで、そうでなければ stack[-1]+1 から i まで
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
 
    return max_area
 
 
# テスト
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 10 (5x2)
print(largest_rectangle_area([2, 4]))               # 4

from collections import deque
 
def max_sliding_window(nums: list, k: int) -> list:
    """
    サイズ k のスライディングウィンドウの最大値を求める。
 
    アルゴリズム:
    - Deque にインデックスを格納し、値が単調減少になるよう維持
    - Deque の先頭が常にウィンドウ内の最大値のインデックス
    - ウィンドウから外れたインデックスは先頭から除去
    - 現在の値より小さい値は末尾から除去（もう最大値にならない）
 
    計算量: O(n) 時間、O(k) 空間
    """
    if not nums or k == 0:
        return []
 
    dq = deque()  # インデックスを格納（値は単調減少）
    result = []
 
    for i in range(len(nums)):
        # ウィンドウから外れたインデックスを先頭から除去
        while dq and dq[0] < i - k + 1:
            dq.popleft()
 
        # 現在の値より小さい値を末尾から除去
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
 
        dq.append(i)
 
        # ウィンドウが完成したら結果に追加
        if i >= k - 1:
            result.append(nums[dq[0]])
 
    return result
 
 
# テスト
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

class UndoRedoEditor:
    """
    2つのスタックによる Undo/Redo の実装。
 
    undo_stack: 実行した操作の履歴
    redo_stack: Undo した操作の履歴（Redo 用）
 
    新しい操作を実行すると redo_stack はクリアされる。
    """
 
    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []
 
    def type_text(self, new_text: str):
        """テキストを入力する"""
        self.undo_stack.append(self.text)
        self.redo_stack.clear()  # 新操作で Redo 履歴をクリア
        self.text = new_text
 
    def undo(self):
        """直前の状態に戻す"""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.text)
        self.text = self.undo_stack.pop()
 
    def redo(self):
        """Undo を取り消す"""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.text)
        self.text = self.redo_stack.pop()
 
 
# デモ
editor = UndoRedoEditor()
editor.type_text("Hello")
editor.type_text("Hello World")
editor.type_text("Hello World!")
print(editor.text)   # "Hello World!"
editor.undo()
print(editor.text)   # "Hello World"
editor.undo()
print(editor.text)   # "Hello"
editor.redo()
print(editor.text)   # "Hello World"

from collections import deque
 
def bfs(graph: dict, start: str) -> list:
    """
    幅優先探索。グラフの頂点を距離順（レベル順）に走査する。
 
    graph: {node: [neighbors]}
    戻り値: 訪問順のリスト
 
    計算量: O(V + E)
    """
    visited = {start}
    queue = deque([start])
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
 
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order
 
 
# テスト
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

def dfs_iterative(graph: dict, start: str) -> list:
    """
    スタックを使った反復的 DFS。
 
    注意: 再帰 DFS とは訪問順が微妙に異なる場合がある
    （隣接ノードの処理順が逆になるため）。
 
    計算量: O(V + E)
    """
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
 
        # 逆順で push すると、元の順序で処理される
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
 
    return order
 
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}
print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']

import heapq
from collections import Counter
 
def least_interval(tasks: list, n: int) -> int:
    """
    タスクスケジューラ: 同種のタスク間に最低 n インターバル必要。
    最短の総実行時間を求める。
 
    例: tasks=["A","A","A","B","B","B"], n=2
    → A B _ A B _ A B → 8
 
    アルゴリズム:
    1. 最大ヒープで残りカウントが多いタスクから処理
    2. クールダウン中のタスクは待機キューに入れる
    3. 待機キューからクールダウンが終わったタスクをヒープに戻す
    """
    count = Counter(tasks)
    max_heap = [-cnt for cnt in count.values()]
    heapq.heapify(max_heap)
 
    time = 0
    cooldown = []  # (再利用可能な時刻, 残りカウント)
 
    while max_heap or cooldown:
        time += 1
 
        if max_heap:
            cnt = heapq.heappop(max_heap) + 1  # 1つ消費（負数なので +1）
            if cnt < 0:  # まだ残っている
                cooldown.append((time + n, cnt))
 
        if cooldown and cooldown[0][0] == time:
            _, cnt = cooldown.pop(0)
            heapq.heappush(max_heap, cnt)
 
    return time
 
 
# テスト
print(least_interval(["A","A","A","B","B","B"], 2))  # 8
print(least_interval(["A","A","A","B","B","B"], 0))  # 6

import java.util.*;
 
public class StackQueueExample {
    public static void main(String[] args) {
        // スタック: ArrayDeque を推奨（Stack クラスは旧式で同期コストあり）
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek()); // 30
        System.out.println(stack.pop());  // 30
 
        // キュー: ArrayDeque を推奨
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        System.out.println(queue.peek()); // 10
        System.out.println(queue.poll()); // 10
 
        // 優先度キュー（最小ヒープ）
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        System.out.println(pq.poll()); // 1
 
        // 優先度キュー（最大ヒープ）
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(
            Comparator.reverseOrder()
        );
        maxPq.offer(5);
        maxPq.offer(1);
        maxPq.offer(3);
        System.out.println(maxPq.poll()); // 5
    }
}

#include <iostream>
#include <stack>
#include <queue>
#include <deque>
 
int main() {
    // スタック（デフォルトは deque ベース）
    std::stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);
    std::cout << st.top() << std::endl;  // 30
    st.pop();  // void を返す（値は返さない）
 
    // キュー（デフォルトは deque ベース）
    std::queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    std::cout << q.front() << std::endl;  // 10
    q.pop();
 
    // 優先度キュー（デフォルトは最大ヒープ）
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(3);
    std::cout << pq.top() << std::endl;  // 5
    pq.pop();
 
    // 最小ヒープ
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(5);
    min_pq.push(1);
    min_pq.push(3);
    std::cout << min_pq.top() << std::endl;  // 1
 
    return 0;
}

# NG: O(n) の dequeue
queue = [1, 2, 3, 4, 5]
val = queue.pop(0)  # O(n) — 全要素のシフトが発生
 
# 10万要素で pop(0) を繰り返すと:
# list.pop(0): 約 3.5 秒
# deque.popleft(): 約 0.01 秒
# 350倍の速度差!

from collections import deque
 
queue = deque([1, 2, 3, 4, 5])
val = queue.popleft()  # O(1)

# NG: 深い再帰で RecursionError
def sum_list(lst, index=0):
    if index == len(lst):
        return 0
    return lst[index] + sum_list(lst, index + 1)
 
# 1000 要素以下なら動くが、10000 要素で RecursionError
# sum_list(list(range(10000)))  # RecursionError!

# 方法1: 反復に書き換える
def sum_list_iterative(lst):
    total = 0
    for val in lst:
        total += val
    return total
 
# 方法2: 明示的なスタックを使う（複雑な再帰の場合）
def sum_list_stack(lst):
    stack = list(range(len(lst)))  # インデックスをスタックに
    total = 0
    while stack:
        i = stack.pop()
        total += lst[i]
    return total
 
# 方法3: Python の組み込み関数を使う
total = sum(range(10000))

// NG: Stack は Vector を継承しており、不要な同期コストがかかる
Stack<Integer> stack = new Stack<>();
stack.push(1);       // synchronized — シングルスレッドでも同期コスト発生
int val = stack.pop();
 
// さらに、Stack は Vector のメソッド（get(i), set(i, v) 等）を
// 継承しているため、スタック以外の操作ができてしまう
stack.add(0, 999);   // スタックの「底」に要素を挿入できてしまう（意味がない）

// OK: ArrayDeque をスタックとして使う
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
int val = stack.pop();
// ArrayDeque はスレッドセーフではないが、シングルスレッドでは高速
// また、任意位置へのアクセスメソッドを持たないため、抽象データ型として適切

# NG: チェックなしの pop
stack = []
val = stack.pop()  # IndexError: pop from empty list
 
# NG: キューでも同様
from collections import deque
queue = deque()
val = queue.popleft()  # IndexError: pop from an empty deque

# 方法1: 事前チェック
if stack:
    val = stack.pop()
 
# 方法2: 例外処理
try:
    val = stack.pop()
except IndexError:
    val = None  # デフォルト値
 
# 方法3: ラッパークラスで安全な操作を提供
class SafeStack:
    def __init__(self):
        self._data = []
 
    def pop(self, default=None):
        return self._data.pop() if self._data else default

stack = [42]
 
# peek と pop が同じ値を返すことを確認
assert stack[-1] == 42   # peek
val = stack.pop()         # pop
assert val == 42
assert len(stack) == 0    # 空になっている
 
# 空になった後の peek/pop はエラーになるべき
# stack[-1]  → IndexError
# stack.pop() → IndexError

# 閉じ括弧だけの入力
assert is_valid_parentheses(")") == False   # スタックが空の状態で pop を試みる
assert is_valid_parentheses("(") == False   # 開き括弧が残ったまま終了
 
# 空文字列
assert is_valid_parentheses("") == True     # 空は valid とみなす

# 容量 1 のキュー
q = CircularQueue(capacity=1)
q.enqueue(10)
# q.enqueue(20)  → リサイズが発生する
print(q.dequeue())  # 10
 
# 容量ちょうどまで埋めてから dequeue/enqueue を繰り返す
q2 = CircularQueue(capacity=4)
for i in range(4):
    q2.enqueue(i)
# 内部状態: [0, 1, 2, 3], front=0, size=4
 
q2.dequeue()  # 0 を取り出し → front=1, size=3
q2.dequeue()  # 1 を取り出し → front=2, size=2
 
q2.enqueue(4)  # rear = (2+2) % 4 = 0 に書き込み → 循環!
q2.enqueue(5)  # rear = (2+3) % 4 = 1 に書き込み
 
# 内部状態: [4, 5, 2, 3], front=2, size=4
# 論理的な順序: 2, 3, 4, 5

import heapq
 
# 同じ優先度の要素があるとき、Python の heapq はタプルの2番目以降を比較する
# 比較不可能なオブジェクトだとエラーになる
 
class Task:
    def __init__(self, name):
        self.name = name
 
# NG: Task オブジェクトは比較不可能
pq = []
heapq.heappush(pq, (1, Task("A")))
heapq.heappush(pq, (1, Task("B")))  # TypeError: '<' not supported
 
# 正しいアプローチ: 一意なカウンタを挟む
counter = 0
pq = []
 
def push_task(priority, task):
    global counter
    heapq.heappush(pq, (priority, counter, task))
    counter += 1
 
push_task(1, Task("A"))
push_task(1, Task("B"))  # 同じ優先度でもカウンタで区別される（FIFO 順）
priority, _, task = heapq.heappop(pq)
print(task.name)  # "A"（先に入れた方）

class QueueFromStacks:
    """
    2つのスタックでキューを実装する。
 
    エッジケース: dequeue 時に in_stack から out_stack への
    移し替えが発生する。最悪 O(n) だが償却 O(1)。
    """
 
    def __init__(self):
        self.in_stack = []   # enqueue 用
        self.out_stack = []  # dequeue 用
 
    def enqueue(self, value):
        """常に O(1)"""
        self.in_stack.append(value)
 
    def dequeue(self):
        """償却 O(1)、最悪 O(n)"""
        if not self.out_stack:
            if not self.in_stack:
                raise IndexError("dequeue from empty queue")
            # in_stack の全要素を out_stack に移す（順序が反転する）
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()
 
    def peek(self):
        if not self.out_stack:
            if not self.in_stack:
                raise IndexError("peek from empty queue")
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]
 
 
# エッジケースのテスト
q = QueueFromStacks()
 
# 1要素だけの場合
q.enqueue(1)
assert q.dequeue() == 1
 
# enqueue と dequeue を交互に
q.enqueue(1)
q.enqueue(2)
assert q.dequeue() == 1  # in_stack → out_stack 移し替え発生
q.enqueue(3)
assert q.dequeue() == 2  # out_stack にまだ 2 がある
assert q.dequeue() == 3  # in_stack → out_stack 移し替え発生