web

栈与队列

第 5 章 · 数据结构与算法

后进先出与先进先出。 栈像一摞盘子：只能从顶部放、从顶部取（LIFO）；队列像排队买票：队尾进、队头出（FIFO）。两者都是「操作受限」的线性表，既可以用数组实现也可以用链表实现。栈在括号匹配、表达式求值、递归/DFS 里无处不在；队列是 BFS 层序遍历的基础。这一章把栈和队列讲清楚，并给出带完整题目与详解的例题。

一、栈

栈（stack）是一种后进先出（LIFO, Last In First Out）的线性结构。只允许在栈顶进行插入（压栈、push）和删除（弹栈、pop）；访问栈顶元素（top/peek）不删除。没有「从中间取」或「按下标访问」。

典型操作与复杂度（用数组或链表在栈顶操作）：push O(1)、pop O(1)、top/peek O(1)、判空 O(1)。

入栈 push ↓ 出栈 pop ↑
栈顶
入栈新元素从顶部压入 · 出栈从顶部弹出（后进先出）
栈：只能从「栈顶」压入和弹出，后进先出（LIFO）

二、栈的代码实现（Python）：数组与链表两种实现

下面分别用数组（list）和链表（节点 + 头指针）实现栈，并列出 push / pop / top / empty 等操作，与表格中的「数组实现」「链表实现」对应。

2.1 栈：数组实现

用 list，末尾作栈顶：push 即 append，pop 即 pop()，均为 O(1) 均摊；top 即 lst[-1]，判空即 len(lst)==0。

from typing import List, Optional

# 栈（数组实现）：末尾为栈顶
def stack_array_demo() -> None:
    st: List[int] = []
    st.append(3)       # push(3)
    st.append(7)       # push(7)
    top_val: Optional[int] = st[-1] if st else None   # top(): 7
    st.pop()           # pop(): 7
    st.pop()           # pop(): 3
    is_empty: bool = len(st) == 0   # empty(): True

2.2 栈：链表实现

用单向链表，头节点作栈顶：push 即在头前插入新节点并更新 head；pop 即删除头节点并返回其值；top 即 head.val；判空即 head 为 None。所有操作 O(1)。

from typing import Optional

class Node:
    def __init__(self, val: int, next: Optional["Node"] = None) -> None:
        self.val = val
        self.next = next

class StackLinked:
    """栈的链表实现：头为栈顶，push=头插，pop=删头。"""
    def __init__(self) -> None:
        self.head: Optional[Node] = None

    def push(self, val: int) -> None:
        self.head = Node(val, self.head)

    def pop(self) -> int:
        if self.head is None:
            raise IndexError("pop from empty stack")
        val: int = self.head.val
        self.head = self.head.next
        return val

    def top(self) -> int:
        if self.head is None:
            raise IndexError("top from empty stack")
        return self.head.val

    def empty(self) -> bool:
        return self.head is None

说明：数组实现利用 list 尾部操作的 O(1)；链表实现利用「在头前插入」和「删头」都是 O(1)，与表格一致。

三、队列

队列（queue）是一种先进先出（FIFO, First In First Out）的线性结构。元素从队尾入队（enqueue）、从队头出队（dequeue）；可支持查看队头（front/peek）不删除。

若用普通 list 在头部 pop(0) 做 dequeue，单次为 O(n)。用双端队列（deque）在两端增删均为 O(1)，适合实现队列。

队列（先进先出 FIFO）
队尾 ← 入队 出队 → 队头
A
B
C
元素从队尾进入，向队头移动，从队头离开
队列：像排队买票，先来的先服务

四、队列的代码实现（Python）：数组与链表两种实现

下面分别用数组（双端队列 deque）和链表（头指针 + 尾指针）实现队列，并列出 enqueue / dequeue / front / empty 等操作。

4.1 队列：数组（双端）实现

用 list 在队头 pop(0) 会导致 dequeue O(n)。标准做法是用 collections.deque（双端队列，底层可视为循环数组）：队尾入 append，队头出 popleft，两端均为 O(1)。

from collections import deque
from typing import Optional

