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

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

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

一、認(rèn)識(shí)隊(duì)列

前面的博客已經(jīng)講了受限的數(shù)據(jù)結(jié)構(gòu)—棧，現(xiàn)在，我們?cè)賮砜纯搓?duì)列（Queue）。

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

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

生活中類似于隊(duì)列的：例如：當(dāng)我們?cè)谂抨?duì)買東西的時(shí)候，先到先買一樣。

二、封裝隊(duì)列

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

 function Queue(){
            
        }

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

隊(duì)列常用的操作有：

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

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

function Queue(){
     this.items = [];
     //向隊(duì)列尾部添加一個(gè)（或多個(gè)）新的項(xiàng) enqueue()
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除隊(duì)列的第一（即排在隊(duì)列最前面的）項(xiàng)dequeue()
     Queue.prototype.dequeue = function(){
          return this.items.shift();
      }
     //返回隊(duì)列中第一個(gè)元素 front()
     Queue.prototype.front = function() {
          return this.items[0];
      }
     //判斷棧是否空isEmpty()
     Queue.prototype.isEmpty = function(){
         return this.items.length == 0;
     }
     //返回隊(duì)列包含的元素個(gè)數(shù) size()
     Queue.prototype.size = function(){
         return this.items.length;
     }
     //將隊(duì)列中的內(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;
     }
 }

以上就是隊(duì)列的封裝，現(xiàn)在進(jìn)行驗(yà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('移除的第一項(xiàng)是：'+queue.dequeue());
 console.log('隊(duì)列中的第一個(gè)元素是：'+queue.front());
 console.log('棧是否為空：'+queue.isEmpty());
 console.log('棧結(jié)構(gòu)的內(nèi)容為：');
 console.log(queue.toString());

輸出的結(jié)果為：

構(gòu)建成功。

來看一個(gè)擊鼓傳花的案例吧！

三、擊鼓傳花案列

原游戲規(guī)則：

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

修改游戲規(guī)則：

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

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

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

代碼如下：

 // 封裝隊(duì)列
 function Queue(){
     this.items = [];
     //末尾添加元素
     Queue.prototype.enqueue = function(element){
         this.items.push(element);
     }
     //移除第一個(gè)元素
     Queue.prototype.dequeue = function(){
         return this.items.shift();
     }
     //返回第一個(gè)元素
     Queue.prototype.front = function(){
         return this.items[0];
     }
     //返回隊(duì)列包含的元素個(gè)數(shù)
     Queue.prototype.size = function(){
         return this.items.length;
     }
 }
 
 function passGame(nameList,num){
     // 創(chuàng)建隊(duì)列
     var queue = new Queue();
     //將所有的人添加到隊(duì)列
     for(var i = 0;i<nameList.length;i++){
         queue.enqueue(nameList[i]);
     }
     //進(jìn)行游戲
    while(queue.size() > 1){
         //num數(shù)字之前的人重新添加到隊(duì)列末尾
         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);
 }
 
 //進(jìn)行測(cè)試
 var nameList = ['a','b','c','d','e'];
 var g = passGame(nameList,5);
 console.log('這個(gè)人的位置是：'+g);

輸出結(jié)果為：

到此這篇關(guān)于JavaScript實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)過程的文章就介紹到這了,更多相關(guān)JavaScript實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: