栈&队列&数组

发表于 2025/08/13 更新于 2025/08/13

作者 Silly Cheese 30 分钟阅读

栈、队列与数组

1. 栈（Stack）

1.1 定义与特性

栈是后进先出（LIFO，Last In First Out）的线性表。
典型操作：push(入栈)、pop(出栈)、top/peek(栈顶元素)、isEmpty、size。
常见实现：顺序栈（基于数组）与链式栈（基于链表）。

1.2 实现要点

顺序栈：
- 需要一个连续的数组/向量来存放元素。
- 注意上溢（栈满）与下溢（栈空）的边界判断。
- 动态数组实现更常见，可以在容量不足时扩容。
链式栈：
- 通过单向链表实现，出栈/入栈复杂度都是 O(1)，不需要预设容量。
- 优点：无容量上限，缺点：指针开销略大。

1.3 时间复杂度

push、pop、top、isEmpty：均为 O(1)（摊销视实现而定，如动态扩容会有偶发的 O(n) 代价，但总体摊销仍是 O(1) 平均）。

1.4 常见题型与解题思路

括号匹配：用栈存放左括号，遇到右括号时与栈顶对对称性检查。
表达式求值：中缀表达式转后缀表达式（逆波兰表达式）再求值，或直接用栈实现表达式求值。
逆波兰表达式求值：遍历表达式，遇数字入栈，遇运算符弹出需要的操作数进行计算后再入栈。
用栈实现队列/双端操作：如用两个栈实现队列，或在特定题型中用栈来回放/反转序列。
最小栈（MinStack）：在栈中维护辅助栈记录当前最小值，O(1) 获取最小值。

1.5 代码模板（Python）

顺序栈（简单版，Python 内置列表即可实现）

        
      
class Stack:
  def __init__(self):
      self.data = []

  def push(self, x):
      self.data.append(x)

  def pop(self):
      if not self.data:
          raise IndexError("pop from empty stack")
      return self.data.pop()

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

  def is_empty(self):
      return len(self.data) == 0

  def __len__(self):
      return len(self.data)

最小栈（MinStack）

        
      
class MinStack:
  def __init__(self):
      self.stack = []
      self.min_stack = []

  def push(self, x):
      self.stack.append(x)
      if not self.min_stack or x <= self.min_stack[-1]:
          self.min_stack.append(x)

  def pop(self):
      v = self.stack.pop()
      if v == self.min_stack[-1]:
          self.min_stack.pop()
      return v

  def top(self):
      return self.stack[-1]

  def get_min(self):
      return self.min_stack[-1] if self.min_stack else None

两个栈实现队列

        
      
class StackQueue:
  def __init__(self):
      self.in_stack = []
      self.out_stack = []

  def enqueue(self, x):
      self.in_stack.append(x)

  def dequeue(self):
      if not self.out_stack:
          while self.in_stack:
              self.out_stack.append(self.in_stack.pop())
      if not self.out_stack:
          raise IndexError("dequeue from empty queue")
      return self.out_stack.pop()

  def is_empty(self):
      return not self.in_stack and not self.out_stack

1.6 共享栈（Multi-stack in one array）

1.6.1 定义与动机

共享栈指在同一个数组中实现多个栈，使多个栈共享同一块物理存储空间。
优点：提高空间利用率，避免“固定分区”导致的浪费。
常见场景：需要多路栈结构且总容量有限时，或在题目中要求“多个栈共用一个数组”的实现。

1.6.2 实现思路

基本思想：通过一组辅助数据结构，将数组的空闲单元按链表形式组织起来，动态分配给任意栈使用；入栈时从自由链表取一个位置，出栈时把该位置回收到自由链表。
常用实现有两种变体：
- 变体A：固定数量的栈（K 个栈），使用一个 free 列表管理未使用的索引，以及每个栈的 top 指针和一个 next 指针数组来组织“下一元素”的链表结构。
- 变体B：两栈在一个数组的简化实现（只有两个栈），仍然使用一个中间界限，适合快速理解。
下面给出最常用的变体A（K 栈在一个数组）的完整实现思路与代码。

