承接上一篇《线性表》的基础，本篇我们来学习线性表的两个特殊形态：栈（Stack）和队列（Queue）。它们的逻辑结构和线性表完全一致，但操作受到严格限制——正是这种“限制”，让它们成为解决特定问题的神器，也是笔试面试中最高频的考点，没有之一。

你有没有过这样的经历：

• 面试时遇到“括号匹配”“逆波兰表达式求值”，明明知道用栈，但写代码时总是边界出错？
• 写二叉树层序遍历、图的广度优先搜索（BFS）时，不知道怎么用队列存节点？
• 好奇浏览器的“后退/前进”功能、操作系统的“函数调用”、消息队列的“任务调度”，底层到底是怎么实现的？

其实，这些问题的答案，都藏在栈和队列里。栈的“后进先出”和队列的“先进先出”，看似简单，却能解决无数复杂问题。本篇文章，我们会从定义出发，手写实现顺序栈、链栈、循环队列、链队列，再深入到5个栈的经典应用和4个队列的经典应用，最后拓展双端队列和优先队列，让你彻底吃透这两个高频考点。

---

一、栈（Stack）：后进先出的“箱子”

1. 栈的定义与核心特性

栈是操作受限的线性表，只允许在**表尾（栈顶）**进行插入和删除操作，不允许在中间或表头（栈底）操作。

我们用通俗的话理解：

• 栈顶（Top）：允许插入和删除的一端，是栈的“开口”；
• 栈底（Bottom）：固定的一端，是栈的“底部”；
• 后进先出（LIFO, Last In First Out）：最后进入栈的元素，最先出来。

举个生活中的例子：往箱子里放书。你只能把书一本本从上面放进去（入栈），也只能从上面一本本拿出来（出栈），最后放进去的书，最先能拿出来——这就是栈的完美体现。

另一个例子：浏览器的后退按钮。你每访问一个新页面，就把当前页面压入栈；点击后退，就把栈顶的页面弹出来——永远是最后访问的页面最先后退。

2. 栈的抽象数据类型（ADT）

栈的操作非常简单，核心只有两个：

操作类型	操作描述
初始化	创建一个空栈
入栈（Push）	在栈顶插入一个元素
出栈（Pop）	删除并返回栈顶元素
查看栈顶（Peek/Top）	返回栈顶元素，但不删除
辅助操作	判空、获取长度、清空

3. 栈的实现：顺序栈 vs 链栈

和线性表一样，栈也有两种存储实现：顺序栈（用动态数组实现）和链栈（用单链表实现）。

（1）顺序栈的完整实现（Python）

顺序栈用动态数组实现，栈底固定在数组的下标0位置，栈顶用一个变量top指向当前栈顶元素的下标（或者用数组的最后一个元素作为栈顶，更简单）。

我们直接复用上一篇的SeqList，用尾插/尾删实现入栈/出栈，因为顺序表的尾操作时间复杂度是O(1)，非常高效。

