栈是一种后进先出(LIFO)的数据结构，在前端开发中有着广泛的应用。

栈 (Stack) 数据结构

栈是一种后进先出(LIFO - Last In First Out)的数据结构，只能在一端进行插入和删除操作。

// 栈的核心操作

class Stack<T> {
  private items: T[] = [];

  push(item: T): void    // 入栈
  pop(): T | undefined   // 出栈
  peek(): T | undefined  // 查看栈顶
  isEmpty(): boolean     // 是否为空
  size(): number         // 栈大小
}

前端常见应用场景:

浏览器前进/后退历史
撤销/重做功能 (Ctrl+Z / Ctrl+Y)
函数调用栈
括号匹配验证
表达式求值
深度优先搜索 (DFS)

示例 1: 栈的基本操作

← 栈顶 (Top)

空栈

栈底 (Bottom) →

栈大小: 0

是否为空: 是

示例 2: 括号匹配（经典算法题）

判断字符串中的括号是否有效匹配。支持 ()、[]、

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (')]}'.includes(char)) {
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

示例 3: 浏览器历史记录

浏览器的前进/后退功能就是用两个栈实现的！

当前页面:

首页

后退栈 (Back Stack):

空

前进栈 (Forward Stack):

空

示例 4: 函数调用栈可视化

function bar() {
  console.log('Hello');
}
function foo() {
  bar();
}
function main() {
  foo();
}
main();

调用栈 (Call Stack):

空

执行日志:

重要概念： JavaScript 是单线程语言，函数调用通过调用栈管理。栈溢出(Stack Overflow)就是因为递归太深导致调用栈超出限制。

代码练习

在下面的编辑器中编写代码，点击"运行"按钮来测试你的解答。

有效的括号

简单

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

javascript

加载编辑器中...

1简单匹配

输入["()"]

期望true

2多种括号

输入["()[]{}"]

期望true

3嵌套括号

输入["({[]})"]

期望true

4不匹配

输入["(]"]

期望false

5顺序错误

输入["([)]"]

期望false

6空字符串

输入[""]

期望true

7只有左括号

输入["(("]

期望false

移除元素

简单

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量 k。要求：更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。

javascript

加载编辑器中...

1基本测试

移除所有的 3，剩余 [2, 2]

输入[[3,2,2,3],3]

期望2

2多个目标值

移除所有的 2，剩余 5 个元素

输入[[0,1,2,2,3,0,4,2],2]

期望5

3空数组

输入[[],1]

期望0

4全部移除

所有元素都等于 val

输入[[1,1,1],1]

期望0

5无需移除

没有元素等于 val

输入[[1,2,3],4]

期望3

6单元素匹配

输入[[1],1]

期望0

7单元素不匹配

输入[[1],2]

期望1

最小栈

中等

设计一个支持 push、pop、top 和 getMin 操作的栈。getMin 操作应该在常数时间内返回栈中的最小元素。

javascript

加载编辑器中...

1基本操作

push -2, push 0, push -3, getMin, pop, top, getMin

输入[["push","push","push","getMin","pop","top","getMin"],[-2,0,-3,null,null,null,null]]

期望[null,null,null,-3,null,0,-2]

2相同最小值

输入[["push","push","push","getMin","pop","getMin"],[1,1,1,null,null,null]]

期望[null,null,null,1,null,1]

API 文档

栈 (Stack)

概念介绍

栈是一种遵循**后进先出(LIFO - Last In First Out)**原则的线性数据结构。想象一摞盘子，你只能从最上面取或放盘子。

核心特点

后进先出: 最后添加的元素最先被移除
单端操作: 只能在栈顶进行插入和删除
时间复杂度: push 和 pop 操作都是 O(1)

基本操作

操作	描述	时间复杂度
push(item)	将元素添加到栈顶	O(1)
pop()	移除并返回栈顶元素	O(1)
peek()	返回栈顶元素但不移除	O(1)
isEmpty()	检查栈是否为空	O(1)
size()	返回栈中元素数量	O(1)

JavaScript/TypeScript 实现

class Stack<T> {
  private items: T[] = [];

  // 入栈 - 将元素添加到栈顶
  push(item: T): void {
    this.items.push(item);
  }

  // 出栈 - 移除并返回栈顶元素
  pop(): T | undefined {
    return this.items.pop();
  }

  // 查看栈顶元素
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  isEmpty(): boolean {
    return this.items.length === 0;
  }

  // 获取栈的大小
  size(): number {
    return this.items.length;
  }

  // 清空栈
  clear(): void {
    this.items = [];
  }
}

前端应用场景

1. 浏览器历史记录

// 后退栈：记录访问过的页面
const backStack = [];
// 前进栈：记录后退后可以前进的页面
const forwardStack = [];

function visit(page) {
  backStack.push(currentPage);
  currentPage = page;
  forwardStack.length = 0; // 清空前进栈
}

function goBack() {
  if (backStack.length === 0) return;
  forwardStack.push(currentPage);
  currentPage = backStack.pop();
}

function goForward() {
  if (forwardStack.length === 0) return;
  backStack.push(currentPage);
  currentPage = forwardStack.pop();
}

2. 撤销/重做功能

const undoStack = [];
const redoStack = [];

function doAction(action) {
  undoStack.push(action);
  redoStack.length = 0;
  executeAction(action);
}

function undo() {
  if (undoStack.length === 0) return;
  const action = undoStack.pop();
  redoStack.push(action);
  reverseAction(action);
}

function redo() {
  if (redoStack.length === 0) return;
  const action = redoStack.pop();
  undoStack.push(action);
  executeAction(action);
}

3. 括号匹配（LeetCode 20）

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (')]}'.includes(char)) {
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

// 测试
isValid("()");      // true
isValid("()[]{}");  // true
isValid("(]");      // false
isValid("([)]");    // false
isValid("{[]}");    // true

4. 表达式求值

// 逆波兰表达式求值 (LeetCode 150)
function evalRPN(tokens) {
  const stack = [];
  const operators = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };

  for (const token of tokens) {
    if (token in operators) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(operators[token](a, b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}

面试高频题

1. 最小栈 (LeetCode 155)

设计一个支持 push, pop, top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = []; // 辅助栈，存储最小值
  }

  push(val) {
    this.stack.push(val);
    // 如果辅助栈为空或当前值更小，入辅助栈
    if (this.minStack.length === 0 ||
        val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }

  pop() {
    const val = this.stack.pop();
    // 如果弹出的是最小值，辅助栈也要弹出
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
    return val;
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

2. 用栈实现队列 (LeetCode 232)

class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  push(x) {
    this.inStack.push(x);
  }

  pop() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }

  peek() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack[this.outStack.length - 1];
  }

  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

3. 每日温度 (LeetCode 739)

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = []; // 存储索引

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 &&
           temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      result[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }
  return result;
}

与函数调用栈

JavaScript 引擎使用调用栈来管理函数执行：

function main() {
  console.log('main start');
  foo();
  console.log('main end');
}

function foo() {
  console.log('foo start');
  bar();
  console.log('foo end');
}

function bar() {
  console.log('bar');
}

main();
// 输出顺序：
// main start
// foo start
// bar
// foo end
// main end

调用栈变化：

main() 入栈
foo() 入栈
bar() 入栈
bar() 执行完毕，出栈
foo() 执行完毕，出栈
main() 执行完毕，出栈

复杂度分析

操作	时间复杂度	空间复杂度
push	O(1)	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)
isEmpty	O(1)	O(1)
整体空间	-	O(n)

总结

栈是前端开发中非常重要的数据结构：

简单高效: 操作简单，时间复杂度低
应用广泛: 函数调用、历史记录、撤销重做
面试必考: 括号匹配、表达式求值等经典问题
理解 JS 运行机制: 调用栈是理解 JavaScript 执行的基础