# ===== CodeLab: algo-stack-queue =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (python) -----
stack = []
stack.append(1)          # 入栈
stack.append(2)
stack.append(3)
top = stack[-1]          # 看栈顶:3,不弹出
popped = stack.pop()     # 出栈:3
print(top, popped, stack)  # 3 3 [1, 2]
print(len(stack) == 0)     # False,栈还没空

# ----- 片段 2 (python) -----
from collections import deque

q = deque()
q.append("a")            # 队尾入队
q.append("b")
q.append("c")
first = q.popleft()      # 队头出队
print(first, list(q))    # a ['b', 'c']
print(len(q))            # 2

# ----- 片段 3 (python) -----
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():   # 左括号:入栈
            stack.append(ch)
        elif ch in pairs:          # 右括号:必须匹配栈顶
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack               # 全部匹配完,栈应为空

print(is_valid("()[]{}"))    # True
print(is_valid("([)]"))      # False,交叉嵌套不合法
print(is_valid("(]"))        # False
print(is_valid("("))         # False,左括号没闭合

# ----- 片段 4 (python) -----
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b = stack.pop()   # 注意:先弹出的是右操作数
            a = stack.pop()
            if t == '+':
                stack.append(a + b)
            elif t == '-':
                stack.append(a - b)
            elif t == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))  # 除法向零取整
        else:
            stack.append(int(t))
    return stack[0]

print(eval_rpn(["2", "1", "+", "3", "*"]))   # 9
print(eval_rpn(["4", "13", "5", "/", "+"]))  # 6
print(eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*"]))  # 0

# ----- 片段 5 (python) -----
def next_greater(nums):
    n = len(nums)
    ans = [-1] * n
    stack = []               # 栈里存下标,值单调递减
    for i in range(n - 1, -1, -1):   # 从右往左扫描
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()      # 比当前元素小的,永远不可能是答案
        if stack:
            ans[i] = nums[stack[-1]]
        stack.append(i)
    return ans

print(next_greater([2, 1, 4, 3]))      # [4, 4, -1, -1]
print(next_greater([1, 3, 2, 5, 4]))   # [3, 5, 5, -1, -1]

# ----- 片段 6 (python) -----
from collections import deque

def max_sliding(nums, k):
    dq = deque()       # 存下标,值单调递减
    ans = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()           # 队尾比 x 小,淘汰
        dq.append(i)
        if dq[0] <= i - k:     # 队头滑出窗口
            dq.popleft()
        if i >= k - 1:         # 窗口成型后才记录
            ans.append(nums[dq[0]])
    return ans

print(max_sliding([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]