栈与队列：后进先出与先进先出

在计算机科学的广袤世界中，数据结构是构建高效算法的基石。当我们告别简单的变量和数组，试图用代码模拟现实世界的排队、撤回操作、函数调用的嵌套关系时，栈 (Stack) 与 队列 (Queue) 便成了两把必不可少的钥匙。它们看似简单，却深刻地体现了顺序与约束的美学。本篇教程将带你从零开始，掌握这两种最基础的线性结构。

什么是栈？后进先出 (LIFO) 的直觉

想象一摞叠在一起的盘子。你只能从最上面取走一个盘子（即最新放上去的），也只能在放新盘子时放在最顶部。这种 "最后放进去的，最先取出来" 的行为，正是栈的精髓——后进先出 (Last-In-First-Out, LIFO)。

在软件中，栈是一种受限制的线性表，只允许在一端（通常称为栈顶）进行插入和删除操作。另一端则称为栈底。因为访问元素的顺序严格受限，栈天生适合处理那些具有 "嵌套" 或 "回溯" 性质的问题。

栈的核心操作

一个标准的栈通常支持以下五种基本操作：

• push(x): 将元素 x 压入栈顶。
• pop(): 移除并返回栈顶元素。如果栈为空，通常会抛出异常或返回特定值。
• peek() 或 top(): 返回栈顶元素的值，但不移除它。
• isEmpty(): 检查栈是否为空，返回布尔值。
• size(): 返回栈中当前元素的个数。

直观示例

假设我们依次执行：push(10)、push(20)、push(30)。此时栈内元素从底到顶为 [10, 20, 30]。接着执行：

• pop() → 返回 30，栈变为 [10, 20]
• push(40) → 栈变为 [10, 20, 40]
• peek() → 返回 40，栈保持不变
• pop() → 返回 40，栈变为 [10, 20]

可以看到，最先进入的 10 被压在最底部，只有等到上面的元素全部移除后，它才有可能被访问。

栈的实现方式

实现一个栈，并无秘密可言。我们可以选择底层用数组或链表来存储数据，两者都能在常数时间 O(1) 内完成 push 和 pop 操作。

基于数组的栈

使用固定容量的数组，并用一个整型变量 top 指示栈顶位置。初始时 top = -1 表示空栈。

Python 伪代码实现：

class ArrayStack:
    def __init__(self, capacity=1000):
        self.data = [None] * capacity
        self.top = -1

    def push(self, x):
        self.top += 1
        self.data[self.top] = x

    def pop(self):
        if self.isEmpty():
            raise IndexError("pop from empty stack")
        val = self.data[self.top]
        self.top -= 1
        return val

    def peek(self):
        if self.isEmpty():
            raise IndexError("peek from empty stack")
        return self.data[self.top]

    def isEmpty(self):
        return self.top == -1

    def size(self):
        return self.top + 1

注意：若数组已满，再执行 push 会导致溢出。实际应用中可以使用动态扩容的数组，但均摊复杂度仍为 O(1)。

基于链表的栈

采用单链表，将链表头部作为栈顶。每次 push 相当于在头部插入节点，pop 相当于删除头部节点。由于不需要扩容，链表实现不会产生空间浪费，但每个节点需额外存储指针。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, x):
        new_node = Node(x)
        new_node.next = self.head
        self.head = new_node
        self.count += 1

    def pop(self):
        if self.isEmpty():
            raise IndexError("pop from empty stack")
        val = self.head.val
        self.head = self.head.next
        self.count -= 1
        return val

    def peek(self):
        if self.isEmpty():
            raise IndexError("peek from empty stack")
        return self.head.val

    def isEmpty(self):
        return self.head is None

    def size(self):
        return self.count

什么是队列？先进先出 (FIFO) 的秩序

与栈截然相反，队列像我们在餐厅排队点餐：最早到达的人最先得到服务并离开，新来的人只能排在队尾。这种 先进先出 (First-In-First-Out, FIFO) 的规则确保了公平的顺序性。

队列同样是一个限制操作的线性表，但插入（入队）仅允许在队尾 (rear/tail) 进行，删除（出队）仅允许在队头 (front/head) 进行。它忠实地保留了元素的到达顺序，非常适合缓冲、调度和广度优先遍历等场景。

队列的核心操作

• enqueue(x): 将元素 x 添加到队尾。
• dequeue(): 移除并返回队头元素。队空时抛异常。
• front() 或 peek(): 返回队头元素而不移除。
• isEmpty(): 判空。
• size(): 返回元素数量。

操作流程演示

执行：enqueue("A")、enqueue("B")、enqueue("C")。队列内部顺序为 ["A", "B", "C"]（A 为队头，C 为队尾）。接着：

