当前位置：首页 > JavaScript

js 队列实现

2026-04-04 01:34:25JavaScript

队列的基本概念

队列是一种遵循先进先出（FIFO）原则的线性数据结构。元素的插入操作在队列的尾部进行，删除操作在队列的头部进行。

js 队列实现

数组实现队列

使用数组实现队列时，可以通过维护头部和尾部指针来模拟队列的行为。

js 队列实现

class Queue {
  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 removedItem = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return removedItem;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    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;
  }
}

链表实现队列

链表实现队列可以避免数组实现的性能问题，尤其是在频繁的插入和删除操作中。

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

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

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

  dequeue() {
    if (this.isEmpty()) return undefined;
    const removedNode = this.front;
    this.front = this.front.next;
    if (this.front === null) this.rear = null;
    this.size--;
    return removedNode.value;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.front.value;
  }

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

  getSize() {
    return this.size;
  }

  clear() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
}

循环队列实现

循环队列是一种优化后的队列实现方式，可以有效利用数组空间。

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = -1;
    this.rear = -1;
  }

  enqueue(element) {
    if (this.isFull()) return false;
    if (this.isEmpty()) this.front = 0;
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = element;
    return true;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const removedItem = this.items[this.front];
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.capacity;
    }
    return removedItem;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.front];
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return (this.rear + 1) % this.capacity === this.front;
  }

  size() {
    if (this.isEmpty()) return 0;
    return (this.rear - this.front + this.capacity) % this.capacity + 1;
  }
}