知识库

Appearance

JavaScript 堆栈详解 ​

一、栈（Stack）基础概念 ​

1.1 什么是栈？ ​

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构。可以把它想象成一摞盘子：

  • 只能从顶部放盘子（入栈/push）
  • 只能从顶部取盘子（出栈/pop）
  • 最先放的盘子在底部，最后才能取到

1.2 栈的核心操作 ​

操作描述时间复杂度
push()入栈，添加元素到栈顶O(1)
pop()出栈，移除并返回栈顶元素O(1)
peek()/top()查看栈顶元素（不移除）O(1)
isEmpty()判断栈是否为空O(1)
size()返回栈中元素个数O(1)

1.3 JavaScript 中的栈实现 ​

方式一：使用数组 ​

javascript
class Stack {
  constructor() {
    this.items = []
  }

  push(element) {
    this.items.push(element)
  }

  pop() {
    if (this.isEmpty()) return undefined
    return this.items.pop()
  }

  peek() {
    if (this.isEmpty()) return undefined
    return this.items[this.items.length - 1]
  }

  isEmpty() {
    return this.items.length === 0
  }

  size() {
    return this.items.length
  }

  clear() {
    this.items = []
  }
}

const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.peek()) // 3
console.log(stack.pop()) // 3
console.log(stack.size()) // 2

方式二：使用对象（更高效） ​

javascript
class Stack {
  constructor() {
    this.items = {}
    this.count = 0
  }

  push(element) {
    this.items[this.count] = element
    this.count++
  }

  pop() {
    if (this.isEmpty()) return undefined
    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }

  peek() {
    if (this.isEmpty()) return undefined
    return this.items[this.count - 1]
  }

  isEmpty() {
    return this.count === 0
  }

  size() {
    return this.count
  }

  clear() {
    this.items = {}
    this.count = 0
  }
}

方式三：使用链表实现 ​

javascript
class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class Stack {
  constructor() {
    this.top = null
    this.size = 0
  }

  push(value) {
    const node = new Node(value)
    node.next = this.top
    this.top = node
    this.size++
  }

  pop() {
    if (!this.top) return undefined
    const value = this.top.value
    this.top = this.top.next
    this.size--
    return value
  }

  peek() {
    return this.top ? this.top.value : undefined
  }

  isEmpty() {
    return this.size === 0
  }
}

二、JavaScript 调用栈 ​

2.1 什么是调用栈？ ​

JavaScript 是单线程语言，调用栈用于管理函数执行顺序：

  1. 函数调用时：推入栈顶
  2. 函数返回时：从栈顶弹出
  3. 栈底：全局执行上下文

2.2 调用栈示例 ​

javascript
function first() {
  console.log('first start')
  second()
  console.log('first end')
}

function second() {
  console.log('second start')
  third()
  console.log('second end')
}

function third() {
  console.log('third')
}

first()

// 输出顺序：
// first start
// second start
// third
// second end
// first end

调用栈变化过程：

1. first() 调用 → [global, first]
2. second() 调用 → [global, first, second]
3. third() 调用 → [global, first, second, third]
4. third() 返回 → [global, first, second]
5. second() 返回 → [global, first]
6. first() 返回 → [global]

2.3 栈溢出（Stack Overflow） ​

当调用栈超出最大容量时，会抛出栈溢出错误：

javascript
function recursive() {
  recursive()
}

recursive() // RangeError: Maximum call stack size exceeded

2.4 堆内存 vs 栈内存 ​

特性栈内存堆内存
存储内容基本类型、引用地址对象、数组等引用类型
大小固定，较小动态，较大
分配方式自动分配释放手动/垃圾回收
访问速度快相对慢
生命周期函数执行完毕即释放由垃圾回收机制管理
javascript
// 栈内存示例
let a = 10
let b = a // 值复制
b = 20
console.log(a) // 10（互不影响）

// 堆内存示例
let obj1 = { name: 'Alice' }
let obj2 = obj1 // 引用复制
obj2.name = 'Bob'
console.log(obj1.name) // 'Bob'（指向同一对象）

三、栈的应用场景 ​

3.1 函数调用管理 ​

  • 维护函数执行上下文
  • 管理递归调用