1.6.3 数据结构设计

arr[n]：存放实际数据
top[k]：存放每个栈的栈顶在 arr 中的索引，初始为 -1
next[n]：用于维护每个下标的“下一个索引”指针，初始用于构建自由链表；对某个栈来说，next[index] 指向该索引在该栈中的下一个元素的位置
free：指向自由链表的头结点，表示当前未使用的数组下标，初始为 0
说明：
- push(x, t) 时，从 free 取一个下标 idx，free 指向 next[idx]，然后把 arr[idx] 赋值为 x、next[idx] 指向上一顶栈顶、top[t] 更新为 idx
- pop(t) 时，取当前栈顶 idx = top[t]，top[t] 指向 next[idx]，将 idx 加回自由链表：next[idx] 指向当前 free，free = idx，返回 arr[idx]

1.6.4 初始化

top = [-1, -1, …, -1]（长度为 K）
next = [i+1 for i in range(n)]，最后一个为 -1
free = 0

1.6.5 操作接口

push(stack_num, value)
pop(stack_num)
peek(stack_num)
is_empty(stack_num)
is_full()（当 free == -1 时，表示没有空闲空间）

1.6.6 时间复杂度与注意点

单次 push/pop 的时间复杂度为 O(1)（摊常数时间）。
空间利用率高于固定分区实现，但实现复杂度比单栈稍高，需要小心边界条件和指针更新。
在大量并发或异常情况时，要注意保证异常安全性（如抛错前确保数据结构状态正确）。

1.6.7 Python 代码模板

通用的 K 栈在一数组中的实现（使用自由链表管理空闲单元）

        
      
class KStacksInOneArray:
    def __init__(self, k, size):
        self.k = k                 # 栈的数量
        self.n = size              # 数组容量
        self.arr = [0] * size      # 存放实际数据
        self.top = [-1] * k          # 每个栈的栈顶在 arr 中的索引
        self.next = list(range(1, size)) + [-1]  # 下一个索引，用作自由链表和各栈中元素的“下一个”指针
        self.free = 0                # 自由链表的头指针

    def is_full(self):
        return self.free == -1

    def is_empty_stack(self, sn):
        return self.top[sn] == -1

    def push(self, sn, value):
        """
        sn: 栈号，范围 [0, k-1]
        value: 要入栈的值
        """
        if sn < 0 or sn >= self.k:
            raise IndexError("Invalid stack number")
        if self.is_full():
            raise IndexError("Stack Overflow")

        insert_at = self.free            # 从空闲链表中取一个位置
        self.free = self.next[insert_at]  # 更新 free 指向下一个空闲位置

        self.next[insert_at] = self.top[sn]  # 将新节点与栈 sn 的当前栈顶连接
        self.top[sn] = insert_at              # 更新栈顶为新节点
        self.arr[insert_at] = value           # 存放值

    def pop(self, sn):
        if sn < 0 or sn >= self.k:
            raise IndexError("Invalid stack number")
        if self.is_empty_stack(sn):
            raise IndexError("Stack Underflow")

        current = self.top[sn]          # 栈顶位置
        self.top[sn] = self.next[current]  # 栈顶向下一个节点移动

        # 将当前索引加入自由链表
        self.next[current] = self.free
        self.free = current

        return self.arr[current]

    def peek(self, sn):
        if sn < 0 or sn >= self.k:
            raise IndexError("Invalid stack number")
        if self.is_empty_stack(sn):
            raise IndexError("Stack is empty")
        return self.arr[self.top[sn]]

    def __str__(self):
        return f"arr={self.arr}, top={self.top}, free={self.free}"

简单的两栈在同一数组实现（变体B，便于理解）

        
      