# 复用上一篇的动态顺序表SeqList（简化版，只保留核心功能）
class SeqList:
    def __init__(self, init_capacity=10):
        self.__capacity = init_capacity
        self.__size = 0
        self.__data = [None] * self.__capacity

    def get_size(self):
        return self.__size

    def is_empty(self):
        return self.__size == 0

    def add_last(self, value):
        if self.__size == self.__capacity:
            self.__resize(self.__capacity * 2)
        self.__data[self.__size] = value
        self.__size += 1

    def remove_last(self):
        if self.is_empty():
            raise IndexError("栈为空，无法出栈")
        value = self.__data[self.__size - 1]
        self.__data[self.__size - 1] = None
        self.__size -= 1
        if self.__size <= self.__capacity // 4 and self.__capacity > 10:
            self.__resize(self.__capacity // 2)
        return value

    def get_last(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self.__data[self.__size - 1]

    def __resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.__size):
            new_data[i] = self.__data[i]
        self.__data = new_data
        self.__capacity = new_capacity

# 顺序栈实现
class ArrayStack:
    def __init__(self):
        self.__list = SeqList()  # 底层用动态顺序表

    # 入栈：尾插
    def push(self, value):
        self.__list.add_last(value)

    # 出栈：尾删
    def pop(self):
        return self.__list.remove_last()

    # 查看栈顶
    def peek(self):
        return self.__list.get_last()

    # 判空
    def is_empty(self):
        return self.__list.is_empty()

    # 获取长度
    def size(self):
        return self.__list.get_size()

    # 格式化输出
    def __str__(self):
        return f"ArrayStack(size={self.size()}, data={self.__list.to_list() if hasattr(self.__list, 'to_list') else '...'})"

# 给SeqList补一个to_list方法，方便输出
def seqlist_to_list(self):
    return [self.__data[i] for i in range(self.__size)]
SeqList.to_list = seqlist_to_list

# 测试顺序栈
if __name__ == "__main__":
    stack = ArrayStack()
    print("初始化栈：", stack)
    # 入栈
    for i in range(5):
        stack.push(i)
        print(f"入栈 {i}：", stack)
    # 查看栈顶
    print("栈顶元素：", stack.peek())
    # 出栈
    for _ in range(3):
        value = stack.pop()
        print(f"出栈 {value}：", stack)

顺序栈的优缺点：

• 优点：实现简单，内存利用率高，没有指针开销，入栈出栈都是O(1)；
• 缺点：需要连续的内存空间，扩容时有内存复制的开销（但均摊复杂度还是O(1)）。

（2）链栈的完整实现（Python）

链栈用单链表实现，为了入栈出栈都是O(1)，我们把栈顶放在链表的头部（虚拟头节点的后面），入栈用头插法，出栈删第一个节点，不需要遍历。

# 复用单链表节点类
class ListNode:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# 链栈实现（带头节点，栈顶在头部）
class LinkedStack:
    def __init__(self):
        self.__head = ListNode()  # 虚拟头节点
        self.__size = 0

    # 入栈：头插法，O(1)
    def push(self, value):
        new_node = ListNode(value)
        new_node.next = self.__head.next
        self.__head.next = new_node
        self.__size += 1

    # 出栈：删第一个节点，O(1)
    def pop(self):
        if self.is_empty():
            raise IndexError("栈为空，无法出栈")
        del_node = self.__head.next
        self.__head.next = del_node.next
        self.__size -= 1
        return del_node.data

    # 查看栈顶
    def peek(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self.__head.next.data

    # 判空
    def is_empty(self):
        return self.__size == 0

    # 获取长度
    def size(self):
        return self.__size

    # 格式化输出
    def to_list(self):
        result = []
        cur = self.__head.next
        while cur:
            result.append(cur.data)
            cur = cur.next
        return result

    def __str__(self):
        return f"LinkedStack(size={self.size()}, data={self.to_list()})"

# 测试链栈
if __name__ == "__main__":
    stack = LinkedStack()
    print("初始化栈：", stack)
    # 入栈
    for i in range(5):
        stack.push(i)
        print(f"入栈 {i}：", stack)
    # 查看栈顶
    print("栈顶元素：", stack.peek())
    # 出栈
    for _ in range(3):
        value = stack.pop()
        print(f"出栈 {value}：", stack)

链栈的优缺点：

• 优点：不需要连续内存，扩容没有开销，入栈出栈都是O(1)；
• 缺点：每个节点有指针开销，存储密度比顺序栈低。

实际开发中：我们通常用顺序栈，因为实现更简单，内存利用率更高，Python的list本身就可以直接当栈用（append入栈，pop()出栈）。

---

4. 栈的经典应用（面试必考！）

栈的核心价值，在于它的**“后进先出”特性**，能完美解决“需要回溯最近操作”的问题。我们来讲解5个最经典的应用，每个都附带代码实现。

应用1：括号匹配（LeetCode 20. 有效的括号）

问题描述：给定一个只包含'(', ')', '{', '}', '[', ']'的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

示例：

• 输入："()[]{}" → 输出：True
• 输入："([)]" → 输出：False
• 输入："{[]}" → 输出：True

解题思路：
遇到左括号，就把对应的右括号压入栈；遇到右括号，就弹出栈顶元素，看是否匹配。如果栈为空或者不匹配，就返回False；最后栈必须为空，才是有效字符串。

代码实现：

def is_valid(s: str) -> bool:
    # 用字典存储左括号到右括号的映射
    bracket_map = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for char in s:
        if char in bracket_map:
            # 左括号：把对应的右括号入栈
            stack.append(bracket_map[char])
        else:
            # 右括号：检查栈是否为空，以及栈顶是否匹配
            if not stack or stack.pop() != char:
                return False
    # 最后栈必须为空
    return len(stack) == 0

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

复杂度分析：时间复杂度O(n)，空间复杂度O(n)，n是字符串长度。

---

应用2：表达式求值（逆波兰表达式）

问题背景：我们平时写的表达式是中缀表达式（比如3 + 4 * 2），运算符在中间，有优先级，计算机处理起来很麻烦。所以计算机通常先把中缀表达式转成后缀表达式（逆波兰式，RPN），运算符在后面，没有优先级，直接用栈计算。

逆波兰式示例：

• 中缀：3 + 4 * 2 → 后缀：3 4 2 * +
• 中缀：(3 + 4) * 2 → 后缀：3 4 + 2 *
• 中缀：3 + 4 * 2 / (1 - 5) → 后缀：3 4 2 * 1 5 - / +

解题思路（计算逆波兰式）：
遍历逆波兰式的每个元素：

1. 遇到操作数：压入栈；
2. 遇到运算符：弹出两个栈顶元素（注意：先弹出的是右操作数，后弹出的是左操作数），计算结果，把结果压入栈；
3. 最后栈中剩下的一个元素，就是表达式的结果。

代码实现：

def eval_rpn(tokens: list) -> int:
    stack = []
    operators = {'+', '-', '*', '/'}
    for token in tokens:
        if token not in operators:
            # 操作数：入栈
            stack.append(int(token))
        else:
            # 运算符：弹出两个数
            b = stack.pop()  # 右操作数
            a = stack.pop()  # 左操作数
            # 计算
            if token == '+':
                res = a + b
            elif token == '-':
                res = a - b
            elif token == '*':
                res = a * b
            elif token == '/':
                # 注意：Python的除法是向下取整，这里要向零取整
                res = int(a / b)
            # 结果入栈
            stack.append(res)
    # 返回栈顶元素
    return stack[0]

# 测试：计算 "3 4 2 * 1 5 - / +" → 结果是 3 + (8 / (-4)) = 3 - 2 = 1
tokens = ["3", "4", "2", "*", "1", "5", "-", "/", "+"]
print(eval_rpn(tokens))  # 输出1

进阶：中缀表达式转后缀表达式
核心思路：用栈存运算符，遇到操作数直接输出；遇到运算符，弹出栈中优先级>=当前运算符的，然后入栈；遇到左括号入栈，遇到右括号弹出直到左括号。

---

应用3：递归转非递归（用栈模拟递归）

问题背景：递归虽然代码简洁，但有两个问题：

1. 递归深度过大会导致栈溢出（Stack Overflow），因为函数调用栈的深度是有限的；
2. 递归的函数调用有开销，性能不如非递归。

所以，我们可以用栈手动模拟函数调用栈，把递归转成非递归。

示例：斐波那契数列的递归转非递归
斐波那契数列的递归公式：F(n) = F(n-1) + F(n-2)，终止条件F(0)=0，F(1)=1。

递归实现：

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

非递归实现（用栈模拟）：
我们用栈存“待计算的任务”，每个任务可以是“计算F(n)”或者“返回结果”。

def fib_non_recursive(n):
    if n <= 1:
        return n
    # 栈中的元素：('calc', n) 表示需要计算F(n)；('res', val) 表示已经计算出的结果
    stack = [('calc', n)]
    # 结果栈，存计算出的F(k)
    res_stack = []
    
    while stack:
        task = stack.pop()
        type_task, num = task
        
        if type_task == 'calc':
            if num <= 1:
                # 终止条件，直接返回结果
                res_stack.append(num)
            else:
                # 先压入'calc'任务（注意顺序：先压n-2，再压n-1，因为栈后进先出，先算n-1）
                stack.append(('calc', num - 2))
                stack.append(('calc', num - 1))
                # 压入'add'任务，等n-1和n-2算完后相加
                stack.append(('add', None))
        elif type_task == 'add':
            # 弹出两个结果相加
            b = res_stack.pop()
            a = res_stack.pop()
            res_stack.append(a + b)
    
    return res_stack[0]

# 测试
print(fib_recursive(10))    # 55
print(fib_non_recursive(10)) # 55

另一个经典应用：二叉树的前序、中序、后序遍历的非递归实现，本质都是用栈模拟递归调用栈。

---

应用4：进制转换（十进制转其他进制）

问题描述：将十进制数转换成二进制、八进制、十六进制等。

解题思路：
以十进制转二进制为例，核心方法是“除2取余，逆序排列”：

1. 用十进制数除以2，得到余数，把余数压入栈；
2. 用商继续除以2，重复步骤1，直到商为0；
3. 依次弹出栈中的余数，就是二进制数（因为栈后进先出，所以余数是逆序的）。

代码实现：

def decimal_to_base(decimal: int, base: int) -> str:
    if decimal == 0:
        return "0"
    # 十六进制需要用到的字符
    digits = "0123456789ABCDEF"
    stack = []
    
    while decimal > 0:
        remainder = decimal % base
        stack.append(digits[remainder])
        decimal = decimal // base
    
    # 弹出栈中的字符，拼接成结果
    result = ""
    while stack:
        result += stack.pop()
    return result

# 测试
print(decimal_to_base(10, 2))   # 1010（十进制10转二进制）
print(decimal_to_base(10, 8))   # 12（十进制10转八进制）
print(decimal_to_base(255, 16)) # FF（十进制255转十六进制）

---

应用5：函数调用栈（操作系统底层）

问题背景：你有没有好奇过，为什么函数调用可以一层套一层？为什么函数返回后，能回到调用它的地方继续执行？答案就是函数调用栈。

栈帧（Stack Frame）：
每次调用一个函数，操作系统就会在内存的“栈区”分配一个栈帧，栈帧里存储：

1. 函数的返回地址（函数执行完后，回到哪里继续执行）；
2. 函数的参数；
3. 函数的局部变量；
4. 一些寄存器的状态。

调用过程：

1. 调用函数时，把参数、返回地址等压入栈，分配栈帧；
2. 函数执行时，在栈帧里操作局部变量；
3. 函数执行完后，弹出栈帧，根据返回地址回到调用处继续执行。

栈溢出（Stack Overflow）：
如果递归深度太大，栈区的内存不够用，就会抛出StackOverflowError——这就是为什么递归要有终止条件。

---

二、队列（Queue）：先进先出的“队伍”

1. 队列的定义与核心特性

队列是另一种操作受限的线性表，只允许在**表尾（队尾）进行插入操作，在表头（队头）**进行删除操作。

通俗理解：

• 队尾（Rear）：允许插入的一端，是队伍的“末尾”；
• 队头（Front）：允许删除的一端，是队伍的“开头”；
• 先进先出（FIFO, First In First Out）：最先进入队列的元素，最先出来。

生活中的例子：排队买奶茶。你只能从队伍的末尾排队（入队），只能从队伍的开头买完离开（出队），先来的人先买——这就是队列的完美体现。

另一个例子：打印机的打印队列。你发送的打印任务，按顺序进入队列，先来的任务先打印。

2. 队列的抽象数据类型（ADT）

队列的核心操作也是两个：

操作类型	操作描述
初始化	创建一个空队列
入队（Enqueue）	在队尾插入一个元素
出队（Dequeue）	删除并返回队头元素
查看队头（Peek/Front）	返回队头元素，但不删除
辅助操作	判空、获取长度、清空

3. 队列的实现：顺序队列、循环队列 vs 链队列

队列的实现比栈复杂一点，因为顺序队列会有“假溢出”问题，所以我们重点讲循环队列（用数组实现）和链队列（用带尾指针的单链表实现）。

（1）顺序队列的问题：假溢出

顺序队列用数组实现，front指向队头元素的下标，rear指向队尾元素的下一个下标。

• 入队：rear++，把元素放入rear位置；
• 出队：front++，返回front位置的元素。

假溢出问题：
当rear到达数组末尾时，数组前面可能还有空位置（因为出队后front后移了），但无法再入队——这就是“假溢出”。

解决假溢出的方案：循环队列，把数组看成一个环，用取模运算让front和rear在数组里循环移动。

---

（2）循环队列的完整实现（Python）

循环队列的核心设计：

• 把数组看成一个环形结构，用(rear + 1) % capacity计算下一个位置；
• 牺牲一个位置，用来区分“队空”和“队满”：
  • 队空条件：front == rear；
  • 队满条件：(rear + 1) % capacity == front（牺牲一个位置，避免和队空条件混淆）。

class CircularQueue:
    def __init__(self, capacity: int = 10):
        if capacity <= 0:
            raise ValueError("容量必须大于0")
        self.__capacity = capacity + 1  # 多分配一个位置，用来区分空和满
        self.__data = [None] * self.__capacity
        self.__front = 0  # 队头指针，指向队头元素
        self.__rear = 0   # 队尾指针，指向队尾元素的下一个位置

    # 入队
    def enqueue(self, value):
        if self.is_full():
            raise IndexError("队列已满，无法入队")
        self.__data[self.__rear] = value
        self.__rear = (self.__rear + 1) % self.__capacity

    # 出队
    def dequeue(self):
        if self.is_empty():
            raise IndexError("队列为空，无法出队")
        value = self.__data[self.__front]
        self.__data[self.__front] = None
        self.__front = (self.__front + 1) % self.__capacity
        return value

    # 查看队头
    def peek(self):
        if self.is_empty():
            raise IndexError("队列为空")
        return self.__data[self.__front]

    # 判空
    def is_empty(self):
        return self.__front == self.__rear

    # 判满
    def is_full(self):
        return (self.__rear + 1) % self.__capacity == self.__front

    # 获取当前元素个数
    def size(self):
        return (self.__rear - self.__front + self.__capacity) % self.__capacity

    # 格式化输出
    def to_list(self):
        result = []
        i = self.__front
        while i != self.__rear:
            result.append(self.__data[i])
            i = (i + 1) % self.__capacity
        return result

    def __str__(self):
        return f"CircularQueue(size={self.size()}, capacity={self.__capacity-1}, data={self.to_list()})"

# 测试循环队列
if __name__ == "__main__":
    # 容量为5的循环队列
    q = CircularQueue(capacity=5)
    print("初始化队列：", q)
    # 入队
    for i in range(5):
        q.enqueue(i)
        print(f"入队 {i}：", q)
    # 尝试入队第6个，会报错（队满）
    try:
        q.enqueue(5)
    except IndexError as e:
        print("入队失败：", e)
    # 查看队头
    print("队头元素：", q.peek())
    # 出队
    for _ in range(3):
        value = q.dequeue()
        print(f"出队 {value}：", q)
    # 再入队
    q.enqueue(5)
    q.enqueue(6)
    print("入队5、6：", q)

循环队列的优缺点：

• 优点：实现了数组的循环利用，解决了假溢出问题，入队出队都是O(1)；
• 缺点：容量固定，需要提前分配，牺牲了一个存储位置。

---

（3）链队列的完整实现（Python）

链队列用带尾指针的单链表实现，队头在链表头部（虚拟头节点后面），队尾在链表尾部，用rear指针指向队尾，这样入队出队都是O(1)。

# 复用单链表节点类
class ListNode:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# 链队列实现（带头节点和尾指针）
class LinkedQueue:
    def __init__(self):
        self.__head = ListNode()  # 虚拟头节点
        self.__rear = self.__head  # 尾指针，初始指向头节点
        self.__size = 0

    # 入队：尾插，O(1)
    def enqueue(self, value):
        new_node = ListNode(value)
        self.__rear.next = new_node
        self.__rear = new_node
        self.__size += 1

    # 出队：删第一个节点，O(1)
    def dequeue(self):
        if self.is_empty():
            raise IndexError("队列为空，无法出队")
        del_node = self.__head.next
        self.__head.next = del_node.next
        # 如果删除的是尾节点，需要更新尾指针
        if self.__rear == del_node:
            self.__rear = self.__head
        self.__size -= 1
        return del_node.data

    # 查看队头
    def peek(self):
        if self.is_empty():
            raise IndexError("队列为空")
        return self.__head.next.data

    # 判空
    def is_empty(self):
        return self.__size == 0

    # 获取长度
    def size(self):
        return self.__size

    # 格式化输出
    def to_list(self):
        result = []
        cur = self.__head.next
        while cur:
            result.append(cur.data)
            cur = cur.next
        return result

    def __str__(self):
        return f"LinkedQueue(size={self.size()}, data={self.to_list()})"

# 测试链队列
if __name__ == "__main__":
    q = LinkedQueue()
    print("初始化队列：", q)
    # 入队
    for i in range(5):
        q.enqueue(i)
        print(f"入队 {i}：", q)
    # 查看队头
    print("队头元素：", q.peek())
    # 出队
    for _ in range(3):
        value = q.dequeue()
        print(f"出队 {value}：", q)
    # 再入队
    q.enqueue(5)
    q.enqueue(6)
    print("入队5、6：", q)

链队列的优缺点：

• 优点：不需要连续内存，容量不固定，入队出队都是O(1)；
• 缺点：每个节点有指针开销，存储密度低。

实际开发中：如果容量固定，用循环队列；如果容量不固定，用链队列。Python的collections.deque也可以当队列用（append入队，popleft()出队）。

---

4. 队列的经典应用（面试必考！）

队列的核心价值，在于它的**“先进先出”特性**，能完美解决“需要按顺序处理任务”的问题。我们来讲解4个最经典的应用。

应用1：广度优先搜索（BFS）

问题背景：BFS是图和树的核心遍历算法，用来“按层遍历”，比如二叉树的层序遍历、图的最短路径搜索，底层都是用队列实现的。

示例：二叉树的层序遍历（LeetCode 102）
问题描述：给你二叉树的根节点，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

解题思路：

1. 把根节点入队；
2. 循环：每次出队一个节点，访问它，然后把它的左子节点和右子节点入队；
3. 为了按层输出，每次记录当前队列的大小（即当前层的节点数），一次性处理完当前层。

代码实现：

# 二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 二叉树层序遍历（BFS）
def level_order(root: TreeNode) -> list:
    if not root:
        return []
    # 用队列存节点
    from collections import deque
    q = deque()
    q.append(root)
    result = []
    
    while q:
        # 当前层的节点数
        level_size = len(q)
        level_nodes = []
        # 处理当前层
        for _ in range(level_size):
            node = q.popleft()
            level_nodes.append(node.val)
            # 左子节点入队
            if node.left:
                q.append(node.left)
            # 右子节点入队
            if node.right:
                q.append(node.right)
        # 把当前层加入结果
        result.append(level_nodes)
    return result

# 测试：构建二叉树
#     3
#    / \
#   9  20
#     /  \
#    15   7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(level_order(root))  # 输出[[3], [9,20], [15,7]]

复杂度分析：时间复杂度O(n)，空间复杂度O(n)，n是节点数。

---

应用2：系统缓冲区（键盘缓冲区、打印机缓冲区）

问题背景：当你在键盘上打字时，键盘输入的速度和CPU处理的速度不匹配——这时候就需要键盘缓冲区（队列实现）。

工作原理：

1. 你每按一个键，字符就进入键盘缓冲区（入队）；
2. CPU按顺序从缓冲区里取字符处理（出队）；
3. 这样即使你打字很快，CPU也能按顺序处理，不会丢失字符。

同样的，打印机缓冲区也是队列：你发送的打印任务按顺序入队，打印机按顺序出队打印。

---

应用3：任务调度（消息队列、线程池任务队列）

问题背景：在分布式系统、后端开发中，消息队列（比如RabbitMQ、Kafka）是核心组件，用来异步处理任务，本质就是队列。

工作原理：

1. 生产者：产生任务，把任务发送到消息队列（入队）；
2. 消费者：从消息队列里取任务，按顺序处理（出队）；
3. 这样可以解耦生产者和消费者，削峰填谷（比如秒杀系统，把请求存入队列，慢慢处理）。

---

应用4：生产者消费者模型

问题描述：生产者消费者模型是多线程编程的经典模型，用队列做“缓冲池”：

• 生产者线程：生产数据，放入队列；
• 消费者线程：从队列里取数据，处理数据；
• 队列满时，生产者等待；队列空时，消费者等待。

核心作用：解耦、平衡生产和消费的速度。

---

三、拓展：双端队列与优先队列

1. 双端队列（Deque, Double-Ended Queue）

双端队列是队列的扩展，允许在队头和队尾同时进行插入和删除操作，结合了栈和队列的特性。

核心操作：

• 队头入队、队头出队；
• 队尾入队、队尾出队。

Python实现：collections.deque就是双端队列的完美实现，所有操作都是O(1)：

from collections import deque

# 初始化双端队列
dq = deque()
# 队尾入队
dq.append(1)
dq.append(2)
# 队头入队
dq.appendleft(0)
print(dq)  # deque([0, 1, 2])
# 队尾出队
print(dq.pop())  # 2
# 队头出队
print(dq.popleft())  # 0
print(dq)  # deque([1])

经典应用：

• 滑动窗口最大值（LeetCode 239）；
• 回文字符串判断（头尾同时比较）；
• 实现栈和队列（用deque当底层）。

---

2. 优先队列（Priority Queue）

优先队列是特殊的队列，出队时不是按“先进先出”，而是按优先级高低出队，优先级最高的元素最先出队。

实现原理：优先队列的底层通常用**堆（Heap）**实现，堆是一种完全二叉树，分为小顶堆（堆顶是最小元素）和大顶堆（堆顶是最大元素）。

Python实现：heapq模块实现了小顶堆，可以用来实现优先队列：

import heapq

# 初始化小顶堆
heap = []
# 入队（push）
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
# 堆的结构：[1,2,8,5]，堆顶是最小元素1
print(heap)
# 出队（pop）：每次弹出最小元素
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 8

经典应用：

• Top K问题（LeetCode 215，找第K大的元素）；
• 任务调度（按优先级执行任务）；
• 哈夫曼编码（构建哈夫曼树）；
• Dijkstra最短路径算法（用优先队列存节点）。

---

四、总结与互动

本篇核心总结

栈和队列是操作受限的线性表，看似简单，却能解决无数复杂问题：

1. 栈（LIFO）：后进先出，用顺序表或链表实现，经典应用有括号匹配、表达式求值、递归转非递归、进制转换、函数调用栈；
2. 队列（FIFO）：先进先出，用循环队列或链队列实现，经典应用有BFS、系统缓冲区、任务调度、生产者消费者模型；
3. 拓展：双端队列（头尾都能操作）、优先队列（按优先级出队，堆实现）。

写给读者的话

栈和队列是笔试面试的“必考题收割机”，LeetCode上有超过200道题和栈队列相关。但只要你理解了“后进先出”和“先进先出”的核心特性，再多的题也能迎刃而解。

下一篇文章，我们会讲解串（String），这也是线性表的一种特殊形态，KMP算法是串的核心考点，敬请期待！

🎯 互动环节

1. 你在面试中遇到过哪些栈和队列的题？是括号匹配，还是BFS？欢迎在评论区留言分享！
2. 你有没有好奇过，Python的list为什么可以同时当栈和队列用？但为什么用list当队列时，pop(0)的效率很低？（提示：和顺序表的头删有关）
3. 下一篇文章，你想重点了解串的KMP算法，还是优先队列的堆实现？或者有其他想了解的内容，都可以告诉我！

如果这篇文章对你有帮助，欢迎点赞、收藏、转发给你的朋友，让更多人一起学好数据结构！有任何问题，都可以在评论区留言，我会一一解答～

---

参考资料：

1. 《数据结构（C语言版）》严蔚敏、吴伟民
2. 《算法（第4版）》Robert Sedgewick
3. LeetCode 高频面试题：有效的括号、二叉树的层序遍历、Top K问题
4. Python官方文档：collections.deque、heapq