3. 栈（Stack）

3. 栈（Stack）

问题：需要「后进先出」的数据结构，如撤销操作、函数调用栈、括号匹配。

核心：只能从一端（栈顶）操作，Push 压入、Pop 弹出，后进先出（LIFO）。

特点

  • 只允许在栈顶操作
  • Push / Pop 均 O(1)
  • 不支持随机访问

优点

  • 操作简单高效，O(1) 入栈出栈
  • 天然适合递归/回溯场景
  • 实现简单（数组或链表均可）

缺点

  • 只能访问栈顶，中间元素不可达
  • 不适合需要随机访问的场景
  • 栈溢出风险（递归过深）
class Stack {
  #data = [];

  push(val) { this.#data.push(val); }
  pop()     { return this.#data.pop(); }
  peek()    { return this.#data.at(-1); }
  get size() { return this.#data.length; }
}

// 括号匹配
function isValid(s) {
  const stack = new Stack();
  const map = { ')': '(', ']': '[', '}': '{' };

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

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

// 基于切片的栈
type Stack[T any] struct {
    data []T
}

func (s *Stack[T]) Push(val T) {
    s.data = append(s.data, val)
}

func (s *Stack[T]) Pop() T {
    n := len(s.data) - 1
    val := s.data[n]
    s.data = s.data[:n]
    return val
}

func (s *Stack[T]) Peek() T {
    return s.data[len(s.data)-1]
}

func (s *Stack[T]) Size() int {
    return len(s.data)
}

// 括号匹配
func IsValid(s string) bool {
    var st Stack[rune]
    match := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, ch := range s {
        if ch == '(' || ch == '[' || ch == '{' {
            st.Push(ch)
        } else if st.Size() == 0 || st.Pop() != match[ch] {
            return false
        }
    }
    return st.Size() == 0
}

浏览器的「后退」、文本编辑器的「撤销」、函数调用栈、DFS 深度优先搜索都是栈的应用。