计算机知识

当前位置:澳门新葡萄京 > 计算机知识 > 第一个发送到打印队列的文档会首先被打印

第一个发送到打印队列的文档会首先被打印

来源:http://www.hhmtch.com 作者:澳门新葡萄京 时间:2020-01-17 02:35

图片 1

前面我们学习了栈的实现,队列和栈非常类似,但是使用了不同的原则,而非后进先出。

队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在计算机科学中,一个最常见的例子就是打印队列。比如说我们要打印五份文档。我们会打开每个文档,然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印,以此类推,直到打印完所有文档。

二、队列的实现

2.1 普通队列

创建普通队列类:

// Queue类

function Queue () {

this.items = [];

this.enqueue = enqueue;

this.dequeue = dequeue;

this.front = front;

this.isEmpty = isEmpty;

this.size = size;

this.clear = clear;

this.print = print;

}

队列里面有一些声明的辅助方法:

enqueue:向队列尾部添加新项

dequeue():移除队列的第一项(即排在队列最前面的项),并返回被移除的元素

front():返回队列中第一个元素,队列不做任何变动,和Stack的peek()方法类似

isEmpty():如果队列中不包含任何元素,返回true,否则返回false

size():返回队列包含的元素个数,与数组的length属性类似

print():打印队列中的元素

clear():清空整个队列

下面我们来一一实现这些辅助方法:

// 向队列尾部添加元素

function enqueue {

this.items.push;

}

// 移除队列的第一个元素,并返回被移除的元素

function dequeue () {

return this.items.shift();

}

// 返回队列的第一个元素

function front () {

return this.items[0];

}

// 判断是否为空队列

function isEmpty () {

return this.items.length === 0;

}

// 获取队列的长度

function size () {

return this.items.length;

}

// 清空队列

function clear () {

this.items = [];

}

// 打印队列里的元素