• dequeue() → 返回 "A"，队列变为 ["B", "C"]
• enqueue("D") → 队列变为 ["B", "C", "D"]
• front() → 返回 "B"

队列的实现

队列的实现难点在于如何高效地维护头尾指针。直接使用普通数组进行 dequeue 时，移除队头会导致后续所有元素前移，时间复杂度为 O(n)。因此，我们需要更巧妙的方案。

基于循环数组的队列

采用固定大小数组，并维护两个索引：front (指向队头) 和 rear (指向队尾的下一个空位)。当指针到达数组末尾时，通过模运算 % 循环回到数组开头，形成一个环形缓冲区。这样在 O(1) 时间内即可完成入队和出队。

class CircularQueue:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.capacity = capacity
        self.front = 0      # 队头索引
        self.rear = 0       # 队尾的下一个空位索引
        self.count = 0

    def enqueue(self, x):
        if self.count == self.capacity:
            raise OverflowError("Queue is full")
        self.data[self.rear] = x
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError("dequeue from empty queue")
        val = self.data[self.front]
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return val

    def front_elem(self):
        if self.isEmpty():
            raise IndexError("queue is empty")
        return self.data[self.front]

    def isEmpty(self):
        return self.count == 0

    def size(self):
        return self.count

基于链表的队列

使用单链表，并额外维护一个指向尾节点的指针，这样既能在 O(1) 时间在尾部插入，也能在 O(1) 时间从头部删除。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = None   # 队头
        self.rear = None    # 队尾
        self.count = 0

    def enqueue(self, x):
        new_node = Node(x)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError("dequeue from empty queue")
        val = self.front.val
        self.front = self.front.next
        if self.front is None:  # 队列变为空
            self.rear = None
        self.count -= 1
        return val

    def front_elem(self):
        if self.isEmpty():
            raise IndexError("queue is empty")
        return self.front.val

    def isEmpty(self):
        return self.front is None

    def size(self):
        return self.count

栈与队列的核心差异对比

经典应用场景

栈的实战案例

• 函数调用栈：编程语言在运行程序时，会使用调用栈记录函数的返回地址、局部变量。嵌套调用就像不断 push，函数返回则 pop。这就是为什么递归层数过深会导致“栈溢出 (stack overflow)”。
• 撤销 (Undo)：文本编辑器中，每次编辑操作都被 push 到一个栈里。按下 Ctrl+Z 时，就 pop 最近的操作并逆向执行。
• 括号匹配：遇到左括号入栈，遇到右括号检查栈顶是否匹配。最终如果栈为空，说明括号完全配对；反之则存在未闭合的括号。

队列的实战案例

• 任务调度：操作系统中的进程/线程通常按就绪队列排队等待 CPU 时间片，先就绪的先执行。
• 广度优先搜索 (BFS)：在图的遍历或树层级遍历中，利用队列记录下一层需要访问的节点，天然保证了按距离顺序访问。
• 消息队列 (Message Queue)：分布式系统中，生产者将消息放入队列尾部，消费者从头部取出，实现异步通信与流量削峰。

栈与队列的联合：用两个栈实现队列

这是一个经典的面试问题，旨在检验对结构的深入理解。使用两个栈 stack1 (用于入队) 和 stack2 (用于出队)：

• enqueue(x): 直接将元素 push 进 stack1。
• dequeue(): 如果 stack2 为空，就将 stack1 中的所有元素逐个 pop 并 push 到 stack2 中，此时原本在 stack1 底部的元素就到了 stack2 顶部。然后从 stack2 pop 即可。如果 stack2 仍有元素，直接 pop。

通过这种方式，两次 LIFO 变成了 FIFO，时间复杂度均摊后仍为 O(1)。

延伸：不只限于基本款

掌握了标准栈和队列后，你会发现它们还有多种变体：

• 双端队列 (Deque)：允许在两端同时进行插入和删除，兼具栈和队列的功能。
• 优先队列 (Priority Queue)：不再遵循严格的 FIFO，而是按元素的优先级决定出队顺序，通常用堆实现。

不过，万变不离其宗。理解 LIFO 与 FIFO 的运作机制，以及它们在内存中维护顺序的方式，才是你构建复杂算法思维的第一步。

总结

栈和队列是最朴素的数据结构，但它们的 "限制" 恰恰赋予了代码明确的逻辑。栈用后进先出来管理回溯与嵌套，队列用先进先出来维护公平与时序。当你在编程时遇到需要 "记住回去的路" 或是 "按顺序逐个处理" 的情景，不妨想一想，它们就是最趁手的工具。亲手用数组或链表实现一遍，运行几个操作序列，这种直观的理解将伴随你的整个编程生涯。