Stack

栈（LIFO）数据结构，后进先出。

函数签名

function createStack<T>(): Stack<T>

interface Stack<T> {
  push(item: T): void
  pop(): T | undefined
  peek(): T | undefined
  size(): number
  isEmpty(): boolean
  clear(): void
  toArray(): T[]
}

API 说明

push(item: T): void

在栈顶添加元素。

参数：

• item: 要添加的元素

时间复杂度：O(1)

pop(): T | undefined

移除并返回栈顶的元素。

返回值：

• 栈顶的元素，如果栈为空则返回 undefined

时间复杂度：O(1)

peek(): T | undefined

查看栈顶的元素，但不移除。

返回值：

• 栈顶的元素，如果栈为空则返回 undefined

时间复杂度：O(1)

size(): number

获取栈中元素的数量。

返回值：

• 栈中元素的数量

时间复杂度：O(1)

isEmpty(): boolean

检查栈是否为空。

返回值：

• 如果栈为空则返回 true，否则返回 false

时间复杂度：O(1)

clear(): void

清空栈中的所有元素。

时间复杂度：O(1)

toArray(): T[]

返回栈中所有元素的数组副本（栈顶在前）。

返回值：

• 包含所有元素的数组（逆序）

时间复杂度：O(n)

使用示例

import { createStack } from '@shared/functions/data-structures/Stack'

// 创建栈
const stack = createStack<string>()

// 入栈操作
stack.push('命令1')
stack.push('命令2')
stack.push('命令3')

// 查看栈顶
console.log(stack.peek())  // '命令3'

// 出栈操作
console.log(stack.pop())  // '命令3'
console.log(stack.pop())  // '命令2'

// 获取栈大小
console.log(stack.size())  // 1

// 检查是否为空
console.log(stack.isEmpty())  // false

// 转换为数组（栈顶在前）
console.log(stack.toArray())  // ['命令1']

// 清空栈
stack.clear()
console.log(stack.isEmpty())  // true

工作原理

栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子：

• 新元素总是添加到栈顶（push）
• 移除操作总是从栈顶开始（pop）
• 后加入的元素先被移除

本实现使用数组作为底层数据结构：

• push 使用数组的 push 方法 - O(1)
• pop 使用数组的 pop 方法 - O(1)
• peek 访问数组最后一个元素 - O(1)

应用场景

1. 函数调用栈：程序执行时管理函数调用
2. 撤销/重做功能：编辑器的操作历史
3. 表达式求值：计算器中的中缀表达式转后缀
4. 括号匹配：检查括号是否配对
5. 深度优先搜索（DFS）：图的遍历算法
6. 浏览器历史记录：后退功能

经典算法

括号匹配

function isValidParentheses(s: string): boolean {
  const stack = createStack<string>()
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
  
  for (const char of s) {
    if (['(', '[', '{'].includes(char)) {
      stack.push(char)
    } else if (char in pairs) {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false
      }
    }
  }
  
  return stack.isEmpty()
}

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

后缀表达式求值

function evalRPN(tokens: string[]): number {
  const stack = createStack<number>()
  
  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const b = stack.pop()!
      const a = stack.pop()!
      
      switch (token) {
        case '+': stack.push(a + b); break
        case '-': stack.push(a - b); break
        case '*': stack.push(a * b); break
        case '/': stack.push(Math.trunc(a / b)); break
      }
    } else {
      stack.push(Number(token))
    }
  }
  
  return stack.pop()!
}

console.log(evalRPN(['2', '1', '+', '3', '*']))  // 9 = (2 + 1) * 3