当前位置：首页 > JavaScript

队列的实现js

2026-02-03 03:09:39JavaScript

队列的基本概念

队列是一种先进先出（FIFO）的数据结构，支持在队尾插入元素（入队）和在队头删除元素（出队）。JavaScript中可通过数组或链表实现队列。

基于数组的实现

数组的push和shift方法天然适合队列操作，但shift的时间复杂度为O(n)，可能影响性能。

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;
  }
}

基于链表的实现

链表实现可保证入队和出队操作均为O(1)时间复杂度，适合高频操作场景。

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

class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.front) {
      this.front = newNode;
    } else {
      this.rear.next = newNode;
    }
    this.rear = newNode;
    this.length++;
  }

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

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

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

  size() {
    return this.length;
  }
}

循环队列优化

针对数组实现的出队性能问题，可通过循环队列减少元素移动：

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }

  enqueue(element) {
    if (this.isFull()) return false;
    this.items[this.tail] = element;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
    return true;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const element = this.items[this.head];
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return element;
  }

  isFull() {
    return this.size === this.capacity;
  }

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

实际应用示例

浏览器任务队列、消息队列等场景常使用队列结构。以下是优先队列的实现变种：

队列的实现js

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

  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    if (!added) this.items.push(queueElement);
  }
}