隊列是遵循FIFO(First In First Out,先進先出,也稱為先來先服務)原則的一組有序的項。隊列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊列的末尾。
1.構造函數建構隊列函數
let Queue = (function () {
const items = new WeakMap();
const weak = {};
return function(){
items.set(weak, []);
this. enqueue = function() { //向隊列添加一個或多個元素
let arr = items.get(weak);
for(let i = 0,length = arguments.length;i<length;i++){
arr.push(arguments[i]);
}
};
this.dequeue= function(valule) { //從隊列移除元素
let arr = items.get(weak);
return arr.shift(); //傳回移除的元素
}
this.front = function(){ //檢視隊列頭元素
let arr = items.get(weak);
return arr[0];
}
this.isEmpty = function(){ //檢查隊列是否為空
let arr = items.get(weak);
return arr.length == 0;
}
this.print = function(){
let arr = items.get(weak);
console.log(arr.toString());
}
}
})();
let queue = new Queue();
queue.enqueue(1,2,3);
console.log(queue.isEmpty());//false
queue.print();//1,2,3
2.用ES6文法實作隊列函數
let Queue = (function () {
const items = new WeakMap();
class Queue1 {
constructor(){
items.set(this,[]);
}
enqueue () { //向隊列添加一個或多個元素
let arr = items.get(this);
for(let i = 0,length = arguments.length;i<length;i++){
arr.push(arguments[i]);
}
};
dequeue(valule) { //從隊列移除元素
let arr = items.get(this);
return arr.shift(); //傳回移除的元素
}
front (){ //檢視隊列頭元素
let arr = items.get(this);
return arr[0];
}
isEmpty(){ //檢查隊列是否為空
let arr = items.get(this);
return arr.length == 0;
}
print (){
let arr = items.get(this);
console.log(arr.toString());
}
}
return Queue1
})();
let queue = new Queue();
queue.enqueue(1,2,3);
console.log(queue.isEmpty());//false
queue.print();//1,2,3
3.優先隊列
元素的添加和移除是基于優先級的。一個現實的例子就是機場登機的順序。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。在有些國家,老年人和孕婦(或帶小孩的婦女)登機時也享有高于其他乘客的優先級。另一個現實中的例子是醫院的(急診科)候診室。醫生會優先處理病情比較嚴重的患者。通常,護士會鑒别分類,根據患者病情的嚴重程度放号。實作一個優先隊列,有兩種選項:設定優先級,然後在正确的位置添加元素;或者用入列操作添加元素,然後按照優先級移除它們。
let PriorityQueue = (function() {
const items = new WeakMap();
const weak = {};
function QueueElement (element, priority){ // {1}
this.element = element;
this.priority = priority;
}
return function(){
items.set(weak, []);
this.enqueue = function(element, priority){
let arr = items.get(weak);
let queueElement = new QueueElement(element, priority);
let added = false;
for (let i=0; i<arr.length; i++){
if (queueElement.priority < arr[i].priority){ // {2}
arr.splice(i,0,queueElement); // {3}
added = true;
break; // {4}
}
}
if (!added){
arr.push(queueElement); //{5}
}
};
this.dequeue= function(valule) { //從隊列移除元素
let arr = items.get(weak);
return arr.shift(); //傳回移除的元素
}
this.front = function(){ //檢視隊列頭元素
let arr = items.get(weak);
return arr[0];
}
this.isEmpty = function(){ //檢查隊列是否為空
let arr = items.get(weak);
return arr.length == 0;
}
this.print = function(){
let arr = items.get(weak);
for (let i=0; i<arr.length; i++){
console.log(`${arr[i].element} - ${arr[i].priority}`);
}
};
}
})()
let queue = new PriorityQueue();
console.log(queue);
queue.enqueue('zhanhong',2);
queue.enqueue('zhan3',3);
queue.enqueue('zhan4',4);
queue.enqueue('zhang1',1);
console.log(queue.isEmpty());
console.log(queue.front());
queue.print();
4.javascript 任務隊列
當我們在浏覽器中打開新标簽時,就會建立一個任務隊列。這是因為每個标簽都是單線程處理所有的任務,它被稱為事件循環。浏覽器要負責多個任務,如渲染HTML,執行JavaScript代碼,處理使用者互動(使用者輸入、滑鼠點選等),執行和處理異步請求。