当前位置：首页 > JavaScript

js 实现队列

2026-02-02 09:24:04JavaScript

队列的基本概念

队列是一种先进先出（FIFO）的数据结构，支持从尾部插入元素（入队）和从头部移除元素（出队）。以下是 JavaScript 中实现队列的几种方法。

使用数组实现队列

数组的 push 和 shift 方法可以分别实现入队和出队操作：

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  peek() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

  size() {
    return this.items.length;
  }
}

// 使用示例
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 输出 1
console.log(queue.peek());    // 输出 2

使用链表实现队列

链表实现可以避免数组 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 newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

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

  peek() {
    return this.head?.value;
  }

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

// 使用示例
const llQueue = new LinkedListQueue();
llQueue.enqueue(10);
llQueue.enqueue(20);
console.log(llQueue.dequeue()); // 输出 10

使用两个栈实现队列

通过两个栈模拟队列的 FIFO 特性，入队和出队的平均时间复杂度为 O(1)：

js 实现队列

class StackQueue {
  constructor() {
    this.stack1 = []; // 用于入队
    this.stack2 = []; // 用于出队
  }

  enqueue(element) {
    this.stack1.push(element);
  }

  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop() || "Queue is empty";
  }

  peek() {
    if (this.stack2.length > 0) {
      return this.stack2[this.stack2.length - 1];
    }
    return this.stack1[0] || "Queue is empty";
  }

  isEmpty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }
}

// 使用示例
const sq = new StackQueue();
sq.enqueue(100);
sq.enqueue(200);
console.log(sq.dequeue()); // 输出 100