javascript如何实现队列功能-js教程-PHP中文网

javascript如何实现队列功能

星降

发布： 2025-08-12 13:45:02

原创

415人浏览过

javascript中实现队列有多种方式，最常见的是使用数组，1. 基于数组的队列通过push和shift方法实现，优点是简单易懂，push为o(1)，但shift为o(n)，性能随队列增大而下降；2. 链表实现通过节点连接，enqueue和dequeue均为o(1)，性能优越，但实现复杂且占用更多内存；3. 环形数组使用固定大小数组和head、tail指针，操作均为o(1)，空间利用率高，但大小固定不可扩展；选择方式应根据队列大小是否确定及性能需求决定，若对性能要求不高可选数组实现，若要求高性能且大小不确定应选链表，若大小固定则选环形数组，每种方式均有适用场景，需结合实际需求权衡选择。

javascript如何实现队列功能

JavaScript实现队列，本质上就是利用数组的特性，模拟队列“先进先出”的行为。数组的

push

登录后复制

和

shift

登录后复制

方法，或者

unshift

登录后复制

和

pop

登录后复制

方法，都能实现队列的基本操作。选择哪一组，取决于你对性能和代码可读性的偏好。

解决方案：

JavaScript中实现队列有多种方式，最常见的是使用数组。以下是一些实现队列的示例，以及对它们的优缺点的讨论。

立即学习“Java免费学习笔记（深入）”；

基于数组的队列实现

这是最直接的实现方式。

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

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

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow"; // 或者抛出异常
    }
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) {
      return "No elements in Queue";
    }
    return this.items[0];
  }

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

  printQueue() {
    let str = "";
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str;
  }
}

// 示例
let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.printQueue()); // 输出：10 20 30
console.log(queue.dequeue());   // 输出：10
console.log(queue.front());     // 输出：20

登录后复制

优点：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

实现简单，易于理解。
```
push
```
登录后复制
操作是O(1)的复杂度。

缺点：

```
shift
```
登录后复制
操作是O(n)的复杂度，因为需要移动数组中的所有元素。当队列很大时，这会影响性能。

使用链表实现队列

为了避免

shift

登录后复制

操作的性能问题，可以使用链表来实现队列。

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(data) {
    let newNode = new Node(data);

    if (this.rear == null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

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

    let temp = this.front;
    this.front = this.front.next;

    if (this.front == null) {
      this.rear = null; // 队列为空时，rear也要置为null
    }

    return temp.data;
  }

  frontElement() {
    if (this.isEmpty()) {
      return "No elements in Queue";
    }
    return this.front.data;
  }

  isEmpty() {
    return this.front == null;
  }
}

// 示例
let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue());   // 输出：10
console.log(queue.frontElement()); // 输出：20

登录后复制

优点：

```
enqueue
```
登录后复制
和
```
dequeue
```
登录后复制
操作都是O(1)的复杂度。

缺点：

实现相对复杂，需要定义节点类。
需要额外的内存来存储节点之间的指针。

环形数组实现队列

环形数组是一种更高级的队列实现方式，它利用固定大小的数组和两个指针（head和tail）来模拟队列。

class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = new Array(capacity);
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      return "Overflow";
    }
    this.items[this.tail] = element;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    const item = this.items[this.head];
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return item;
  }

  front() {
    if (this.isEmpty()) {
      return "No elements in Queue";
    }
    return this.items[this.head];
  }

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

  isFull() {
    return this.size == this.capacity;
  }

  printQueue() {
    let str = "";
    let i = this.head;
    for (let j = 0; j < this.size; j++) {
      str += this.items[i] + " ";
      i = (i + 1) % this.capacity;
    }
    return str;
  }
}

// 示例
let queue = new CircularQueue(3);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.printQueue()); // 输出：10 20 30
console.log(queue.dequeue());   // 输出：10
console.log(queue.front());     // 输出：20

登录后复制

优点：

```
enqueue
```
登录后复制
和
```
dequeue
```
登录后复制
操作都是O(1)的复杂度。
可以有效地利用数组空间。

缺点：

实现相对复杂，需要维护head和tail指针。
队列的大小是固定的，不能动态扩展。

如何选择合适的队列实现方式？

选择哪种实现方式取决于你的具体需求。

如果队列的大小不确定，并且对性能要求不高，那么基于数组的队列实现是最简单的选择。
如果队列的大小不确定，并且对性能要求很高，那么使用链表实现队列是更好的选择。
如果队列的大小是固定的，并且对性能要求很高，那么使用环形数组实现队列是最好的选择。

如何优化基于数组的队列实现？

虽然

shift

登录后复制

操作是O(n)的复杂度，但我们可以通过一些技巧来优化基于数组的队列实现。

预分配足够的数组空间： 避免频繁地重新分配数组空间。
使用双端队列（Deque）： 双端队列允许在队列的两端进行插入和删除操作。可以使用
```
unshift
```
登录后复制
和
```
pop
```
登录后复制
方法来实现队列。虽然
```
unshift
```
登录后复制
操作也是O(n)的复杂度，但在某些情况下，它可以比
```
shift
```
登录后复制
操作更高效。