數(shù)據(jù)結(jié)構(gòu)——隊列

svtter 發(fā)布于2019-08-20 14:23 / 1417人閱讀

摘要：最近一直在學(xué)習(xí)圖數(shù)據(jù)結(jié)構(gòu)，但是他用實現(xiàn)需要用到字典，遍歷的時候又需要用到棧，所以接下來我先把原來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)所記的筆記整理出來隊列基本知識隊列和我們?nèi)粘Ｉ钪械呐抨犚粯樱裱氖窃瓌t，及的原則操作隊列的方法有向尾部插入元素方法完成進隊刪除頭

最近一直在學(xué)習(xí)圖數(shù)據(jù)結(jié)構(gòu)，但是他用js實現(xiàn)需要用到字典，遍歷的時候又需要用到棧，所以接下來我先把原來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)所記的筆記整理出來

隊列基本知識

隊列：和我們?nèi)粘Ｉ钪械呐抨犚粯樱裱氖荈IFO原則，及first in first out的原則
操作隊列的方法有：

向尾部插入元素 enqueue（）方法完成進隊

刪除頭部的元素 dequeue（）方法完成出隊

返回隊列中的第一個元素 front（）方法及最先進入隊列和最先出隊列的元素

還有一些用于查詢的方法：

判斷一個隊列是否為空 isEmpty()方法如果為空就返回true 如果不為空就返回false

返回數(shù)組的容量 size（）方法

將一個數(shù)組打印出來 print（）方法

接下來，我們將實現(xiàn)隊列這個類，首先，定義一個隊列的類，類中有一個私有數(shù)組，存放著我們需要的元素：

let Queue = function(){
       let items = [];
  }

接下來，我們來定義隊列類的公共方法

 //首先創(chuàng)建一個隊列的類
   let Queue = function(){
       let items = [];
       //在數(shù)組末尾添加元素
       this.enqueue = function(e){
         items.push(e);
       }
       //刪除最開頭，也是最先添加的元素
       this.dequeue = function(e){
           return items.shift();
       }
       //讀取隊列中的最先被添加 最先被刪除的元素
       this.front = function(){
           return items[0];
       }
       //判斷數(shù)組是否為空，如果為空就返回true 反之 就返回false
       this.isEmpty = function(){
           return items.length == 0;
       }
       //返回數(shù)組的容量
       this.size = function(){
           return items.length;
       }
       //打印數(shù)組
       this.print = function(){
          console.log(items.toString());
       }
   }

優(yōu)先隊列

就像現(xiàn)實生活中的訂購特等艙的顧客先上機，訂購經(jīng)濟艙的顧客后上機一樣，優(yōu)先隊列就是對權(quán)重較大的元素（用1表示權(quán)重最大）優(yōu)先進行操作，我們有兩種實現(xiàn)方法：

將不同的元素設(shè)置優(yōu)先級，根據(jù)優(yōu)先及將元素添加到數(shù)組的正確位置，修改的是enqueue方法

用入列操作添加元素以后，按照元素的優(yōu)先級執(zhí)行出列，修改的是dequeue方法

我們將用第一種方法進行實現(xiàn)（如果用第二種的話用字典會更加合適一些），其他方法都不變，我們只對enqueue方法進行修改

 //首先創(chuàng)建一個隊列的類
   var Queue = function(){
       var items = [];
       function QueueElements(element,priority){
           this.element = element;
           this.priority = priority;
           return this;
       }
       //在數(shù)組末尾添加元素
       this.equeue = function(element,priority){
         var item = new QueueElements(element,priority);
         if(this.isEmpty()){
             items.push(item);
         }else{
             var added = false;
             for(let i=0;i
函數(shù)解釋：這里的equeue方法 和 以往的 equeue方法區(qū)別就是，添加的元素是一個帶有優(yōu)先級屬性的元素（QueueElements類new出來的一個對象），在添加之前先判斷數(shù)組的是否為空，如果為空就直接插入，如果不為空就對優(yōu)先級進行比較，只要找到比他大的就將該元素插入，將added設(shè)置為true，如果沒有找到比他還大的，那么added依然是false，這時就將元素push到數(shù)組的最后
擊鼓傳花模擬
基本思想就是：如果沒有輪到這個元素，就把該元素從頭部刪除添加到隊列的末尾，如果傳到了，就將該元素刪除，繼續(xù)循環(huán)剩下的元素
function hotPotato(namelist,num){
       //創(chuàng)建一個新的隊列
       let queue = new Queue();
       //將所有元素加入姓名的列表
       for(let i=0;i 1){
          let nameitem = "";
          for(let i=0;i
函數(shù)解釋：游戲不停止的條件是隊列中元素的長度大于1，等于1時則擇出勝利者，循環(huán)，當num不等于7時，就把末尾的移到隊列前面，循環(huán)完畢，num=7，刪除這個時候處在尾部的元素，繼續(xù)執(zhí)行上述操作，直至隊列中只剩一個元素
以上是隊列的全部內(nèi)容，還望各位同仁大神指點一二，我虛心接受