class TwoStacksInOneArray:
    def __init__(self, n):
        self.n = n
        self.arr = [0] * n
        self.left_top = -1            # 左栈顶
        self.right_top = n            # 右栈顶
    def push_left(self, x):
        if self.left_top + 1 == self.right_top:
            raise IndexError("Stack Overflow")
        self.left_top += 1
        self.arr[self.left_top] = x
    def pop_left(self):
        if self.left_top == -1:
            raise IndexError("Left Stack Underflow")
        val = self.arr[self.left_top]
        self.left_top -= 1
        return val
    def push_right(self, x):
        if self.right_top - 1 == self.left_top:
            raise IndexError("Stack Overflow")
        self.right_top -= 1
        self.arr[self.right_top] = x
    def pop_right(self):
        if self.right_top == self.n:
            raise IndexError("Right Stack Underflow")
        val = self.arr[self.right_top]
        self.right_top += 1
        return val

使用场景提醒

对于需要强大空间利用率的多栈场景，优先考虑 KStacksInOneArray 的实现；

如果栈数固定且大小比较小，且实现要简单快速，可先用两栈共享或分区实现，后续再改为通用实现。

1.7 链栈（Linked Stack）

1.7.1 定义与特性

链栈通过单向链表实现栈结构，栈顶通常对应链表的头结点。
支持的操作：入栈 push、出栈 pop、获取栈顶元素 peek、判空 is_empty、获取大小 size/name。
优点：天然无容量上限，动态扩展；缺点：每个节点需要额外的指针域，内存开销较数组栈大，且在连续分配/释放时可能产生碎片。

1.7.2 数据结构设计

Node/结点结构：包含值和值所属的下一个节点引用。
top 指针：指向当前栈顶节点。
size（可选）：记录当前栈中元素个数，便于 O(1) 的 size。
变体选择：
- 简单版本：不使用哨兵结点，直接通过头指针与 next 指针实现。
- 带哨兵版本（Sentinel/ dummy head）：用一个哨兵头结点简化边界条件，入栈/出栈操作更简洁。

1.7.3 初始化

简单版本：top = None，size = 0
哨兵版本：head 指向哨兵节点，head.next 指向实际栈顶，size = 0

1.7.4 基本操作接口

push(x): 将 x 入栈
pop(): 将栈顶元素出栈并返回
peek(): 返回栈顶元素但不出栈
is_empty(): 判断栈是否为空
size()/len(): 返回栈中元素个数

1.7.5 时间复杂度

push、pop、peek、is_empty、size：均为 O(1)

1.7.6 变体：带哨兵头结点的链栈

优点：边界判断统一，代码常量更小，尤其在需要频繁判断空栈时更稳妥。
结构要点：哨兵结点不存放实际数据，所有数据结点都位于 head.next 及其后续。

1.7.7 Python 代码模板

变体A：简单版本（无哨兵） ```python class Node: def init(self, val, nxt=None): self.val = val self.next = nxt

class LinkedStack: def init(self): self.top = None self._size = 0

def push(self, x):
    node = Node(x, self.top)
    self.top = node
    self._size += 1

def pop(self):
    if self.top is None:
        raise IndexError("pop from empty stack")
    val = self.top.val
    self.top = self.top.next
    self._size -= 1
    return val

def peek(self):
    if self.top is None:
        raise IndexError("peek from empty stack")
    return self.top.val

def is_empty(self):
    return self.top is None

def size(self):
    return self._size

def __len__(self):
    return self._size ```

变体B：带哨兵头结点的链栈 ```python class Node: def init(self, val=None, nxt=None): self.val = val self.next = nxt

class LinkedStackSentinel: def init(self): self.head = Node() # 哨兵头结点 self._size = 0

def push(self, x):
    # 新结点插入在 head.next 之前
    self.head.next = Node(x, self.head.next)
    self._size += 1

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

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

def is_empty(self):
    return self.head.next is None

def size(self):
    return self._size

def __len__(self):
    return self._size ```

使用建议
- 如果题目强调空间使用，需要尽量避免固定容量的分区，链栈是天然选择。
- 如果对性能要求更多，且栈深度可控，数组栈在缓存局部性方面可能更快；两者可按题目需求选用或互换。

1.7.8 与数组栈的对比要点

