JavaScript實現隊列結構過程

Posted on by

一、認識隊列

前面的博客已經講瞭受限的數據結構—棧，現在，我們再來看看隊列（Queue）。

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

其結構圖可以表示為：

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

二、封裝隊列

這裡也采用數組的方式實現隊列結構，首先，創建一個類。

 function Queue(){
            
        }

在其內部添加屬性和方法，將數組通過屬性的方法添加給該類。然後采用原型的方法添加常用的操作。

隊列常用的操作有：

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

現在就來具體實現： 

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;
     }
     //返回隊列包含的元素個數 size()
     Queue.prototype.size = function(){
         return this.items.length;
     }
     //將隊列中的內容，轉化成字符串形式 toString()
     Queue.prototype.toString  = function(){
         var str = '';
         for(var i =0;i<this.items.length;i++){
             str += this.items[i] + ' ';
         }
         return str;
     }
 }

以上就是隊列的封裝，現在進行驗證：

 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('棧結構的內容為：');
 console.log(queue.toString());

輸出的結果為：

在這裡插入圖片描述

構建成功。

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

三、擊鼓傳花案列

原遊戲規則：

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

修改遊戲規則：

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

封裝一個基於隊列的函數：

  • 參數：所有參與人的姓名，基於的數字
  • 結果：最終剩下的人的姓名

代碼如下：

 // 封裝隊列
 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];
     }
     //返回隊列包含的元素個數
     Queue.prototype.size = function(){
         return this.items.length;
     }
 }
 
 function passGame(nameList,num){
     // 創建隊列
     var queue = new Queue();
     //將所有的人添加到隊列
     for(var i = 0;i<nameList.length;i++){
         queue.enqueue(nameList[i]);
     }
     //進行遊戲
    while(queue.size() > 1){
         //num數字之前的人重新添加到隊列末尾
         for(var i =1;i<num;i++){
             queue.enqueue(queue.dequeue());
         }
       //num數字的人直接移除
         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);

輸出結果為：

在這裡插入圖片描述

到此這篇關於JavaScript實現隊列結構過程的文章就介紹到這瞭,更多相關JavaScript實現隊列結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：