当前位置：首页 > JavaScript

js实现队列

2026-02-02 05:47:57JavaScript

队列的基本概念

队列是一种遵循先进先出（FIFO）原则的线性数据结构。元素从队尾入队，从队头出队，操作包括enqueue（入队）、dequeue（出队）、peek（查看队头元素）和isEmpty（判断是否为空）。

使用数组实现队列

数组实现简单直观，但出队操作（shift）的时间复杂度为O(n)，因为需要移动剩余元素。

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

使用链表实现队列

链表实现避免了数组出队的性能问题，所有操作均为O(1)时间复杂度。

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.isEmpty()) {
      this.front = newNode;
    } else {
      this.rear.next = newNode;
    }
    this.rear = newNode;
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    const removedValue = this.front.value;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    this.size--;
    return removedValue;
  }

  peek() {
    if (this.isEmpty()) return "Queue is empty";
    return this.front.value;
  }

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

使用两个栈实现队列

通过维护输入栈和输出栈，模拟队列行为。摊还时间复杂度为O(1)。

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

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

  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop() || "Queue is empty";
  }

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

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

循环队列实现

固定大小的循环队列能有效利用空间，通过模运算实现环形结构。

js实现队列

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