栈与队列(进阶篇) - 高级技巧与优化

在基础篇中,我们学习了栈和队列的基本概念和实现。本篇将深入探讨高级技巧:循环队列、单调栈、最小栈等,以及如何用它们解决复杂问题。

一、问题引入

场景1: 性能瓶颈

// 基础队列的性能问题
const queue = [];
for (let i = 0; i < 100000; i++) {
  queue.push(i);
  queue.shift(); // O(n) 操作,总复杂度 O(n²)
}
// 如何优化到 O(1)?

场景2: 股票价格分析

// 找到每天之后第一个更高的价格
const prices = [73, 74, 75, 71, 69, 72, 76, 73];
// 对于 73,下一个更高价格是 74
// 对于 71,下一个更高价格是 72
// 如何高效计算?

场景3: 实时监控

// 需要随时获取当前最小值
const monitor = new MinStack();
monitor.push(5);
monitor.push(3);
monitor.push(7);
console.log(monitor.getMin()); // 3,要求 O(1)

这些问题需要用到循环队列、单调栈、最小栈等高级数据结构。

二、循环队列 - O(1) 的高效队列

原理

循环队列使用固定大小的数组,通过移动指针而不是移动元素来实现高效的入队出队。

初始状态(容量=5):
[_, _, _, _, _]
  ↑           
front/rear

入队 1,2,3:
[1, 2, 3, _, _]
  ↑        ↑
front    rear

出队 1:
[1, 2, 3, _, _]
    ↑     ↑
  front  rear

继续入队 4,5:
[1, 2, 3, 4, 5]
    ↑        ↑
  front    rear(满)

出队 2,3,入队 6,7:
[6, 7, 3, 4, 5]
        ↑     ↑
      rear  front

形成环形!

完整实现

/**
  * 循环队列 - O(1) 的入队和出队
  */
class CircularQueue<T> {
  private items: (T | undefined)[];
  private front: number = 0;  // 队首指针
  private rear: number = 0;   // 队尾指针
  private count: number = 0;  // 元素个数
  private capacity: number;   // 容量
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity);
  }
  
  /**
    * 入队 - O(1)
    */
  enqueue(item: T): boolean {
    if (this.isFull()) {
      return false;
    }
    
    this.items[this.rear] = item;
    this.rear = (this.rear + 1) % this.capacity; // 循环
    this.count++;
    return true;
  }
  
  /**
    * 出队 - O(1)
    */
  dequeue(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    
    const item = this.items[this.front];
    this.items[this.front] = undefined; // 清理
    this.front = (this.front + 1) % this.capacity; // 循环
    this.count--;
    return item;
  }
  
  /**
    * 查看队首 - O(1)
    */
  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[this.front];
  }
  
  /**
    * 判断是否为空
    */
  isEmpty(): boolean {
    return this.count === 0;
  }
  
  /**
    * 判断是否已满
    */
  isFull(): boolean {
    return this.count === this.capacity;
  }
  
  /**
    * 获取大小
    */
  size(): number {
    return this.count;
  }
  
  /**
    * 打印队列(用于调试)
    */
  toString(): string {
    if (this.isEmpty()) return '[]';
    
    const result: T[] = [];
    let index = this.front;
    for (let i = 0; i < this.count; i++) {
      result.push(this.items[index]!);
      index = (index + 1) % this.capacity;
    }
    return `[${result.join(', ')}]`;
  }
}

// 测试
const queue = new CircularQueue<number>(3);
console.log(queue.enqueue(1)); // true
console.log(queue.enqueue(2)); // true
console.log(queue.enqueue(3)); // true
console.log(queue.enqueue(4)); // false (队列已满)
console.log(queue.toString()); // [1, 2, 3]

console.log(queue.dequeue());  // 1
console.log(queue.enqueue(4)); // true (现在有空间了)
console.log(queue.toString()); // [2, 3, 4]

关键技巧

1. 取模运算实现循环:

// 不使用 if 判断,直接取模
this.rear = (this.rear + 1) % this.capacity;

