js实现队列的三种方法

数组实现队列

使用数组的 push 和 shift 方法模拟队列的先进先出特性。

class ArrayQueue {
  constructor() {
    this.items = [];
  }
  enqueue(element) {
    this.items.push(element);
  }
  dequeue() {
    return this.items.shift();
  }
  peek() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
}

缺点：shift() 操作的时间复杂度为 O(n)，频繁出队时性能较差。

链表实现队列

通过链表节点实现高效的头尾操作，避免数组的频繁位移。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  enqueue(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }
  dequeue() {
    if (!this.head) return null;
    const value = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) this.tail = null;
    return value;
  }
  peek() {
    return this.head?.value;
  }
  isEmpty() {
    return this.length === 0;
  }
}

优点：enqueue 和 dequeue 的时间复杂度均为 O(1)。

双栈实现队列

利用两个栈模拟队列行为，通过反转栈顺序实现先进先出。

class StackQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  enqueue(element) {
    this.inStack.push(element);
  }
  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
  peek() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack[this.outStack.length - 1];
  }
  isEmpty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

特点：摊还时间复杂度为 O(1)，适合需要兼顾入队和出队性能的场景。