队列遵循FIFO先进先出原则。
用数组储存队列中的数据结构
队列类
function Queue() {
let items = [];
//向队列尾部添加一个或者多个的项
this.enqueue = function (element) {
items.push(element);
};
//移除队列第一项并返回
//shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。
this.dequeue = function () {
return items.shift();
};
//返回队列的第一个元素，队列不做变动
this.front = function () {
return items[0];
};
//判断队列是否为空
this.isEmpty = function () {
return items.length === 0;
};
//返回队列包含的元素个数
this.size = function () {
return items.length;
};
//打印队列
this.print = function () {
console.log(items.toString());
};
}
使用ES6进行实现
使用WeakMap保存私有属性，外层函数（闭包）来封装Queue类
let Queue = (function () {
const items = new WeakMap();
class Queue{
constructor () {
items.set(this, []);
}
//向队列尾部添加一个或者多个的项
enqueue(element){
let q = items.get(this);
q.push(element);
}
//移除队列第一项并返回
dequeue(){
let q = items.get(this);
let r = q.shift();
return r;
}
//返回队列的第一个元素，队列不做变动
front(){
let q = items.get(this);
return q[0];
}
//判断队列是否为空
isEmpty(){
let q = items.get(this);
return q.length === 0;
};
//返回队列包含的元素个数
size(){
let q = items.get(this);
return q.length;
};
//打印队列
print(){
let q = items.get(this);
console.log(q.toString());
};
}
return Queue;
})();
优先队列
function PriorityQueue() {
let items = [];
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function (element, priority) {
let queueElement = new QueueElement(element, priority);
let added = false;
for(let i = 0; i < items.length; i++){
if (queueElement.priority < items[i].priority){
items.splice(i, 0, queueElement);
added = true;
break;
}
}
if(!added){
items.push(queueElement);
}
};
//移除队列第一项并返回
//shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。
this.dequeue = function () {
return items.shift();
};
//返回队列的第一个元素，队列不做变动
this.front = function () {
return items[0];
};
//判断队列是否为空
this.isEmpty = function () {
return items.length === 0;
};
//返回队列包含的元素个数
this.size = function () {
return items.length;
};
this.print = function () {
for(let i = 0; i < items.length; i++){
console.log(`${items[i].element}-${items[i].priority}`);
}
}
}
循环队列-击鼓传花
//循环队列-击鼓传花
function hotPotato(nameList, num) {
let queue = new Queue();
for(let i = 0;i < nameList.length; i++){
queue.enqueue(nameList[i]);
}
let eliminated = '';
while (queue.size() > 1){
for(let i = 0; i <num; i++){
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(eliminated + '在击鼓传花中被淘汰');
}
return queue.dequeue();
}
let names = ['john','tom','bob','barl','vc','dd'];
let winner = hotPotato(names, 7);
console.log('the winner is ' + winner);
有兴趣可以加入Nodejs交流群，和大佬们一起成长！！！
群号：348108867
图片.png