链栈优点
- 无固定容量限制，理论上可无限扩展（受限于内存）。
- 入栈/出栈操作都为 O(1)，且边界处理通常更简单，尤其带哨兵时。
链栈缺点
- 每个节点需要额外的对象/指针，占用额外内存。
- 访问时可能对 CPU 缓存友好性较差。
适用场景
- 题目要求“动态扩容且不预先设定容量”的场景。
- 需要在栈中间频繁插入/删除节点的题型，或需要实现可回溯的状态记录。

1.7.9 常见题型与解题要点

括号匹配、表达式求值、逆波兰表达式（RPN）求值等栈相关题型，链栈与数组栈思路一致，区别在数据结构实现方式。
回溯/状态记录题：利用栈来保存历史状态，链栈在需要动态扩展的历史记录场景下更自然。
注意点
- 边界条件：空栈出栈/查看栈顶等操作需先判空。
- 内存管理：Python 等语言自动管理，但在手写语言（如 C/C++）需关注删除节点以防内存泄漏。
- 线程安全：默认非线程安全，如需多线程，需加锁或使用并发结构。

2. 队列（Queue）

2.1 定义与特性

队列是先进先出（FIFO，First In First Out）的线性表。
栈反向的角色：push 变为 enqueue，pop 变为 dequeue。
常见实现：顺序队列、循环队列、链式队列、以及更高级的双端队列（Deque）和优先队列（Priority Queue）。

2.2 实现要点

顺序队列：
- 用数组维护头尾指针，直观但容易在大量出队后产生“假空”，需要移动/记忆头指针。
循环队列（环形缓冲区）：
- 通过取模运算实现头尾移动，避免数据移动。
- 边界判定：通常通过头尾指针相遇来判空/判满。
链式队列：
- 通过链表节点实现，入队以尾部插入，出队以头部删除，避免容量限制。
双端队列（Deque）：
- 同时支持队头出/队尾入、队尾出/队头入，灵活性更强。
优先队列（Priority Queue）：
- 根据优先级高低出队，常用堆实现（最大堆或最小堆）。

2.3 时间复杂度

入队/出队：通常 O(1)；具体取决于实现（循环队列和链式队列为 O(1)，数组实现需关注头指针移动）。

2.4 常见题型与解题思路

广度优先搜索（BFS）：图/树的层级遍历，典型用队列存放待访问节点。
队列实现题：用两栈实现队列、用队列实现滑动窗口等。
优先队列的应用：最小生成树的某些实现、Dijkstra、A* 等路径算法的核心结构。
双端队列在滑动窗口、回文判断等题型中的应用。

2.5 代码模板（Python）

循环队列（容量 fixed）

        
      
class CircularQueue:
  def __init__(self, k):
      self.data = [None] * k
      self.head = 0
      self.tail = 0
      self.size = 0
      self.capacity = k

  def enqueue(self, x):
      if self.is_full():
          raise IndexError("enqueue on full queue")
      self.data[self.tail] = x
      self.tail = (self.tail + 1) % self.capacity
      self.size += 1

  def dequeue(self):
      if self.is_empty():
          raise IndexError("dequeue from empty queue")
      val = self.data[self.head]
      self.data[self.head] = None
      self.head = (self.head + 1) % self.capacity
      self.size -= 1
      return val

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

  def is_full(self):
      return self.size == self.capacity

两栈实现队列（前面已有 MinStack 的思路）

        
      
class StackQueue:
  def __init__(self):
      self.in_stack = []
      self.out_stack = []

  def enqueue(self, x):
      self.in_stack.append(x)

  def dequeue(self):
      if not self.out_stack:
          while self.in_stack:
              self.out_stack.append(self.in_stack.pop())
      if not self.out_stack:
          raise IndexError("dequeue from empty queue")
      return self.out_stack.pop()

3. 双端队列与优先队列（Deque & Priority Queue）

3.1 双端队列（Deque）

支持在两端进行插入和删除的队列。
常见题型：滑动窗口中的维护、回文判定、队列的谓词性题型等。
实现：可以用 Python 的 collections.deque，或自实现循环数组/链表。

3.2 优先队列（Priority Queue）

