# ===== CodeLab: 数据结构与算法入门 =====
# 来源: https://aoerliang.dpdns.org/articles/algorithms-basics
# 以下代码片段按文章出现顺序拼接, 共 4 段

# ----- 片段 1 (python) -----
arr = [10, 20, 30, 40]
print(arr[2])      # 30, 直接寻址 O(1)
arr.append(50)     # 尾部追加, 均摊 O(1)
arr.insert(0, 5)   # 头部插入, 需要搬移所有元素 O(n)
arr.remove(20)     # 删除同样需要搬移 O(n)

# ----- 片段 2 (python) -----
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# 构建: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 遍历
cur = head
while cur:
    print(cur.val, end=" ")
    cur = cur.next   # 1 2 3

# ----- 片段 3 (python) -----
stack = []
stack.append(1)   # push 入栈
stack.append(2)
stack.append(3)
print(stack.pop())  # pop 出栈: 3
print(stack[-1])    # peek 看栈顶: 2

# 经典应用: 括号匹配
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in s:
        if ch in "([{":
            st.append(ch)
        elif not st or st.pop() != pairs[ch]:
            return False
    return not st

print(is_valid("({[]})"))   # True
print(is_valid("([)]"))     # False

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

queue = deque()
queue.append("任务A")   # 入队
queue.append("任务B")
queue.append("任务C")

print(queue.popleft())  # 出队: 任务A
print(queue.popleft())  # 出队: 任务B
print(len(queue))       # 还剩 1 个

# 经典应用: BFS 二叉树层序遍历(简化版)
def bfs(root):
    if not root:
        return []
    q, result = deque([root]), []
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return result