3.2 括号匹配 ​

javascript
function isValidParentheses(s) {
  const stack = []
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

  for (const char of s) {
    if (['(', '[', '{'].includes(char)) {
      stack.push(char)
    } else {
      if (stack.pop() !== map[char]) {
        return false
      }
    }
  }

  return stack.length === 0
}

console.log(isValidParentheses('()[]{}')) // true
console.log(isValidParentheses('([)]')) // false

3.3 表达式求值 ​

javascript
function calculate(s) {
  const stack = []
  let num = 0
  let sign = '+'

  for (let i = 0; i <= s.length; i++) {
    const char = s[i]

    if (char >= '0' && char <= '9') {
      num = num * 10 + parseInt(char)
    }

    if (((char < '0' || char > '9') && char !== ' ') || i === s.length) {
      switch (sign) {
        case '+':
          stack.push(num)
          break
        case '-':
          stack.push(-num)
          break
        case '*':
          stack.push(stack.pop() * num)
          break
        case '/':
          stack.push(Math.trunc(stack.pop() / num))
          break
      }
      sign = char
      num = 0
    }
  }

  return stack.reduce((a, b) => a + b, 0)
}

console.log(calculate('3+2*2')) // 7

3.4 浏览器历史记录 ​

javascript
class BrowserHistory {
  constructor() {
    this.backStack = []
    this.forwardStack = []
  }

  visit(url) {
    this.backStack.push(url)
    this.forwardStack = []
    console.log(`访问: ${url}`)
  }

  back() {
    if (this.backStack.length <= 1) {
      console.log('无法后退')
      return
    }
    const current = this.backStack.pop()
    this.forwardStack.push(current)
    console.log(`后退到: ${this.backStack[this.backStack.length - 1]}`)
  }

  forward() {
    if (this.forwardStack.length === 0) {
      console.log('无法前进')
      return
    }
    const url = this.forwardStack.pop()
    this.backStack.push(url)
    console.log(`前进到: ${url}`)
  }
}

const browser = new BrowserHistory()
browser.visit('a.com')
browser.visit('b.com')
browser.visit('c.com')
browser.back() // 后退到: b.com
browser.forward() // 前进到: c.com

3.5 撤销/重做功能 ​

javascript
class UndoRedo {
  constructor() {
    this.undoStack = []
    this.redoStack = []
  }

  do(action) {
    this.undoStack.push(action)
    this.redoStack = []
    console.log(`执行: ${action}`)
  }

  undo() {
    if (this.undoStack.length === 0) return
    const action = this.undoStack.pop()
    this.redoStack.push(action)
    console.log(`撤销: ${action}`)
    return action
  }

  redo() {
    if (this.redoStack.length === 0) return
    const action = this.redoStack.pop()
    this.undoStack.push(action)
    console.log(`重做: ${action}`)
    return action
  }
}

四、20道栈面试题及答案 ​

题目1：实现一个栈，使得入栈、出栈、查找栈顶元素时间复杂度均为 O(1) ​

答案：

javascript
class Stack {
  constructor() {
    this.items = {}
    this.count = 0
  }

  // 入栈 O(1)
  push(element) {
    this.items[this.count] = element
    this.count++
    return this.count
  }

  // 出栈 O(1)
  pop() {
    if (this.isEmpty()) return undefined
    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }

  // 查找栈顶元素 O(1)
  peek() {
    if (this.isEmpty()) return undefined
    return this.items[this.count - 1]
  }

  isEmpty() {
    return this.count === 0
  }

  size() {
    return this.count
  }
}

// 测试
const stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.peek()) // 3
console.log(stack.pop()) // 3
console.log(stack.peek()) // 2

解析： 使用对象存储，count 作为索引，三个核心操作都是直接访问属性，时间复杂度为 O(1)。

题目2：用两个栈实现队列 ​

答案：

javascript
class QueueWithStacks {
  constructor() {
    this.stackIn = [] // 入队栈
    this.stackOut = [] // 出队栈
  }

  // 入队
  enqueue(x) {
    this.stackIn.push(x)
  }

  // 出队
  dequeue() {
    if (this.stackOut.length === 0) {
      // 将入队栈所有元素倒入出队栈
      while (this.stackIn.length > 0) {
        this.stackOut.push(this.stackIn.pop())
      }
    }
    return this.stackOut.pop()
  }

