栈与队列

栈(Stack)与队列(Queue)是两种受限的线性表,分别遵循 LIFO(后进先出)与 FIFO(先进先出)规则。它们是函数调用、任务调度、表达式求值等场景的基础构件。

栈(LIFO)

栈只允许在栈顶进行插入(push)与删除(pop),时间复杂度均为 O(1)。典型应用包括:

• 括号匹配:遍历字符串,遇左括号入栈,遇右括号则弹出栈顶检查是否配对。
• 函数调用栈:保存局部变量、返回地址,递归本质上是栈的自我调用。
• 表达式求值:中缀转后缀(逆波兰式)时用栈保存运算符。
• 浏览器前进/后退:两个栈即可实现历史记录切换。

def is_balanced(s: str) -> bool:
    stack, pairs = [], {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

队列(FIFO)

队列在队尾入队(enqueue)、队头出队(dequeue),同样为 O(1)。常用于任务调度、消息队列、树的层序遍历(BFS)、广度优先搜索等。

循环队列(数组实现)

普通数组实现队列时,dequeue 后队头空间无法复用,容易浪费。循环队列将数组视为首尾相接的环,使用 head 与 tail 两个指针并对长度取模,使入队出队均为 O(1),且能高效利用固定大小的数组。关键公式为:

tail = (tail + 1) % capacity
head = (head + 1) % capacity

通常预留一个空位区分队空(head == tail)与队满((tail + 1) % cap == head)。

双端队列(Deque)

双端队列允许在两端进行插入和删除,兼具栈与队列的能力。Python 的 collections.deque、Java 的 ArrayDeque、C++ 的 std::deque 都是典型实现,内部多采用循环数组或块状链表,在两端操作均为均摊 O(1)。滑动窗口、单调队列(求区间最值)等算法都依赖双端队列。

用栈模拟队列(经典面试题)

仅用两个栈 in_stack 与 out_stack 即可实现队列:

• push(x):压入 in_stack。
• pop():若 out_stack 为空,先将 in_stack 全部倒入 out_stack,再弹出 out_stack 栈顶。
• peek():同理,但不弹出栈顶。
• empty():两栈同时为空。

每个元素至多被搬运两次,均摊时间 O(1)。反过来,也可用两个队列实现栈,但单次操作最坏为 O(n)。这类题考察的核心是对操作均摊分析与状态复用的理解。