我們需要創建自己的類來表示一個隊列。先從最基本的聲明類開始:
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;
如果打印隊列的內容,就會得到John
、Jack
和Camila
這三個元素。因為我們向隊列添加了三個元素,所以隊列的大小為3(當然也就不為空了)。
下圖展示了目前為止執行的所有入列操作,以及隊列當前的狀態:
然後,出列兩個元素(執行兩次dequeue
方法)。下圖展示了dequeue
方法的執行過程:
最後,再次打印隊列內容時,就只剩Camila
一個元素了。前兩個入列的元素出列了,最後入列的元素也將是最後出列的。也就是說,我們遵循了先進先出原則。