当前位置：首页 > JavaScript

js实现queue

2026-03-14 09:52:32JavaScript

实现队列的基本概念

队列是一种遵循先进先出（FIFO）原则的数据结构。在JavaScript中，队列可以通过数组或链表实现。数组实现简单直观，链表实现更适合频繁的插入和删除操作。

使用数组实现队列

数组提供push和shift方法，分别用于入队和出队操作。这种方式简单但性能较差，因为shift操作需要移动所有剩余元素。

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

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

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

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

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

  clear() {
    this.items = [];
  }
}

使用链表实现队列

链表实现避免了数组shift操作的低效问题。每个节点保存数据和指向下一个节点的引用。

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

class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(data) {
    const newNode = new Node(data);
    if (this.tail) {
      this.tail.next = newNode;
    }
    this.tail = newNode;
    if (!this.head) {
      this.head = newNode;
    }
    this.length++;
  }

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

  peek() {
    return this.head ? this.head.data : null;
  }

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

  size() {
    return this.length;
  }

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

性能优化版本

结合数组和指针可以避免频繁移动元素。使用两个指针分别标记队列的头部和尾部。

class OptimizedQueue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }

  enqueue(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }

  peek() {
    return this.items[this.frontIndex];
  }

  isEmpty() {
    return this.frontIndex === this.rearIndex;
  }

  size() {
    return this.rearIndex - this.frontIndex;
  }

  clear() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }
}