  // 查看队首
  peek() {
    if (this.stackOut.length === 0) {
      while (this.stackIn.length > 0) {
        this.stackOut.push(this.stackIn.pop())
      }
    }
    return this.stackOut[this.stackOut.length - 1]
  }

  isEmpty() {
    return this.stackIn.length === 0 && this.stackOut.length === 0
  }
}

const queue = new QueueWithStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.dequeue()) // 1
console.log(queue.dequeue()) // 2

题目3：用两个队列实现栈 ​

答案：

javascript
class StackWithQueues {
  constructor() {
    this.queue1 = []
    this.queue2 = []
  }

  push(x) {
    // 将元素放入空队列
    if (this.queue1.length === 0) {
      this.queue1.push(x)
      while (this.queue2.length > 0) {
        this.queue1.push(this.queue2.shift())
      }
    } else {
      this.queue2.push(x)
      while (this.queue1.length > 0) {
        this.queue2.push(this.queue1.shift())
      }
    }
  }

  pop() {
    if (this.queue1.length > 0) {
      return this.queue1.shift()
    }
    return this.queue2.shift()
  }

  top() {
    if (this.queue1.length > 0) {
      return this.queue1[0]
    }
    return this.queue2[0]
  }

  isEmpty() {
    return this.queue1.length === 0 && this.queue2.length === 0
  }
}

题目4：实现一个包含 min 函数的栈，要求 push、pop、min 都是 O(1) ​

答案：

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

  push(x) {
    this.stack.push(x)
    // 最小栈压入当前最小值
    if (
      this.minStack.length === 0 ||
      x <= this.minStack[this.minStack.length - 1]
    ) {
      this.minStack.push(x)
    } else {
      this.minStack.push(this.minStack[this.minStack.length - 1])
    }
  }

  pop() {
    if (this.stack.length === 0) return undefined
    this.minStack.pop()
    return this.stack.pop()
  }

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

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

const minStack = new MinStack()
minStack.push(5)
minStack.push(3)
minStack.push(4)
console.log(minStack.getMin()) // 3
minStack.pop()
console.log(minStack.getMin()) // 3
minStack.pop()
console.log(minStack.getMin()) // 5

题目5：有效的括号 ​

答案：

javascript
function isValid(s) {
  const stack = []
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

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

  return stack.length === 0
}

console.log(isValid('()[]{}')) // true
console.log(isValid('([)]')) // false
console.log(isValid('{[]}')) // true

题目6：最长有效括号 ​

答案：

javascript
function longestValidParentheses(s) {
  const stack = [-1] // 栈底存-1作为基准
  let maxLen = 0

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i)
    } else {
      stack.pop()
      if (stack.length === 0) {
        stack.push(i) // 新的基准
      } else {
        maxLen = Math.max(maxLen, i - stack[stack.length - 1])
      }
    }
  }

  return maxLen
}

console.log(longestValidParentheses('(()')) // 2
console.log(longestValidParentheses(')()())')) // 4

题目7：每日温度（下一个更高温度） ​

答案：

javascript
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 idx = stack.pop()
      result[idx] = i - idx
    }
    stack.push(i)
  }

  return result
}

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

题目8：下一个更大元素 ​

答案：

javascript
function nextGreaterElement(nums1, nums2) {
  const map = new Map()
  const stack = []

  // 对 nums2 使用单调栈
  for (const num of nums2) {
    while (stack.length > 0 && num > stack[stack.length - 1]) {
      map.set(stack.pop(), num)
    }
    stack.push(num)
  }

  // 剩余元素没有更大值
  while (stack.length > 0) {
    map.set(stack.pop(), -1)
  }

  return nums1.map(num => map.get(num))
}

console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))
// [-1, 3, -1]

题目9：柱状图中最大的矩形 ​

答案：

javascript
function largestRectangleArea(heights) {
  heights.push(0) // 添加哨兵
  const stack = []
  let maxArea = 0

  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && 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
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])) // 10

题目10：接雨水 ​

答案：

