当前位置：首页 > JavaScript

js队列实现

2026-03-14 05:11:36JavaScript

队列的基本概念

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

基于数组的实现

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

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

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

  dequeue() {
    if (this.isEmpty()) return "Underflow";
    return this.items.shift();
  }

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

基于链表的实现

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

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

class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 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.size++;
  }

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

循环队列实现

解决数组实现中空间浪费问题：

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 false;
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.capacity;
    }
    return true;
  }
}

优先队列实现

元素按优先级出队：

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