队列的实现

为什么不能直接用数组当队列？

• 数组删除元素: 时间复杂度 O(n), 删除队首后所有元素都要前移;
• 目标: 让入队与出队都保持 O(1);
• 手段: 用链表挂接节点, 或用环形数组记录下标;

如何用链表实现队列？

• 结构: 双向链表 + front/rear 指针;
• 入队: 在链表的一端插入新节点, 并把它记为 rear;
• 出队: 删除 front 节点, 再把 front 移到它的另一侧前驱;
• 边界: 出队后队列为空时, front 和 rear 同时置空;

class QueueWithLinkedList<T> {
  list: DoublyLinkedList<T>;
  front: DoublyLinkedListNode<T> | null = null;
  rear: DoublyLinkedListNode<T> | null = null;

  isEmpty() {
    return this.list.isEmpty();
  }

  enQueue(node: DoublyLinkedListNode<T>) {
    if (this.isEmpty()) this.front = node;
    this.list.insert(node, this.list.head); // 新节点插入链表头部一侧, 该侧作为队尾
    this.rear = node;
  }

  deQueue() {
    if (this.isEmpty()) throw new Error("empty");
    const front = this.front as DoublyLinkedListNode<T>;
    this.list.delete(front);
    this.front = front.before as DoublyLinkedListNode<T>; // 队首向另一侧移动
    if (this.isEmpty()) {
      this.front = null;
      this.rear = null;
    }
  }
}

如何用环形数组实现队列？

• 思路: 用 front 和 rear 记录队首队尾下标;
• 环形: front 或 rear 越过数组末尾时回到数组头部;
• 状态: capacity 容量与 size 当前元素数;
• 入队: 写入 array[rear], 再把 rear 前进一格取模;
• 出队: 清空 array[front], 再把 front 前进一格取模;

class QueueArray {
  private _capacity: number;
  private _size: number;
  private _front: number;
  private _rear: number;
  private _array: unknown[];

  constructor(capacity: number) {
    this._capacity = capacity;
    this._size = 0;
    this._front = 0;
    this._rear = 0;
    this._array = new Array(capacity);
  }

  isEmpty() {
    return this._size === 0;
  }

  isFull() {
    return this._size === this._capacity;
  }

  enQueue(value: unknown) {
    if (this.isFull()) return false;
    this._array[this._rear] = value;
    this._size += 1;
    this._rear = (this._rear + 1) % this._capacity;
    return true;
  }

  deQueue() {
    if (this.isEmpty()) return false;
    this._array[this._front] = undefined;
    this._size -= 1;
    this._front = (this._front + 1) % this._capacity;
    return true;
  }
}

环形数组为什么需要额外的 size 字段？

• 直接判满的陷阱: front === rear 既可能是空队列, 也可能是满队列;
• 解法: 用 size 单独记录元素个数, 空与满分别用 size === 0 和 size === capacity 判断;