// 例如 capacity = 5:
// 0 → 1 → 2 → 3 → 4 → 0 → 1 ...

2. 使用 count 判断空/满:

// 避免 front === rear 的歧义
isEmpty(): count === 0
isFull(): count === capacity

性能对比

三、单调栈 - 下一个更大元素

原理

单调栈维护栈内元素的单调性(递增或递减),用于快速找到"下一个更大/更小元素"。

问题: 找到每个元素右边第一个更大的元素
输入: [2, 1, 5, 6, 2, 3]

使用单调递减栈:

i=0, val=2:
  stack=[] → push(0)
  stack=[2]

i=1, val=1:
  1 < 2,直接入栈
  stack=[2, 1]

i=2, val=5:
  5 > 1,弹出 1,答案是 5
  5 > 2,弹出 2,答案是 5
  stack=[5]

i=3, val=6:
  6 > 5,弹出 5,答案是 6
  stack=[6]

i=4, val=2:
  2 < 6,直接入栈
  stack=[6, 2]

i=5, val=3:
  3 > 2,弹出 2,答案是 3
  3 < 6,入栈
  stack=[6, 3]

结果: [5, 5, 6, -1, 3, -1]

实现

/**
  * 找到每个元素右边第一个更大的元素
  * @param nums - 输入数组
  * @return 结果数组,-1 表示不存在
  */
function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // 存储索引
  
  for (let i = 0; i < n; i++) {
    // 当前元素大于栈顶元素时,找到了栈顶元素的答案
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

// 测试
console.log(nextGreaterElements([2, 1, 5, 6, 2, 3]));
// [5, 5, 6, -1, 3, -1]

console.log(nextGreaterElements([1, 2, 3, 4, 5]));
// [2, 3, 4, 5, -1]

console.log(nextGreaterElements([5, 4, 3, 2, 1]));
// [-1, -1, -1, -1, -1]

时间复杂度证明

虽然有嵌套循环,但:
- 每个元素最多入栈一次: O(n)
- 每个元素最多出栈一次: O(n)

总时间复杂度: O(n)

变体:循环数组

/**
  * 循环数组中下一个更大元素
  * 例: [1,2,1] → [2,-1,2] (最后的1可以循环到开头的2)
  */
function nextGreaterElementsCircular(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  
  // 遍历两遍数组,模拟循环
  for (let i = 0; i < n * 2; i++) {
    const index = i % n;
    
    while (stack.length && nums[index] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop()!;
      result[idx] = nums[index];
    }
    
    // 只在第一遍时入栈
    if (i < n) {
      stack.push(index);
    }
  }
  
  return result;
}

// 测试
console.log(nextGreaterElementsCircular([1, 2, 1]));
// [2, -1, 2]

四、每日温度问题

/**
  * 每日温度:找到下一个更高温度的天数
  * 例: [73,74,75,71,69,72,76,73]
  * 输出: [1,1,4,2,1,1,0,0]
  */
function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack: number[] = []; // 存储索引
  
  for (let i = 0; i < n; i++) {
    while (
      stack.length && 
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const index = stack.pop()!;
      result[index] = i - index; // 计算天数差
    }
    stack.push(i);
  }
  
  return result;
}

// 测试
console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]));
// [1, 1, 4, 2, 1, 1, 0, 0]

可视化:

温度: [73, 74, 75, 71, 69, 72, 76, 73]
索引:  0   1   2   3   4   5   6   7

i=0: stack=[0]
i=1: 74>73, 弹出0, result[0]=1-0=1
      stack=[1]
i=2: 75>74, 弹出1, result[1]=2-1=1
      stack=[2]
i=3: 71<75, stack=[2,3]
i=4: 69<71, stack=[2,3,4]
i=5: 72>69, 弹出4, result[4]=5-4=1
      72>71, 弹出3, result[3]=5-3=2
      72<75, stack=[2,5]
i=6: 76>72, 弹出5, result[5]=6-5=1
      76>75, 弹出2, result[2]=6-2=4
      stack=[6]
i=7: 73<76, stack=[6,7]

