讀古今文學網 > 學習JavaScript數據結構與算法(第2版) > 4.2 創建隊列 >

4.2 創建隊列

我們需要創建自己的類來表示一個隊列。先從最基本的聲明類開始:

function Queue {
  //這裡是屬性和方法
}

  

首先需要一個用於存儲隊列中元素的數據結構。我們可以使用數組,就像在上一章Stack類中那樣使用(你會發現Queue類和Stack類非常類似,只是添加和移除元素的原則不同):

let items = ;

  

接下來需要聲明一些隊列可用的方法。

  • enqueue(element(s)):向隊列尾部添加一個(或多個)新的項。

  • dequeue:移除隊列的第一(即排在隊列最前面的)項,並返回被移除的元素。

  • front:返回隊列中第一個元素——最先被添加,也將是最先被移除的元素。隊列不做任何變動(不移除元素,只返回元素信息——與Stack類的peek方法非常類似)。

  • isEmpty:如果隊列中不包含任何元素,返回true,否則返回false

  • size:返回隊列包含的元素個數,與數組的length屬性類似。

4.2.1 向隊列添加元素

首先要實現的是enqueue方法。這個方法負責向隊列添加新元素。這裡有一個非常重要的細節,新的項只能添加到隊列末尾:

this.enqueue = function(element){
  items.push(element);
};

  

既然我們使用數組來存儲隊列的元素,就可以用第2章和第3章中介紹過的JavaScript的array類的push方法。

4.2.2 從隊列移除元素

接下來要實現dequeue方法。這個方法負責從隊列移除項。由於隊列遵循先進先出原則,最先添加的項也是最先被移除的。可以用第2章中介紹過的JavaScript的array類的shift方法。如果你不記得了,這裡幫你回憶一下,shift方法會從數組中移除存儲在索引0(第一個位置)的元素:

this.dequeue = function{
  return items.shift;
};

  

只有enqueue方法和dequeue方法可以添加和移除元素,這樣就確保了Queue類遵循先進先出原則。

4.2.3 查看隊列頭元素

現在來為我們的類實現一些額外的輔助方法。如果想知道隊列最前面的項是什麼,可以用front方法。這個方法會返回隊列最前面的項(數組的索引為0):

this.front = function{
  return items[0];
};

  

4.2.4 檢查隊列是否為空

下一個是isEmpty方法。如果隊列為空,它會返回true,否則返回false(注意這個方法和Stack類裡的一樣):

this.isEmpty = function{
  return items.length == 0;
};

  

對於isEmpty方法,可以簡單地驗證內部數組的length是否為0。

我們也可以為Queue類實現類似於array類的length屬性的方法。size方法也跟Stack類裡的一樣:

this.size = function{
  return items.length;
};

  

4.2.5 打印隊列元素

完成!我們的Queue類就實現好了。也可以像Stack類一樣增加一個print方法:

this.print = function{
  console.log(items.toString);
};

  

現在我們真的完成了!

 Queue類和Stack類非常類似。唯一的區別是dequeue方法和front方法,這是由於先進先出和後進先出原則的不同所造成的。

使用Queue類

首先要做的是實例化我們剛剛創建的Queue類,然後就可以驗證它為空(輸出為true,因為我們還沒有向隊列添加任何元素):

let queue = new Queue;
console.log(queue.isEmpty); //輸出true

  

接下來,添加一些元素(添加\"John\"\"Jack\"兩個元素——你可以向隊列添加任何類型的元素):

queue.enqueue(\"John\");
queue.enqueue(\"Jack\");

  

添加另一個元素:

queue.enqueue(\"Camila\");

  

再執行一些其他的命令:

queue.print;
console.log(queue.size); //輸出3
console.log(queue.isEmpty); //輸出false
queue.dequeue;
queue.dequeue;
queue.print;

  

如果打印隊列的內容,就會得到JohnJackCamila這三個元素。因為我們向隊列添加了三個元素,所以隊列的大小為3(當然也就不為空了)。

下圖展示了目前為止執行的所有入列操作,以及隊列當前的狀態:

然後,出列兩個元素(執行兩次dequeue方法)。下圖展示了dequeue方法的執行過程:

最後,再次打印隊列內容時,就只剩Camila一個元素了。前兩個入列的元素出列了,最後入列的元素也將是最後出列的。也就是說,我們遵循了先進先出原則。