当前位置：首页 > JavaScript

js队列实现

2026-02-01 06:45:01JavaScript

队列的基本概念

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

基于数组的实现

利用数组的push和shift方法模拟队列操作：

js队列实现

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

  // 入队
  enqueue(element) {
    this.items.push(element);
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  // 查看队头
  peek() {
    return this.items[0];
  }

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

  // 清空队列
  clear() {
    this.items = [];
  }

  // 获取队列长度
  size() {
    return this.items.length;
  }
}

基于链表的实现

通过维护头尾指针实现高效操作：

js队列实现

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 removedValue = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (!this.head) this.tail = null;
    return removedValue;
  }

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

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

  size() {
    return this.length;
  }
}

循环队列实现

解决数组实现中出队时元素移动的性能问题：

class CircularQueue {
  constructor(k) {
    this.size = k;
    this.queue = new Array(k);
    this.head = -1;
    this.tail = -1;
  }

  enQueue(value) {
    if (this.isFull()) return false;
    if (this.isEmpty()) this.head = 0;
    this.tail = (this.tail + 1) % this.size;
    this.queue[this.tail] = value;
    return true;
  }

  deQueue() {
    if (this.isEmpty()) return false;
    if (this.head === this.tail) {
      this.head = -1;
      this.tail = -1;
    } else {
      this.head = (this.head + 1) % this.size;
    }
    return true;
  }

  Front() {
    return this.isEmpty() ? -1 : this.queue[this.head];
  }

  Rear() {
    return this.isEmpty() ? -1 : this.queue[this.tail];
  }

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

  isFull() {
    return (this.tail + 1) % this.size === this.head;
  }
}

优先级队列实现

元素按优先级出队，可通过最小堆实现：

class PriorityQueue {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

  enqueue(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  dequeue() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown();
    }
    return min;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parentIdx]) >= 0) break;
      [this.heap[index], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[index]];
      index = parentIdx;
    }
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      const leftChildIdx = 2 * index + 1;
      const rightChildIdx = 2 * index + 2;
      let swapIdx = null;

      if (leftChildIdx < length && this.comparator(this.heap[leftChildIdx], this.heap[index]) < 0) {
        swapIdx = leftChildIdx;
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.comparator(this.heap[rightChildIdx], this.heap[index]) < 0) ||
          (swapIdx !== null && this.comparator(this.heap[rightChildIdx], this.heap[leftChildIdx]) < 0)
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }

  peek() {
    return this.heap[0];
  }

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