剩余元素没有答案,保持为0

实际应用:

• 股票价格分析
• 性能监控告警
• 天气预报系统

五、最小栈 - O(1) 获取最小值

原理

使用辅助栈记录每个状态下的最小值。

操作序列:
push(5): stack=[5], minStack=[5]
push(3): stack=[5,3], minStack=[5,3]
push(7): stack=[5,3,7], minStack=[5,3,3]
getMin(): 返回 3
pop():   stack=[5,3], minStack=[5,3]
getMin(): 返回 3
pop():   stack=[5], minStack=[5]
getMin(): 返回 5

实现

/**
  * 最小栈 - 支持 O(1) 时间获取最小值
  */
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = []; // 辅助栈
  
  /**
    * 入栈
    */
  push(val: number): void {
    this.stack.push(val);
    
    // 更新最小值栈
    if (this.minStack.length === 0) {
      this.minStack.push(val);
    } else {
      const currentMin = this.minStack[this.minStack.length - 1];
      this.minStack.push(Math.min(currentMin, val));
    }
  }
  
  /**
    * 出栈
    */
  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }
  
  /**
    * 获取栈顶元素
    */
  top(): number {
    return this.stack[this.stack.length - 1];
  }
  
  /**
    * 获取最小值 - O(1)
    */
  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
  
  /**
    * 打印状态(调试用)
    */
  debug(): void {
    console.log('stack:', this.stack);
    console.log('minStack:', this.minStack);
  }
}

// 测试
const minStack = new MinStack();
minStack.push(5);
minStack.push(3);
minStack.push(7);
minStack.push(2);
minStack.debug();
// stack: [5, 3, 7, 2]
// minStack: [5, 3, 3, 2]

console.log(minStack.getMin()); // 2
minStack.pop();
console.log(minStack.getMin()); // 3
minStack.pop();
console.log(minStack.getMin()); // 3

空间优化版本

/**
  * 最小栈(空间优化版)
  * 只在最小值变化时才记录
  */
class MinStackOptimized {
  private stack: number[] = [];
  private minStack: number[] = [];
  
  push(val: number): void {
    this.stack.push(val);
    
    // 只有当新值 <= 当前最小值时才入 minStack
    if (
      this.minStack.length === 0 || 
      val <= this.minStack[this.minStack.length - 1]
    ) {
      this.minStack.push(val);
    }
  }
  
  pop(): void {
    const val = this.stack.pop()!;
    
    // 如果弹出的是最小值,也要从 minStack 弹出
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }
  
  top(): number {
    return this.stack[this.stack.length - 1];
  }
  
  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

// 测试
const minStack2 = new MinStackOptimized();
minStack2.push(5);
minStack2.push(3);
minStack2.push(7); // 7 不入 minStack
minStack2.push(3); // 3 入 minStack(等于当前最小值)
console.log(minStack2.getMin()); // 3

空间对比:

输入: [5, 3, 7, 8, 9, 2]

普通版本:
minStack = [5, 3, 3, 3, 3, 2]  (6个元素)

优化版本:
minStack = [5, 3, 2]  (3个元素)

六、逆波兰表达式求值

什么是逆波兰表达式?

中缀表达式: 3 + 5 * 2
后缀表达式(逆波兰): 3 5 2 * +

优势:
- 不需要括号
- 不需要考虑优先级
- 从左到右扫描即可

实现

/**
  * 计算逆波兰表达式(后缀表达式)
  * 例: ["2","1","+","3","*"] → ((2 + 1) * 3) = 9
  */
function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  const operators = new Set(['+', '-', '*', '/']);
  
  for (const token of tokens) {
    if (operators.has(token)) {
      // 弹出两个操作数(注意顺序)
      const b = stack.pop()!;
      const a = stack.pop()!;
      
      // 计算结果并入栈
      let result: number;
      switch (token) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = Math.trunc(a / b); break; // 向零截断
        default: result = 0;
      }
      stack.push(result);
    } else {
      // 操作数入栈
      stack.push(parseInt(token));
    }
  }
  
  return stack[0];
}

