跳到主要内容位置

队列

定义

队列是一种先进先出(FIFO)的、线性的数据结构,与栈的结构类似,只是最先入队到队列的数据,会第一个出队,这与栈相反。 队列常见的应用场景是基于事件的处理系统,例如 JavaScript 事件循环机制、订单处理系统,邮件处理系统等,它们都是基于消息队列实现的。 队列常见的操作有:

  • 入队,把数据添加到队列中。
  • 出队,把数据从队列中取出。
  • 查看队首元素。
  • 查看队列的大小。
  • 判断队列是否为空。

JavaScript 实现

在 JavaScript 中,队列同样可以使用数组来实现,因为 JavaScript 的数组也支持队列模式,我们可以对它进行包装。

  1. 定义一个 Queue Class:
class Queue {}
  1. 在里边定义一个数组成员变量,保存队列内部的数据:
class Queue {
items = [];
}
  1. 接下来看一下队列的每个操作的实现方式,equeue() 把一个元素添加到队尾,它:
    • 接收一个要添加的元素作为参数。
    • 调用数组的 push() 方法,把新元素 item 添加到内部的 items 数组的尾部。
enqueue(item) {
this.items.push(item);
}
  1. dequeue() 方法会把队首元素出队并返回,在里边先判断当前队列是否为空,如果为空,返回“队列为空”,如果不为空,调用数组的 shift() 出队数组的第一个元素:
dequeue() {
if (this.isEmpty()) {
return "队列为空";
}
return this.items.shift();
}
  1. isEmpty() 方法判断了队列是否为空,这里调用了 size(),如果返回 0,则队列为空:
isEmpty() {
return this.size() === 0;
}
  1. size() 方法返回队列的大小,这里返回 items 数组的 length 属性:
size() {
return this.items.length;
}
  1. front() 方法返回队首元素,但并不从队列中出队,这里直接返回 items 数组的第 1 个元素:
front() {
if (this.isEmpty()) {
return "队列为空";
}
return this.items[0];
}

运行示例

我们使用 Queue 类,来编写一些队列的操作示例:

  1. 初始化一个 Queue 对象。
  2. 使用 enqueue() 添加元素 1, 2, 3 到队列中。
  3. 调用 size() 查看队列的大小,此时为 3。
  4. 调用 front() 查看队首元素,此时为 1,注意 front() 不会把元素从队列中出队。
  5. 调用 dequeue() 出队一个队首元素,1。
  6. 再调用 size() 查看队列的大小,此时为 2。
  7. 再查看队首元素,此时是 2。
  8. 我们再调用 3 次 dequeue() 出队操作,在第 3 次调用时,队列已经为空了,会返回队列为空。
const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log("队列大小:" + queue.size());
console.log("查看队首元素:" + queue.front());

const ele = queue.dequeue();
console.log("出队元素:" + ele);

console.log("队列大小:" + queue.size());
console.log("查看队首元素:" + queue.front());

console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());

执行结果是:

队列大小:3
查看队首元素:1
出队元素:1
队列大小:2
查看队首元素:2
2
3
队列为空

小结

好了,这个就是队列数据结构的定义、操作和 JavaScript 实现,你学会了吗?如果有帮助请三连,想学更多有用的前端开发知识,请关注峰华前端工程师,感谢观看!