当前位置：首页 > JavaScript

js 实现队列

2026-04-07 02:50:04JavaScript

队列的基本概念

队列是一种先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队。JavaScript中可以通过数组或链表实现队列。

使用数组实现队列

数组的push和shift方法天然适合队列操作，但频繁的shift操作会导致性能问题（因为需要移动所有剩余元素）。

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

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

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items.shift();
  }

  peek() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

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

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

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

使用链表实现队列

链表实现的队列在频繁操作时性能更优，因为不需要移动元素。

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 "Queue is empty";
    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 "Queue is empty";
    return this.front.value;
  }

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

  getSize() {
    return this.size;
  }

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

使用两个栈实现队列

这种方法利用栈的后进先出特性模拟队列的先进先出。

js 实现队列

class StackQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

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

  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }

  peek() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack[this.outStack.length - 1];
  }

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

  size() {
    return this.inStack.length + this.outStack.length;
  }
}