JavaScript實現(xiàn)隊列結(jié)構(gòu)過程

更新時間：2022年01月24日 14:15:47 作者：bear*6

這篇文章主要介紹了JavaScript實現(xiàn)隊列結(jié)構(gòu)的過程,隊列即Queue，它是受限的線性表，先進先出，受限之處在于它只允許在表的前端進行刪除操作，下面我們一起進入文章學習更加詳細內(nèi)容,需要的朋友也可以參考一下

一、認識隊列

前面的博客已經(jīng)講了受限的數(shù)據(jù)結(jié)構(gòu)—棧，現(xiàn)在，我們再來看看隊列（Queue）。

它是受限的線性表，先進先出（FIFO）,即first in first out。
受限之處在于它只允許在表的前端（front）進行刪除操作。
而在表的后端（rear）進行插入操作。

其結(jié)構(gòu)圖可以表示為：

生活中類似于隊列的：例如：當我們在排隊買東西的時候，先到先買一樣。

二、封裝隊列

這里也采用數(shù)組的方式實現(xiàn)隊列結(jié)構(gòu)，首先，創(chuàng)建一個類。

 function Queue(){
            
        }

在其內(nèi)部添加屬性和方法，將數(shù)組通過屬性的方法添加給該類。然后采用原型的方法添加常用的操作。

隊列常用的操作有：

enqueue(element)：向隊列尾部添加一個（或多個）新的項
dequeue() ：移除隊列的第一（即排在隊列最前面的）項，并且返回被移除的元素
front() ：返回隊列中第一個元素----最先被添加，也將是最先被移除的元素
isEmpty() ：如果隊列中不包含任何元素，返回true，否則，返回false
size() ：返回隊列包含的元素個數(shù)
toString() ：將隊列中的內(nèi)容，轉(zhuǎn)化成字符串形式

現(xiàn)在就來具體實現(xiàn)：

function Queue(){
     this.items = [];
     //向隊列尾部添加一個（或多個）新的項 enqueue()
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除隊列的第一（即排在隊列最前面的）項dequeue()
     Queue.prototype.dequeue = function(){
          return this.items.shift();
      }
     //返回隊列中第一個元素 front()
     Queue.prototype.front = function() {
          return this.items[0];
      }
     //判斷棧是否空isEmpty()
     Queue.prototype.isEmpty = function(){
         return this.items.length == 0;
     }
     //返回隊列包含的元素個數(shù) size()
     Queue.prototype.size = function(){
         return this.items.length;
     }
     //將隊列中的內(nèi)容，轉(zhuǎn)化成字符串形式 toString()
     Queue.prototype.toString  = function(){
         var str = '';
         for(var i =0;i<this.items.length;i++){
             str += this.items[i] + ' ';
         }
         return str;
     }
 }

以上就是隊列的封裝，現(xiàn)在進行驗證：

 var queue = new Queue();
 queue.enqueue(10);
 queue.enqueue(20);
 queue.enqueue(30);
 queue.enqueue(40);
 queue.enqueue(50);
 console.log(queue);
 console.log('移除的第一項是：'+queue.dequeue());
 console.log('隊列中的第一個元素是：'+queue.front());
 console.log('棧是否為空：'+queue.isEmpty());
 console.log('棧結(jié)構(gòu)的內(nèi)容為：');
 console.log(queue.toString());

輸出的結(jié)果為：

構(gòu)建成功。

來看一個擊鼓傳花的案例吧！

三、擊鼓傳花案列

原游戲規(guī)則：

班級中玩一個游戲，所有學生圍成一圈，從某位同學手里開始像旁邊的同學傳一束花
此時一個人在擊鼓，當鼓聲停下的時候，花落在誰手里，誰就被懲罰。

修改游戲規(guī)則：

幾個朋友一起玩游戲，圍成一圈，開始數(shù)數(shù)，數(shù)到某個數(shù)字的人自動淘汰
最后剩下的這個人獲得勝利，判斷最后剩下的是原來在哪一個位置上的人？

封裝一個基于隊列的函數(shù)：

參數(shù)：所有參與人的姓名，基于的數(shù)字
結(jié)果：最終剩下的人的姓名

代碼如下：

 // 封裝隊列
 function Queue(){
     this.items = [];
     //末尾添加元素
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除第一個元素
     Queue.prototype.dequeue = function(){
         return this.items.shift();
     }
     //返回第一個元素
     Queue.prototype.front = function(){
         return this.items[0];
     }
     //返回隊列包含的元素個數(shù)
     Queue.prototype.size = function(){
         return this.items.length;
     }
 }
 
 function passGame(nameList,num){
     // 創(chuàng)建隊列
     var queue = new Queue();
     //將所有的人添加到隊列
     for(var i = 0;i<nameList.length;i++){
         queue.enqueue(nameList[i]);
     }
     //進行游戲
    while(queue.size() > 1){
         //num數(shù)字之前的人重新添加到隊列末尾
         for(var i =1;i<num;i++){
             queue.enqueue(queue.dequeue());
         }
       //num數(shù)字的人直接移除
         queue.dequeue();
    }
    //獲取獲勝者信息
    var endName = queue.front();
    console.log('最終剩下的人是：'+endName);
    return nameList.indexOf(endName);
 }
 
 //進行測試
 var nameList = ['a','b','c','d','e'];
 var g = passGame(nameList,5);
 console.log('這個人的位置是：'+g);

輸出結(jié)果為：