认识队列
队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)
受限之处:
- 只允许在表的前端(front)进行删除操作。
- 只允许在表的后端(rear)进行插入操作。
生活中类似队列结构的场景:
- 排队,比如在电影院,商场,甚至是厕所排队。
- 优先排队的人,优先处理。 (买票、结账、WC)。
队列图解
队列在程序中的应用
- 打印队列:计算机打印多个文件的时候,需要排队打印。
- 线程队列:当开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待 CPU 处理。
队列的实现
队列的实现和栈一样,有两种方案:
队列常见的操作
enqueue(element)
向队列尾部添加一个(或多个)新的项。dequeue()
移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。front()
返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与 Map 类的 peek 方法非常类似)。isEmpty()
如果队列中不包含任何元素,返回 true,否则返回 false。size()
返回队列包含的元素个数,与数组的 length 属性类似。toString()
将队列中的内容,转成字符串形式。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| class Queue { constructor() { this.items = []; }
enqueue(item) { this.items.push(item); }
dequeue() { return this.items.shift(); }
front() { return this.items[0]; }
isEmpty() { return this.items.length === 0; }
size() { return this.items.length; }
toString() { let result = ""; for (let item of this.items) { result += item + " "; } return result; } }
|
测试代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| const queue = new Queue();
queue.enqueue("a"); queue.enqueue("b"); queue.enqueue("c"); queue.enqueue("d"); console.log(queue.items);
queue.dequeue(); queue.dequeue(); console.log(queue.items);
console.log(queue.front());
console.log(queue.isEmpty());
console.log(queue.size());
console.log(queue.toString());
|
队列的应用
使用队列实现小游戏:击鼓传花。
分析:传入一组数据集合和设定的数字 number,循环遍历数组内元素,遍历到的元素为指定数字 number 时将该元素删除,直至数组剩下一个元素。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| function passGame(nameList, number) { const queue = new Queue();
for (const name of nameList) { queue.enqueue(name); }
while (queue.size() > 1) {
for (let i = 0; i < number - 1; i++) { queue.enqueue(queue.dequeue()); }
queue.dequeue(); }
const endName = queue.front();
return nameList.indexOf(endName); }
|
测试代码
1 2 3 4
| const names = ["lily", "lucy", "tom", "tony", "jack"]; const targetIndex = passGame(names, 4); console.log("击鼓传花", names[targetIndex]);
|