# 队列（数组/双端实现）：队尾 append，队头 popleft
def queue_array_demo() -> None:
    q: deque[int] = deque()
    q.append(3)           # enqueue(3)
    q.append(7)           # enqueue(7)
    front_val: Optional[int] = q[0] if q else None   # front(): 3
    q.popleft()           # dequeue(): 3
    q.popleft()           # dequeue(): 7
    is_empty: bool = len(q) == 0   # empty(): True

4.2 队列：链表实现

维护头指针 head（队头）和尾指针 tail（队尾）。enqueue：在 tail 后插入新节点并更新 tail；若为空则 head=tail=新节点。dequeue：删 head 并返回其值，若删后为空则 tail 置 None。front、empty 即读 head。所有操作 O(1)。

from typing import Optional

class QNode:
    def __init__(self, val: int, next: Optional["QNode"] = None) -> None:
        self.val = val
        self.next = next

class QueueLinked:
    """队列的链表实现：head 队头、tail 队尾，enqueue 接在 tail 后，dequeue 删 head。"""
    def __init__(self) -> None:
        self.head: Optional[QNode] = None
        self.tail: Optional[QNode] = None

    def enqueue(self, val: int) -> None:
        node: QNode = QNode(val)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self) -> int:
        if self.head is None:
            raise IndexError("dequeue from empty queue")
        val: int = self.head.val
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return val

    def front(self) -> int:
        if self.head is None:
            raise IndexError("front from empty queue")
        return self.head.val

    def empty(self) -> bool:
        return self.head is None

说明：数组实现用 deque 在两端 O(1) 入出，对应表格「头出需移动或循环队列」——用循环/双端避免整体移动。链表实现用 head+tail 在队尾 O(1) 入、队头 O(1) 出，与表格「头指针+尾指针，O(1)」一致。

五、栈与队列的对比与实现

对比项栈队列
顺序后进先出（LIFO）先进先出（FIFO）
操作位置仅栈顶队尾入、队头出
典型操作push / pop / topenqueue / dequeue / front
数组实现末尾作栈顶，O(1)头出需移动或循环队列
链表实现头作栈顶，O(1)头指针+尾指针，O(1)

栈和队列都只在一端或两端操作，因此用数组（末尾/循环）或链表都能实现 O(1) 的入出。上文的「二、栈的代码实现」与「四、队列的代码实现」已分别给出数组实现和链表实现的 Python 代码及 push/pop、enqueue/dequeue 等操作，可与本表对照理解。

六、常见应用延伸

栈：括号匹配、表达式求值（中缀转后缀或双栈）、递归/DFS 的调用栈、单调栈（下一更大元素等）。队列：BFS 层序遍历、滑动窗口最值（双端队列）。下面用四道例题把「栈实现」「队列实现」和典型应用串起来。

七、例题与代码详解

以下四道题给出完整题目描述、Python3 解法（带类型标注）与详细讲解。

例题 1：有效括号

题目描述：给定一个只包含 '(' ')' '[' ']' '{' '}' 的字符串 s，判断括号是否有效。有效条件：同类型左右括号成对、且顺序正确（即闭合顺序与打开顺序一致）。

输入：s 长度 ≥ 0。
输出：True 有效，False 无效。

def is_valid(s: str) -> bool:
    """栈：遇左括号压栈，遇右括号与栈顶匹配并弹栈；不匹配或最后栈非空则无效。"""
    stack: list[str] = []
    pair: dict[str, str] = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in pair:
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return len(stack) == 0

讲解：从左到右扫描，左括号必须等「对应的」右括号在之后出现才能闭合，因此用栈维护「未闭合的左括号」顺序。遇到右括号时，栈顶必须是与之匹配的左括号并弹栈；否则无效。扫描结束后栈必须为空。时间 O(n)，空间 O(n)。

例题 2：最小栈（O(1) 获取当前最小值）

题目描述：实现一个栈，支持 push、pop、top，并能在 O(1) 时间内获取当前栈中的最小元素 getMin。

输入：一系列操作（push 带整型参数）。
输出：getMin 返回当前栈内最小值。

