Queue
function Queue() {
let items = [];
this.enqueue = function(element){
items.push(element);
};
this.dequeue = function(){
return items.shift();
};
this.front = function(){
return items[0];
};
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}
Queue2
let Queue2 = (function () {
const items = new WeakMap();
class Queue2 {
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(){
return items.get(this).length == 0;
}
size(){
let q = items.get(this);
return q.length;
}
clear(){
items.set(this, []);
}
print(){
console.log(this.toString());
}
toString(){
return items.get(this).toString();
}
}
return Queue2;
})();
使用Queue
let queue = new Queue2();
console.log(queue.isEmpty()); //outputs true
queue.enqueue("John");
queue.enqueue("Jack");
queue.print();
queue.enqueue("Camila");
queue.print();
console.log(queue.size()); //outputs 3
console.log(queue.isEmpty()); //outputs false
queue.dequeue();
queue.dequeue();
queue.print();
优先队列
function PriorityQueue() {
let items = [];
function QueueElement (element, priority){ // {1}
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){ // {2}
items.splice(i,0,queueElement); // {3}
added = true;
break; // {4}
}
}
if (!added){
items.push(queueElement); //{5}
}
};
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}`);
}
};
}
let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print();
PriorityQueue2
let PriorityQueue2 = (function () {
class QueueElement {
constructor(element, priority){
this.element = element;
this.priority = priority;
}
}
const items = new WeakMap();
class PriorityQueue2 { //extends Queue2 { //with this approach the private properties are not reachable through inheritance
constructor () {
items.set(this, []);
}
enqueue(element, priority){
let queueElement = new QueueElement(element, priority);
let q = items.get(this);
let added = false;
for (let i=0; i<q.length; i++){
if (queueElement.priority < q[i].priority){
q.splice(i,0,queueElement);
added = true;
break;
}
}
if (!added){
q.push(queueElement);
}
items.set(this, q);
};
dequeue() {
let q = items.get(this);
let r = q.shift();
items.set(this, q);
return r;
}
front() {
let q = items.get(this);
return q[0];
}
isEmpty(){
return items.get(this).length == 0;
}
size(){
let q = items.get(this);
return q.length;
}
clear(){
items.set(this, []);
}
print(){
let q = items.get(this);
for (let i=0; i<q.length; i++){
console.log(`${q[i].element} - ${q[i].priority}`);
}
};
}
return PriorityQueue2;
})();
let priorityQueue = new PriorityQueue2();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.enqueue("Maxwell", 2);
priorityQueue.enqueue("Ana", 3);
priorityQueue.print();
击鼓传花
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 + ' was eliminated from the Hot Potato game.');
}
return queue.dequeue();
}
let names = ['John','Jack','Camila','Ingrid','Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);