javascript
function trap(height) {
  const stack = []
  let water = 0

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const mid = stack.pop()
      if (stack.length === 0) break

      const left = stack[stack.length - 1]
      const h = Math.min(height[left], height[i]) - height[mid]
      const w = i - left - 1
      water += h * w
    }
    stack.push(i)
  }

  return water
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) // 6

题目11：简化路径 ​

答案：

javascript
function simplifyPath(path) {
  const stack = []
  const parts = path.split('/')

  for (const part of parts) {
    if (part === '' || part === '.') {
      continue
    } else if (part === '..') {
      stack.pop()
    } else {
      stack.push(part)
    }
  }

  return '/' + stack.join('/')
}

console.log(simplifyPath('/home/')) // '/home'
console.log(simplifyPath('/../')) // '/'
console.log(simplifyPath('/home//foo/')) // '/home/foo'
console.log(simplifyPath('/a/./b/../../c/')) // '/c'

题目12：逆波兰表达式求值 ​

答案：

javascript
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 (operators[token]) {
      const b = stack.pop()
      const a = stack.pop()
      stack.push(operators[token](a, b))
    } else {
      stack.push(parseInt(token))
    }
  }

  return stack[0]
}

console.log(evalRPN(['2', '1', '+', '3', '*'])) // 9
console.log(evalRPN(['4', '13', '5', '/', '+'])) // 6

题目13：基本计算器 ​

答案：

javascript
function calculate(s) {
  const stack = []
  let result = 0
  let num = 0
  let sign = 1

  for (let i = 0; i < s.length; i++) {
    const char = s[i]

    if (char >= '0' && char <= '9') {
      num = num * 10 + parseInt(char)
    } else if (char === '+') {
      result += sign * num
      num = 0
      sign = 1
    } else if (char === '-') {
      result += sign * num
      num = 0
      sign = -1
    } else if (char === '(') {
      stack.push(result)
      stack.push(sign)
      result = 0
      sign = 1
    } else if (char === ')') {
      result += sign * num
      num = 0
      result *= stack.pop() // sign
      result += stack.pop() // result
    }
  }

  return result + sign * num
}

console.log(calculate('1 + 1')) // 2
console.log(calculate(' 2-1 + 2 ')) // 3
console.log(calculate('(1+(4+5+2)-3)')) // 9

题目14：字符串解码 ​

答案：

javascript
function decodeString(s) {
  const countStack = []
  const stringStack = []
  let currentString = ''
  let currentNum = 0

  for (const char of s) {
    if (char >= '0' && char <= '9') {
      currentNum = currentNum * 10 + parseInt(char)
    } else if (char === '[') {
      countStack.push(currentNum)
      stringStack.push(currentString)
      currentNum = 0
      currentString = ''
    } else if (char === ']') {
      const count = countStack.pop()
      const prevString = stringStack.pop()
      currentString = prevString + currentString.repeat(count)
    } else {
      currentString += char
    }
  }

  return currentString
}

console.log(decodeString('3[a]2[bc]')) // 'aaabcbc'
console.log(decodeString('3[a2[c]]')) // 'accaccacc'
console.log(decodeString('2[abc]3[cd]ef')) // 'abcabccdcdcdef'

题目15：验证栈序列 ​

答案：

javascript
function validateStackSequences(pushed, popped) {
  const stack = []
  let popIndex = 0

  for (const num of pushed) {
    stack.push(num)
    while (stack.length > 0 && stack[stack.length - 1] === popped[popIndex]) {
      stack.pop()
      popIndex++
    }
  }

  return stack.length === 0
}

console.log(validateStackSequences([1, 2, 3, 4, 5], [4, 5, 3, 2, 1])) // true
console.log(validateStackSequences([1, 2, 3, 4, 5], [4, 3, 5, 1, 2])) // false

题目16：删除字符串中的所有相邻重复项 ​

答案：

javascript
function removeDuplicates(s) {
  const stack = []

  for (const char of s) {
    if (stack.length > 0 && stack[stack.length - 1] === char) {
      stack.pop()
    } else {
      stack.push(char)
    }
  }

  return stack.join('')
}

console.log(removeDuplicates('abbaca')) // 'ca'
console.log(removeDuplicates('azxxzy')) // 'ay'