function print () {

console.log(this.items.toString;

}

创建普通队列实例进行测试:

// 创建Queue实例

var queue = new Queue();

console.log(queue.isEmpty; // true

queue.enqueue; // undefined

queue.enqueue; // undefined

queue.enqueue; // undefined

queue.print(); // "John,Jack,Camila"

console.log(queue.size; // 3

console.log(queue.isEmpty; // false

queue.dequeue(); // "John"

queue.dequeue(); // "Jack"

queue.print(); // "Camila"

queue.clear(); // undefined

console.log(queue.size; // 0

2.2 优先队列

2.2.1 定义

普通队列的添加和移除只依赖于先后顺序,先来的先添加,后来的后添加,然后按照先后顺序依次从队列移除。

但是,还有一种队列叫优先队列,元素的添加和移除是依赖优先级的。

一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。再比如火车,老年人、孕妇和带小孩的乘客是享有优先检票权的。

2.2.2 分类

优先队列分为两类:

最小优先队列

最大优先队列

最小优先队列是把优先级的值最小的元素被放置到队列的最前面。比如有四个元素:”John”, “Jack”, “Camila”, “Tom”,他们的优先级值分别为4,3,2,1。

那么最小优先队列排序应该为:“Tom”,”Camila”,”Jack”,”John”

最大优先队列正好相反,把优先级值最大的元素放置在队列的最前面,以上面的为例,最大优先队列排序应该为:“John”, “Jack”, “Camila”, “Tom”

2.2.2 实现

实现一个优先队列,有两种选项:

设置优先级,根据优先级正确添加元素,然后和普通队列一样正常移除

设置优先级,和普通队列一样正常按顺序添加,然后根据优先级移除

这里最小优先队列和最大优先队列我都采用第一种方式实现,大家可以尝试一下第二种。

所以我只重写enqueue()方法和print()方法,其他方法和上面的普通队列完全相同。完整代码见我的github。

实现最小优先队列:

// 定义最小优先队列

function MinPriorityQueue () {

this.items = [];

this.enqueue = enqueue;

this.dequeue = dequeue;

this.front = front;

this.isEmpty = isEmpty;

this.size = size;

this.clear = clear;

this.print = print;

}

实现最小优先队列enqueue()方法和print()方法:

// 优先队列添加元素,要根据优先级判断在队列中的插入顺序

function enqueue (element, priority) {

var queueElement = {

element: element,

priority: priority

};

if (this.isEmpty {

this.items.push(queueElement);

} else {

var added = false;

for (var i = 0; i < this.size {

if (queueElement.priority < this.items[i].priority) {

this.items.splice(i, 0, queueElement);

added = true;

break ;

}

}

if {

this.items.push(queueElement);

}

}

}

// 打印队列里的元素

function print () {

var strArr = [];

strArr = this.items.map(function {

return `${item.element}->${item.priority}`;

});

console.log(strArr.toString;

}

最小优先队列测试:

// 创建最小优先队列minPriorityQueue实例

var minPriorityQueue = new MinPriorityQueue();

console.log(minPriorityQueue.isEmpty; // true

minPriorityQueue.enqueue("John", 1); // undefined

minPriorityQueue.enqueue("Jack", 3); // undefined

minPriorityQueue.enqueue("Camila", 2); // undefined

minPriorityQueue.enqueue; // undefined

minPriorityQueue.print(); // "John->1,Camila->2,Jack->3,Tom->3"

console.log(minPriorityQueue.size; // 4

console.log(minPriorityQueue.isEmpty; // false

minPriorityQueue.dequeue(); // {element: "John", priority: 1}

minPriorityQueue.dequeue(); // {element: "Camila", priority: 2}

minPriorityQueue.print(); // "Jack->3,Tom->3"

minPriorityQueue.clear(); // undefined

console.log(minPriorityQueue.size; // 0

实现最大优先队列

最大优先队列只要将优先级的判断改为大于号”>”就可以了:在此我向大家推荐一个架构学习交流群。交流学习群号:821169538 里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化、分布式架构等这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多。

// 最大优先队列MaxPriorityQueue类

function MaxPriorityQueue () {

this.items = [];

this.enqueue = enqueue;

this.dequeue = dequeue;

this.front = front;

this.isEmpty = isEmpty;

this.size = size;

this.clear = clear;

this.print = print;

}

// 优先队列添加元素,要根据优先级判断在队列中的插入顺序

function enqueue (element, priority) {

var queueElement = {

element: element,

priority: priority

};

if (this.isEmpty {

this.items.push(queueElement);

} else {

var added = false;

for (var i = 0; i < this.items.length; i ) {

// 注意,只需要将这里改为大于号就可以了

if (queueElement.priority > this.items[i].priority) {

this.items.splice(i, 0, queueElement);

added = true;

break ;

}

}

if {

this.items.push(queueElement);

}

}

}

最大优先队列测试:

// 创建最大优先队列maxPriorityQueue实例

var maxPriorityQueue = new MaxPriorityQueue();

console.log(maxPriorityQueue.isEmpty; // true

maxPriorityQueue.enqueue("John", 1); // undefined

maxPriorityQueue.enqueue("Jack", 3); // undefined

maxPriorityQueue.enqueue("Camila", 2); // undefined

maxPriorityQueue.enqueue; // undefined

maxPriorityQueue.print(); // "Jack->3,Tom->3,Camila->2,John->1"

console.log(maxPriorityQueue.size; // 4

console.log(maxPriorityQueue.isEmpty; // false

maxPriorityQueue.dequeue(); // {element: "Jack", priority: 3}

maxPriorityQueue.dequeue(); // {element: "Tom", priority: 3}

maxPriorityQueue.print(); // "Camila->2,John->1"

maxPriorityQueue.clear(); // undefined

console.log(maxPriorityQueue.size; // 0

2.3 循环队列

还有一种队列实现叫做循环队列

循环队列的一个例子就是击鼓传花游戏(Hot Potato)。在这个游戏中,孩子们围城一个圆圈,击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止,这时花在谁的手里,谁就退出圆圈直到游戏结束。重复这个过程,直到只剩一个孩子。

下面我们在普通队列的基础上,实现一个模拟的击鼓传花游戏:

// 实现击鼓传花

function hotPotato (nameList, num) {

var queue = new Queue();

for (var i = 0; i < nameList.length; i ) {

queue.enqueue(nameList[i]);

}

var eliminated = '';

while (queue.size {

// 循环num次,队首出来去到队尾

for (var i = 0; i < num; i ) {

queue.enqueue(queue.dequeue;

}

// 循环num次过后,移除当前队首的元素

eliminated = queue.dequeue();

console.log(`${eliminated}在击鼓传花中被淘汰!`);

}

// 最后只剩一个元素

return queue.dequeue();

}

// 测试

var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];

var winner = hotPotato(nameList, 10);

console.log(`最后的胜利者是:${winner}`);

执行结果为:

// John在击鼓传花中被淘汰!

// Ingrid在击鼓传花中被淘汰!

// Jack在击鼓传花中被淘汰!

// Camila在击鼓传花中被淘汰!

// 最后的胜利者是:Carl

本文由澳门新葡萄京发布于计算机知识,转载请注明出处:第一个发送到打印队列的文档会首先被打印

关键词: 新浦京 数据结构 队列 JavaScript

上一篇:系统变量 CLASSPATH 的作用

下一篇:没有了