天天看點

javascript 實作資料結構 - 隊列

隊列是遵循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代碼,處理使用者互動(使用者輸入、滑鼠點選等),執行和處理異步請求。

繼續閱讀