队列实现 | SkyBlog

动态大小：链表允许队列在运行时动态增长或缩小，而无需预先指定固定大小。这使得队列更加灵活，能够适应不同场景下的变化。
插入和删除效率高：在链表中插入和删除元素的效率很高，只需修改指针即可，不需要像数组那样搬移大量元素。这使得队列的入队（enqueue）和出队（dequeue）操作在链表实现中更为高效。

class ListNode<T> {
  val: T | null
  prev: ListNode<T> | null
  next: ListNode<T> | null

  constructor(val?: T, prev?: ListNode<T>, next?: ListNode<T>) {
    this.val = val || null
    this.prev = prev || null
    this.next = next || null
  }
}

class Queue<T> {
  private head: ListNode<T> | null = null
  private tail: ListNode<T> | null = null
  private len = 0

  enqueue(item: T) {
    const node = new ListNode(item)
    if (this.head == null || this.tail == null) {
      this.head = this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }
    this.len++
  }

  dequeue() {
    if (this.head == null) return null
    const val = this.head.val
    this.head = this.head.next
    if (this.head != null) this.head.prev = null
    this.len--
    return val
  }

  isEmpty() {
    return this.head == null
  }

  size() {
    return this.len
  }

  front() {
    if (this.head == null) return null
    return this.head.val
  }

  clear() {
    this.head = null
    this.tail = null
    this.len = 0
  }
}