// 测试
console.log(evalRPN(["2", "1", "+", "3", "*"]));
// 9

console.log(evalRPN(["4", "13", "5", "/", "+"]));
// 6 (4 + (13 / 5) = 4 + 2 = 6)

console.log(evalRPN(["10","6","9","3","+","-11","*","/","*","17","+","5","+"]));
// 22

可视化过程:

输入: ["2", "1", "+", "3", "*"]

读取 "2": stack = [2]
读取 "1": stack = [2, 1]
读取 "+": 弹出 1,2, 计算 2+1=3, stack = [3]
读取 "3": stack = [3, 3]
读取 "*": 弹出 3,3, 计算 3*3=9, stack = [9]

结果: 9

七、中缀表达式转后缀表达式

调度场算法 (Shunting Yard Algorithm)

/**
  * 中缀表达式转后缀表达式
  * 例: "3 + 5 * 2" → ["3", "5", "2", "*", "+"]
  */
function infixToPostfix(expression: string): string[] {
  const output: string[] = [];
  const operators: string[] = [];
  
  // 运算符优先级
  const precedence: Record<string, number> = {
    '+': 1, '-': 1,
    '*': 2, '/': 2
  };
  
  const tokens = expression.split(' ');
  
  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      // 操作数直接输出
      output.push(token);
    } else if (token === '(') {
      // 左括号入栈
      operators.push(token);
    } else if (token === ')') {
      // 右括号:弹出直到遇到左括号
      while (operators.length && operators[operators.length - 1] !== '(') {
        output.push(operators.pop()!);
      }
      operators.pop(); // 弹出左括号
    } else {
      // 运算符:弹出优先级 >= 当前运算符的
      while (
        operators.length &&
        operators[operators.length - 1] !== '(' &&
        precedence[operators[operators.length - 1]] >= precedence[token]
      ) {
        output.push(operators.pop()!);
      }
      operators.push(token);
    }
  }
  
  // 弹出剩余运算符
  while (operators.length) {
    output.push(operators.pop()!);
  }
  
  return output;
}

// 测试
console.log(infixToPostfix("3 + 5 * 2"));
// ["3", "5", "2", "*", "+"]

console.log(infixToPostfix("( 1 + 2 ) * 3"));
// ["1", "2", "+", "3", "*"]

console.log(infixToPostfix("3 + 4 * 2 / ( 1 - 5 )"));
// ["3", "4", "2", "*", "1", "5", "-", "/", "+"]

可视化过程:

输入: "3 + 5 * 2"

读取 "3": output=["3"], operators=[]
读取 "+": output=["3"], operators=["+"]
读取 "5": output=["3","5"], operators=["+"]
读取 "*": * 优先级高,入栈
          output=["3","5"], operators=["+","*"]
读取 "2": output=["3","5","2"], operators=["+","*"]
结束:     弹出所有运算符
          output=["3","5","2","*","+"]

完整计算器

/**
  * 完整计算器:中缀表达式 → 后缀表达式 → 计算结果
  */
function calculate(expression: string): number {
  const postfix = infixToPostfix(expression);
  return evalRPN(postfix);
}

// 测试
console.log(calculate("3 + 5 * 2"));           // 13
console.log(calculate("( 1 + 2 ) * 3"));       // 9
console.log(calculate("10 + 2 * 6"));          // 22
console.log(calculate("100 * ( 2 + 12 )"));    // 1400

八、单调队列 - 滑动窗口最大值

原理

使用双端队列维护窗口内的最大值索引。

输入: nums=[1,3,-1,-3,5,3,6,7], k=3

维护单调递减队列(存储索引):

i=0, val=1: deque=[0]
i=1, val=3: 3>1, 移除0, deque=[1]
i=2, val=-1: deque=[1,2], 窗口形成, max=nums[1]=3

i=3, val=-3: deque=[1,2,3], max=nums[1]=3
i=4, val=5: 移除1(窗口外),移除2,3(小于5)
            deque=[4], max=nums[4]=5
