栈的实现与对比

如何用数组实现栈？

• 状态: 固定容量 _array + 栈顶下标 _index (空栈为 -1);
• push: 满则失败, 否则 _index 加一后写入;
• pop: 空则返回 null, 否则取出后把该位置置 undefined 再 _index 减一;
• 时间: 三个操作都是 $O(1)$;

class StackWithArray<T> {
  private array: T[];
  private index = -1;

  constructor(private size: number) {
    this.array = new Array(size);
  }

  isEmpty() {
    return this.index === -1;
  }

  isFull() {
    return this.index === this.size - 1;
  }

  push(value: T) {
    if (this.isFull()) return false;
    this.array[++this.index] = value;
    return true;
  }

  pop() {
    if (this.isEmpty()) return null;
    const value = this.array[this.index];
    this.array[this.index--] = undefined as T;
    return value;
  }

  peek() {
    return this.isEmpty() ? null : this.array[this.index];
  }
}

如何用链表实现栈？

• 选择: 栈顶放在链表头部, 使入栈/出栈都落在 $O(1)$ 的头部插入删除上;
• 依据: 双向链表已提供头哨兵与 insert/delete, 见 链表操作与双向链表实现;

class StackWithLinkedList<T> {
  private list = new DoublyLinkedList<T>();

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

  push(value: DoublyLinkedListNode<T>) {
    this.list.insert(value, this.list.head);
    return true;
  }

  pop() {
    if (this.isEmpty()) return null;
    const top = this.list.head.next as DoublyLinkedListNode<T>;
    this.list.delete(top);
    return top.value;
  }

  peek() {
    return this.isEmpty() ? null : (this.list.head.next?.value ?? null);
  }
}

两种实现如何取舍？

维度	数组实现	链表实现
时间	分摊效率高, 但扩容时单次退化	每次操作稳定, 常数较大
空间	连续内存, 固定容量, 可能预留浪费	每元素多一个引用, 按需分配
适用	容量可预估, 追求吞吐	容量波动大, 追求稳定延迟