class MinStack:
    """用辅助栈同步记录「从栈底到当前栈顶」的最小值，与主栈同进同出。"""

    def __init__(self) -> None:
        self.st: list[int] = []
        self.min_st: list[int] = []

    def push(self, val: int) -> None:
        self.st.append(val)
        self.min_st.append(min(val, self.min_st[-1]) if self.min_st else val)

    def pop(self) -> None:
        self.st.pop()
        self.min_st.pop()

    def top(self) -> int:
        return self.st[-1]

    def get_min(self) -> int:
        return self.min_st[-1]

讲解：主栈正常存值；min_st[i] 表示「主栈前 i+1 个元素」的最小值。push 时对 min_st 压入 min(新值, 当前 min_st 栈顶)；pop 时两栈同步弹。这样栈顶的 min_st[-1] 始终是当前栈的最小值。时间各操作 O(1)，空间 O(n)。

例题 3：用栈实现队列

题目描述：仅使用两个栈实现一个 FIFO 队列，支持 push（队尾入）、pop（队头出）、peek（看队头）、empty（判空）。假设所有操作合法（如非空时才 pop）。

输入：一系列 push / pop / peek / empty 操作。
输出：pop 与 peek 返回队头元素，empty 返回是否为空。

class MyQueue:
    """入队全进 in_st；出队/看队头时若 out_st 为空则把 in_st 全部倒入 out_st，再从 out_st 取。"""

    def __init__(self) -> None:
        self.in_st: list[int] = []
        self.out_st: list[int] = []

    def push(self, x: int) -> None:
        self.in_st.append(x)

    def pop(self) -> int:
        self._pour()
        return self.out_st.pop()

    def peek(self) -> int:
        self._pour()
        return self.out_st[-1]

    def empty(self) -> bool:
        return not self.in_st and not self.out_st

    def _pour(self) -> None:
        if not self.out_st:
            while self.in_st:
                self.out_st.append(self.in_st.pop())

讲解：栈是 LIFO，要得到 FIFO 需要「反序」一次。做法：入队只往 in_st 压；出队或 peek 时，若 out_st 为空，就把 in_st 全部依次弹出并压入 out_st，这样最早进 in_st 的会出现在 out_st 的栈顶，从 out_st 弹出即队头。每个元素最多进 in_st 一次、进 out_st 一次，均摊 O(1)。

例题 4：用队列实现栈

题目描述：仅使用两个队列实现一个 LIFO 栈，支持 push、pop、top、empty。假设所有操作合法。

输入：一系列 push / pop / top / empty 操作。
输出：pop 与 top 返回栈顶元素。

from collections import deque

class MyStack:
    """保持主队列 q 中「队尾即栈顶」。pop/top 时把队尾前的元素依次出队再入队，露出队尾。"""

    def __init__(self) -> None:
        self.q: deque[int] = deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        return self.q.popleft()

    def top(self) -> int:
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        res: int = self.q[0]
        self.q.append(self.q.popleft())
        return res

    def empty(self) -> bool:
        return len(self.q) == 0

讲解：队列是 FIFO，队尾是最后进的，对应「栈顶」。pop 时要把「栈顶」（队尾）取出：把队尾之前的元素依次从队头出队再接到队尾，这样原队尾变队头，popleft 即栈顶。top 同理，但取完后要把该元素再放回队尾以保持结构。push O(1)，pop/top 单次 O(n)。（也可用两个队列轮转，思路类似。）

小贴士： 栈和队列的题常考「用 A 实现 B」或「在 O(1) 内多维护一个量」（如最小栈）。先想清楚「谁对应栈顶/队头」，再设计辅助结构或倒序方式。

八、小结

栈是 LIFO，仅栈顶操作，Python 用 list 的 append/pop 即可；队列是 FIFO，队尾入队头出，Python 用 collections.deque 的 append/popleft。两者都可用数组或链表实现 O(1) 入出。典型应用：栈做括号匹配、表达式、DFS；队列做 BFS。例题：有效括号、最小栈、用栈实现队列、用队列实现栈。下一章我们会学哈希表——键值存储与 O(1) 查找。