元素带有优先级，出队时总是优先级最高的元素。
常见实现：二叉堆（MinHeap/MaxHeap）。
应用：Dijkstra/Prim 等算法、任务调度等。

代码模板（Python 内置 heapq 的简单示例）：

        
      
import heapq

class MinPriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        if not self.heap:
            raise IndexError("pop from empty priority queue")
        priority, item = heapq.heappop(self.heap)
        return item

    def is_empty(self):
        return not self.heap

4. 数组（Array）

4.1 基本概念

静态数组：长度固定，访问常数时间 O(1)，缺点是扩容和删除成本较高。
动态数组：容量可扩容，通常通过“容量翻倍”策略实现，平均摊销为 O(1) 访问/写入。

4.2 常见操作与复杂度

访问/赋值：O(1)
插入/删除（在中间位置）：O(n)（需要移动后续元素）
数组题型核心常用技巧：双指针、滑动窗口、二分查找、前缀和、差分等。

4.3 常见题型与解题思路

4.3.1 双指针法

适用场景：有序数组、需要在两端移动的条件等。
常见用途：删除重复、两数之和、子序列等。

示例：有序数组去除重复元素（就地去重，返回新长度）

        
      
def remove_duplicates(nums):
    if not nums:
        return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

4.3.2 两数之和（有序数组）

        
      
def two_sum_sorted(nums, target):
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            return (i, j)
        elif s < target:
            i += 1
        else:
            j -= 1
    return None

4.3.3 滑动窗口

目标：在一个可变窗口内维护和/最大长度/最小值等。
常见题型：最长无重复子串、满足条件的子数组长度、最小窗口覆盖等。

示例：最大和不超过 k 的子数组长度（简单版）

        
      
def max_subarray_len_under_k(nums, k):
    left = 0
    cur_sum = 0
    max_len = 0
    for right, val in enumerate(nums):
        cur_sum += val
        while cur_sum > k and left <= right:
            cur_sum -= nums[left]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

4.3.4 前缀和（Prefix Sum）

将数组转换为前缀和数组，快速求任意区间和。
常与二分、哈希结合解决子数组等问题。

示例：前缀和数组

        
      
def prefix_sums(nums):
    ps = [0]
    for x in nums:
        ps.append(ps[-1] + x)
    return ps

4.3.5 差分数组（Difference Array）

适用于多次区间加法，最后用前缀和得到结果。
典型题型：一段区间内统一修改某值，最后输出数组。

示例：

        
      
def difference_array(n, ops):
    diff = [0] * (n + 1)
    for l, r, val in ops:
        diff[l] += val
        if r + 1 < n:
            diff[r + 1] -= val
    ans = [0] * n
    cur = 0
    for i in range(n):
        cur += diff[i]
        ans[i] = cur
    return ans

4.3.6 二分查找（Binary Search）

在有序数组中定位目标值的下标，或找到满足特定条件的边界。
常见变体：lower_bound、upper_bound、find first/last等。

示例：

        
      
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

4.3.7 Kadane 算法（最大子数组和）

        
      
def max_subarray_sum(arr):
    if not arr:
        return 0
    max_so_far = curr = arr[0]
    for x in arr[1:]:
        curr = max(x, curr + x)
        max_so_far = max(max_so_far, curr)
    return max_so_far

5. 常见题型与解题模板

5.1 栈相关

括号匹配：使用栈保存左括号，遇到右括号进行匹配。
中缀转后缀表达式（Shunting-yard 算法的一部分思想）+ 逆波兰表达式求值。
字符串/表达式处理：如只包含数字、运算符、括号的表达式求值。
题型变体：需要在栈中同时维护额外信息（如最小值、计数等）。

模板要点：

先掌握基本栈操作及边界判断。
对复杂题，先把输入分成能被栈处理的子任务（如括号对齐、分块处理等）。

5.2 队列相关

BFS 实现：用队列按层逐层展开节点，常用于图遍历、树的层序遍历。
双端队列在滑动窗口/回文等题中的应用。
优先队列在最短路径、调度类题型中的应用。