JavaScript 队列

摘要: 本教程将介绍队列数据结构以及如何实现 JavaScript 队列。

队列数据结构简介

队列是一个元素的有序列表，其中元素插入到队列的末尾，并从队列的开头删除。

队列的工作原理基于先进先出 (FIFO) 原则，这与 堆栈 不同，堆栈基于后进先出 (LIFO) 原则。

队列有两个主要操作

• 在队列的末尾插入一个新元素，称为入队。
• 从队列的开头删除一个元素，称为出队。

下图说明了队列

队列的另一个重要操作是获取称为“窥视”的开头元素。与出队操作不同，窥视操作返回开头元素而不修改队列。

队列这个名字来自银行客户队列的类比。先来的顾客先被服务，后来来的顾客排在队列的末尾，稍后会被服务。

使用对象实现 JavaScript 队列

以下显示了如何使用对象实现队列数据结构

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}Code language: JavaScript (javascript)

工作原理。

首先，初始化存储队列元素的对象 (elements) 以及两个用于在构造函数中跟踪头部和尾部的变量

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  //...
}Code language: JavaScript (javascript)

其次，通过将元素添加到队列末尾的元素对象中来入队元素

class Queue {
  //...
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }

  //...
}Code language: JavaScript (javascript)

第三，从队列的开头删除元素

class Queue {

  // ...
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }

  //...
}Code language: JavaScript (javascript)

第四，定义访问队列开头元素的 peek() 方法

class Queue {
  //...
  peek() {
    return this.elements[this.head];
  }
  //...  
}Code language: JavaScript (javascript)

第五，获取队列的长度

class Queue {
  //...
  get length() {
    return this.tail - this.head;
  }
  //...
}Code language: JavaScript (javascript)

当长度为零时，队列为空。

最后，定义 isEmpty() 方法，如果队列为空，则返回 true

class Queue {
  // ...
  get isEmpty() {
    return this.tail - this.head;
  }
  // ... 
}Code language: JavaScript (javascript)

要从 Queue() 构造函数创建新队列，请使用以下新关键字

let q = new Queue();Code language: JavaScript (javascript)

要入队从 1 到 7 的数字，请使用以下代码。

for (let i = 1; i <= 7; i++) {
    q.enqueue(i);
}Code language: JavaScript (javascript)

要获取队列开头的数字，请使用 peek() 方法。

console.log(q.peek()); // 1Code language: JavaScript (javascript)

要获取队列的当前长度，请使用以下示例中的 length() 方法。

console.log(q.length); // 7Code language: JavaScript (javascript)

要删除队列开头元素，请使用以下 dequeue() 方法

// dequeue all elements
while (!q.isEmpty()) {
    console.log(q.dequeue());
}Code language: JavaScript (javascript)

将所有内容整合在一起

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

let q = new Queue();
for (let i = 1; i <= 7; i++) {
  q.enqueue(i);
}
// get the current item at the front of the queue
console.log(q.peek()); // 1

// get the current length of queue
console.log(q.length); // 7

// dequeue all elements
while (!q.isEmpty) {
  console.log(q.dequeue());
}Code language: JavaScript (javascript)

总结

• 队列是一种基于 FIFO 原则工作的数位结构。