题目17：比较含退格的字符串 ​

答案：

javascript
function backspaceCompare(s, t) {
  function buildString(str) {
    const stack = []
    for (const char of str) {
      if (char === '#') {
        stack.pop()
      } else {
        stack.push(char)
      }
    }
    return stack.join('')
  }

  return buildString(s) === buildString(t)
}

console.log(backspaceCompare('ab#c', 'ad#c')) // true
console.log(backspaceCompare('ab##', 'c#d#')) // true
console.log(backspaceCompare('a##c', '#a#c')) // true
console.log(backspaceCompare('a#c', 'b')) // false

题目18：棒球比赛 ​

答案：

javascript
function calPoints(ops) {
  const stack = []

  for (const op of ops) {
    if (op === '+') {
      const a = stack[stack.length - 1]
      const b = stack[stack.length - 2]
      stack.push(a + b)
    } else if (op === 'D') {
      stack.push(stack[stack.length - 1] * 2)
    } else if (op === 'C') {
      stack.pop()
    } else {
      stack.push(parseInt(op))
    }
  }

  return stack.reduce((sum, num) => sum + num, 0)
}

console.log(calPoints(['5', '2', 'C', 'D', '+'])) // 30
console.log(calPoints(['5', '-2', '4', 'C', 'D', '9', '+', '+'])) // 27

题目19：设计一个支持增量操作的栈 ​

答案：

javascript
class CustomStack {
  constructor(maxSize) {
    this.stack = []
    this.maxSize = maxSize
    this.inc = [] // 增量数组
  }

  push(x) {
    if (this.stack.length < this.maxSize) {
      this.stack.push(x)
      this.inc.push(0)
    }
  }

  pop() {
    if (this.stack.length === 0) return -1
    const i = this.stack.length - 1
    const res = this.stack.pop() + this.inc[i]
    if (i > 0) {
      this.inc[i - 1] += this.inc[i]
    }
    this.inc.pop()
    return res
  }

  increment(k, val) {
    const i = Math.min(k, this.stack.length) - 1
    if (i >= 0) {
      this.inc[i] += val
    }
  }
}

const stk = new CustomStack(3)
stk.push(1)
stk.push(2)
console.log(stk.pop()) // 2
stk.push(2)
stk.push(3)
stk.push(4)
stk.increment(5, 100)
stk.increment(2, 100)
console.log(stk.pop()) // 103
console.log(stk.pop()) // 202
console.log(stk.pop()) // 201
console.log(stk.pop()) // -1

题目20：股票价格跨度 ​

答案：

javascript
class StockSpanner {
  constructor() {
    this.stack = [] // [price, span]
  }

  next(price) {
    let span = 1

    while (
      this.stack.length > 0 &&
      this.stack[this.stack.length - 1][0] <= price
    ) {
      span += this.stack.pop()[1]
    }

    this.stack.push([price, span])
    return span
  }
}

const spanner = new StockSpanner()
console.log(spanner.next(100)) // 1
console.log(spanner.next(80)) // 1
console.log(spanner.next(60)) // 1
console.log(spanner.next(70)) // 2
console.log(spanner.next(60)) // 1
console.log(spanner.next(75)) // 4
console.log(spanner.next(85)) // 6

五、总结 ​

栈的核心要点 ​

  1. LIFO 原则：后进先出是栈的本质
  2. 时间复杂度：核心操作 push、pop、peek 都是 O(1)
  3. 空间复杂度：O(n)，n 为元素个数
  4. 单调栈：解决"下一个更大/更小元素"类问题
  5. 调用栈：理解 JavaScript 函数执行机制的关键

常见题型 ​

类型典型题目
基础实现最小栈、两个栈实现队列
括号匹配有效括号、最长有效括号
单调栈每日温度、下一个更大元素
表达式计算逆波兰表达式、基本计算器
字符串处理简化路径、字符串解码
设计类股票价格跨度、增量栈

解题技巧 ​

  1. 遇到匹配问题：考虑用栈
  2. 需要知道"下一个"：考虑单调栈
  3. 涉及嵌套结构：栈天然适合
  4. 需要撤销/回退：栈可以保存历史状态

基于 VitePress 的本地知识库

Copyright © 2026