i=5, val=3: deque=[4,5], max=nums[4]=5
i=6, val=6: 移除4(窗口外),移除5(小于6)
            deque=[6], max=nums[6]=6
i=7, val=7: 移除6(小于7), deque=[7], max=nums[7]=7

结果: [3, 3, 5, 5, 6, 7]

实现

/**
  * 滑动窗口最大值
  */
function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // 存储索引,保持单调递减
  
  for (let i = 0; i < nums.length; i++) {
    // 移除窗口外的元素
    while (deque.length && deque[0] <= i - k) {
      deque.shift();
    }
    
    // 移除所有小于当前元素的值(维护单调性)
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // 窗口形成后,记录最大值
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

// 测试
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]

console.log(maxSlidingWindow([1], 1));
// [1]

console.log(maxSlidingWindow([1,-1], 1));
// [1, -1]

时间复杂度: O(n) - 每个元素最多入队出队一次

九、复杂度分析

各种栈/队列操作对比

空间复杂度

• 循环队列: O(k),k 为容量
• 最小栈: O(n),需要辅助栈
• 单调栈/队列: O(n),最坏情况存储所有元素

十、练习题

题目1: 柱状图中最大的矩形 (LeetCode 84)

难度: 困难

题目描述: 给定 n 个非负整数表示柱状图中各个柱子的高度,求柱状图中最大的矩形面积。

/**
  * @param heights - 柱子高度数组
  * @return 最大矩形面积
  */
function largestRectangleArea(heights: number[]): number {
  // 在这里实现你的代码
}

// 测试用例
console.log(largestRectangleArea([2,1,5,6,2,3])); // 10
console.log(largestRectangleArea([2,4]));         // 4

提示: 使用单调栈,找到每个柱子左右两边第一个更矮的柱子。

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  
  // 在数组末尾添加0,确保所有柱子都能被处理
  heights.push(0);
  
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
      const h = heights[stack.pop()!];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  
  return maxArea;
}

题目2: 接雨水 (LeetCode 42)

难度: 困难

题目描述: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算下雨后能接多少雨水。

/**
  * @param height - 高度数组
  * @return 能接的雨水总量
  */
function trap(height: number[]): number {
  // 在这里实现你的代码
}

// 测试用例
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trap([4,2,0,3,2,5]));             // 9

提示: 使用单调栈或双指针。

题目3: 设计循环双端队列 (LeetCode 641)

难度: 中等

题目描述: 设计实现双端队列,支持从前后两端添加和删除元素。

class MyCircularDeque {
  constructor(k: number) {
    // 初始化
  }
  
  insertFront(value: number): boolean {
    // 从前端插入
  }
  
  insertLast(value: number): boolean {
    // 从后端插入
  }
  
  deleteFront(): boolean {
    // 从前端删除
  }
  
  deleteLast(): boolean {
    // 从后端删除
  }
  
  getFront(): number {
    // 获取前端元素
  }
  
  getRear(): number {
    // 获取后端元素
  }
  
  isEmpty(): boolean {
    // 判断是否为空
  }
  
  isFull(): boolean {
    // 判断是否已满
  }
}

十一、总结

核心要点

1. 循环队列: 用取模实现循环,O(1) 的出队操作
2. 单调栈: 维护单调性,快速找到下一个更大/更小元素
3. 最小栈: 用辅助栈记录最小值,O(1) 查询
4. 单调队列: 滑动窗口最值问题的利器

适用场景

识别信号

• ✅ 需要高效出队 → 循环队列
• ✅ 找下一个更大/小 → 单调栈
• ✅ 需要实时最值 → 最小栈/单调队列
• ✅ 滑动窗口最值 → 单调队列
• ✅ 表达式求值 → 栈 + 调度场算法

下期预告

在实战篇中,我们将学习:

• 浏览器历史记录的完整实现
• 异步任务队列与并发控制
• LRU 缓存的高效实现
• 撤销重做系统设计

相关资源:

• LeetCode 单调栈题单
• 可视化算法
• 本系列代码仓库