js实现队列的三种方法

使用数组实现队列

数组是最直观的队列实现方式，利用push和shift方法分别模拟入队和出队操作。

const queue = [];
queue.push(1); // 入队
queue.push(2);
const item = queue.shift(); // 出队，返回1

缺点：shift操作的时间复杂度为O(n)，因为需要移动剩余元素。

使用链表实现队列

链表结构天然适合队列操作，通过维护头尾指针实现O(1)时间复杂度的入队和出队。

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(value) {
    const node = new Node(value);
    if (!this.head) this.head = node;
    else this.tail.next = node;
    this.tail = node;
    this.size++;
  }

  dequeue() {
    if (!this.head) return null;
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }
}

使用两个栈实现队列

通过维护输入栈和输出栈，将栈的LIFO特性转换为队列的FIFO特性。

class StackQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  enqueue(value) {
    this.inStack.push(value);
  }

  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}

特点：摊还时间复杂度为O(1)，适合需要兼顾栈和队列操作的场景。