如何使用JavaScript實現棧與隊列

前言

棧和隊列是web開發中最常用的兩種數據結構。絕大多數用戶，甚至包括web開發人員，都不知道這個驚人的事實。如果你是一個程序員，那么請聽我講兩個啟發性的例子:使用堆棧來組織數據，來實現文本編輯器的“撤消”操作;使用隊列處理數據，實現web瀏覽器的事件循環處理事件(單擊click、懸停hoover等)。

等等，先想象一下我們作為用戶和程序員，每天使用棧和隊列的次數，這太驚人了吧！由于它們在設計上有普遍性和相似性，我決定從這里開始為大家介紹數據結構。

棧

在計算機科學中，棧是一種線性數據結構。如果你理解起來有困難，就像最初非常困惑的我一樣，不妨這樣認為：一個棧可以對數據按照順序進行組織和管理。

要理解這種順序，我們可以把棧這種結構想象為自助餐廳的一堆盤子，當一個盤子被疊加到一堆盤子上時，原有的盤子保留了它們原來的順序；同時，當一個新盤子被添加時，它會朝棧的底部方向堆積。每當我們添加一個新盤子時，被稱作入棧，這個新盤子處于棧的頂部，也被稱作棧頂。

這個添加盤子的過程會保留每個盤子被添加到棧中的順序，每次從棧中取出一個盤子時也是一樣的。我可能用了太多的篇幅來描述自助餐廳中的盤子是怎樣被添加和刪除的過程。

為了是大家理解棧更多的技術細節，讓我們回顧一下前面關于文本編輯器的“撤消”操作。每次將文本添加到文本編輯器事，該文本被壓入棧中。其中第一次添加的文本代表棧的底部（棧底）；最后一次的修改表示棧的頂部（棧頂）。如果用戶希望撤銷最后一次修改，則刪除處于棧的頂部的那段文本，這個過程可以不斷重復，一直到棧中沒有更多內容，這時我們會得到一個空白文件。

棧的操作

現在我們對棧的模型有了基本概念，下一步就要定義棧的兩個操作：

• push(data) 添加數據
• pop() 刪除最后添加的數據

棧的實現

現在讓我們開始為棧編寫代碼吧！

棧的屬性

為了實現棧結構，我們將會創建一個名為 Stack 的構造函數。棧的每個實例都有兩個屬性：_size 和 _storage。

function Stack() {
this._size = 0;
this._storage = {};
}

this._storage 屬性使棧的每一個實例都具有自己的用來存儲數據的容器； this._size 屬性反映了當前棧中數據的個數。如果創建了一個新的棧的實例，并且有一個數據被存入棧中，那么 this._size 的值將被增加到1。如果又有數據入棧，this._size 的值將增加到2。如果一個數據從棧中被取出，this._size 的值將會減少為1。

棧的方法(操作)

我們需要定義可以向棧中添加（入棧）和從棧中取出（出棧）數據的方法。讓我們從添加數據開始。

方法1/2: push(data)

（每一個棧的實例都具有這個方法，所以我們把它添加到棧結構的原型中）
我們對這個方法有兩個要求：

1.每當添加數據時, 我們希望能夠增加棧的大小。

2.每當添加數據時,我們希望能夠保留它的添加順序。

Stack.prototype.push = function(data) {
// increases the size of our storage
var size = this._size++;
// assigns size as a key of storage
// assigns data as the value of this key
this._storage[size] = data;
};

我們實現push(data)方法時要包含以下邏輯：聲明一個變量 size 并賦值為 this._size++。指定 size 為 this._storage 的鍵;并將數據賦給相應鍵的值。

如果我們調用push(data)方法5次，那么棧的大小將是5。第一次入棧時，將會把數據存入this._storage 中鍵名為1對應的空間，當第5次入棧時，將會把數據存入this._storage 中鍵名為5對應的空間。現在我們的數據有了順序！

方法2/2: pop()

我們已經實現了把數據送入棧中，下一步我們要從棧中彈出（刪除）數據。從棧中彈出數據并不是簡單的刪除數據，它只刪除最后一次添加的數據。

以下是這個方法的要點：

1. 使用棧當前的大小獲得最后一次添加的數據。
2. 刪除最后一次添加的數據。
3. 使 _this._size 計數減一。
4. 返回剛剛刪除的數據。

Stack.prototype.pop = function() {
var size = this._size,
deletedData;
deletedData = this._storage[size];
delete this._storage[size];
this.size--;
return deletedData;
};

pop()方法滿足以上四個要點。首先，我們聲明了兩個變量：size 用來初始化棧的大小；deletedData 用來保存棧中最后一次添加的數據。第二，我們刪除了最后一次添加的數據的鍵值對。第三，我們把棧的大小減少了1.第四，返回從棧中刪除的數據。

如果我們測試當前實現的pop()方法，會發現它適用下面的案例：如果向棧內push數據，棧的大小會增加1，如果從棧中pop()數據，棧的大小會減少1！

為了處理這個用例，我們將向pop()中添加if語句。

Stack.prototype.pop = function() {
var size = this._size,
deletedData;
if (size) {
deletedData = this._storage[size];
delete this._storage[size];
this._size--;
return deletedData;
}
};

通過添加if語句，可以使代碼在存儲中有數據時才被執行。

棧的完整實現

我們已經實現了完整的棧結構。不管以怎樣的順序調用任何一個方法，代碼都可以工作！下面使代碼的最終版本：

function Stack() {
this._size = 0;
this._storage = {};
}
Stack.prototype.push = function(data) {
var size = ++this._size;
this._storage[size] = data;
};
Stack.prototype.pop = function() {
var size = this._size,
deletedData;
if (size) {
deletedData = this._storage[size];
delete this._storage[size];
this._size--;
return deletedData;
}
};

從棧到隊列

當我們想要按順序添加數據或刪除數據時，可以使用棧結構。根據它的定義，棧可以只刪除最近添加的數據。如果想要刪除最早的數據該怎么辦呢?這時我們希望使用名為queue的數據結構。

隊列

與棧類似，隊列也是一個線性數據結構。與棧不同的是，隊列只刪除最先添加的數據。

為了幫助你明白隊列是如何工作的，讓我們花點時間舉個例子。我們可以把隊列想象成為熟食店的售票系統。每個顧客拿一張票，當他們的號碼被呼叫時接受服務。持第一張票的顧客首先接受服務。

再進一步想象一下，這張票上有一個數字“1”。下一張票上有數字“2”。得到二張票的顧客將會第二個接受服務。（如果我們的售票系統像棧一樣運行，最先進入堆棧的客戶將會最后一個接受服務！）

隊列的一個更實際的例子是Web瀏覽器的事件循環。當觸發不同事件時，例如單擊某個按鈕，點擊事件將被添加到事件循環隊列中，并按照它們進入隊列的順序進行處理。

現在我們具有了隊列的概念，接下來就要定義它的操作。你會注意到，隊列的操作和棧非常相似。區別就在被刪除的數據在什么地方。

• enqueue(data) 將數據添加到隊列中。
• dequeue 刪除最早加入隊列的數據。

隊列的實現

現在讓我們開始寫隊列的代碼吧！

隊列的屬性

在實現隊列的代碼中，我們將會創建一個名為 Queue 的構造方法。接下來添加三個屬性：_oldestIndex, _newestIndex, 和 _storage。在下一小節中，_oldestIndex 和 _newestIndex 的作用將變得更加清晰。

function Queue() {
this._oldestIndex = 1;
this._newestIndex = 1;
this._storage = {};
}

隊列的方法

現在我們將創建隊列會用到的三個方法：size(), enqueue(data), 和 dequeue(data)。我將描述每個方法的作用，寫出每個方法的代碼，然后解釋這些代碼。

方法1/3：size( )

這個方法有兩個作用：

• 返回當前隊列的長度。
• 保持隊列中鍵的正確范圍。

Queue.prototype.size = function() {
return this._newestIndex - this._oldestIndex;
};

實現 size() 可能顯得微不足道，但你會很快發現并不是這樣的。為了理解其原因，我們必須快速重新審視 size() 在棧結構中的實現。

回想一下棧的概念模型，假設我們把5個盤子添加到一個棧上。棧的大小是5，每個盤子都有一個數字，從1(第一個添加的盤子)到5(最后一個添加的盤子)。如果我們取走三個盤子，就只剩下兩個盤子。我們可以簡單地用5減去3，得到正確的大小，也就是2。這是關于棧大小最重要的一點：當前大小相當于從棧頂部的盤子（2）到棧中其他盤子（1）的計數。換句話說，鍵的范圍總是從當前大小到1之間。

現在，讓我們將棧大小的實現應用到隊列中。假設有五個顧客從我們的售票系統中取到了票。第一個顧客有一張顯示數字1的票，第五個客戶有一張顯示數字5的票。現在有了一個隊列，拿著第一張票的第一位顧客。

假設第一個客戶接受了服務，這張票會從隊列中被移除。與棧類似，我們可以通過從5減去1來獲得隊列的正確大小。那么服務隊列中還有4張票。現在出現了一個問題：隊列的大小不能對應正確的票號。如果我們從五減去一個，得到大小是4，但是不能使用4來確定當前隊列中剩余票的編號范圍。我們并不能確定隊列中票號的順序到底是1到4還是2到5。

這就是 oldestIndex 和 newestIndex 這兩個屬性 在隊列中的用途。所有這一切似乎令人困惑——到現在我仍然會偶爾覺得困惑。下面的例子可以幫助我門理順所有的邏輯。
假設我們的熟食店有兩個售票系統：

1. _newestindex 代表顧客售票系統的票。
2. _oldestindex 代表員工售票系統的票。

對于兩個售票系統來說，這是最難掌握的概念：當兩個系統中的數字相同時，隊列中的每個客戶都被處理了，隊列是空的。我們將使用下面的場景來加強這種邏輯：

1. 當顧客買票時，顧客的票號從_newestIndex 得到，票的編號是1。顧客售票系統的下一張票號碼是2。
2. 員工不買票，員工售票系統中當前票的編號是1。
3. 我們在顧客系統中得到當前的票號2，減去員工系統中的號碼1，得到的結果是1。這個數字1表示仍然在隊列中沒有被刪除的票的數量
4. 員工從它們的售票系統中取票，這張票代表正在被服務的顧客的票號，從_oldestIndex中得到，數字為1。
5. 重復第4步，現在差為0，隊列中沒有其他的票了。

現在屬性 _newestindex可以告訴我們被分配在隊列中票號的最大值（鍵），屬性 _oldestindex 可以告訴我們最先進入隊列中票號（鍵）。

探討完了size()，接下來看enqueue(data)方法。

方法2/3：enqueue(data)

對于 enqueue 方法，有兩個功能：

• 使用_newestIndex 的值作為 this._storage 的鍵，并使用要添加的數據作為該鍵的值。
• 將_newestIndex 的值增加1。

基于這兩個功能，我們將編寫 enqueue(data) 方法的代碼：

Queue.prototype.enqueue = function(data) {
this._storage[this._newestIndex] = data;
this._newestIndex++;
};

該方法的主體只有兩行代碼。 在第一行，用 this._newestIndex 為this._storage 創建一個新的鍵，并為其分配數據。 this._newestIndex 始終從1開始。在第二行代碼中，我們將 this._newestIndex 的值增加1，將其更新為2。
以上是方法 enqueue(data) 的所有代碼。下面我們來實現方法 dequeue( )。

方法2/3：dequeue( )

以下是此方法的兩個功能點：

• 刪除隊列中最舊的數據。
• 屬性 _oldestIndex 加1。

Queue.prototype.dequeue = function() {
var oldestIndex = this._oldestIndex,
deletedData = this._storage[oldestIndex];
delete this._storage[oldestIndex];
this._oldestIndex++;
return deletedData;
};

在 dequeue( )的代碼中，我們聲明兩個變量。 第一個變量 oldestIndex 給 this._oldestIndex 賦值。第二個變量 deletedData 被賦予 this._storage[oldestIndex] 的值。

下一步，刪除隊列中最早的索引。之后將 this._oldestIndex 的值加1。最后返回剛剛被刪除的數據。

與棧的 pop() 方法第一次實現中出現的問題類似，dequeue() 在隊列中沒有數據的情況下不應該被執行。我們需要一些代碼來處理這種情況。

Queue.prototype.dequeue = function() {
var oldestIndex = this._oldestIndex,
newestIndex = this._newestIndex,
deletedData;
if (oldestIndex !== newestIndex) {
deletedData = this._storage[oldestIndex];
delete this._storage[oldestIndex];
this._oldestIndex++;
return deletedData;
}
};

每當 oldestIndex 和 newestIndex 的值不相等時，我們就執行前面的邏輯。

隊列的完整實現代碼

到此為止，我們實現了一個完整的隊列結構的邏輯。下面是全部代碼。

function Queue() {
this._oldestIndex = 1;
this._newestIndex = 1;
this._storage = {};
}
Queue.prototype.size = function() {
return this._newestIndex - this._oldestIndex;
};
Queue.prototype.enqueue = function(data) {
this._storage[this._newestIndex] = data;
this._newestIndex++;
};
Queue.prototype.dequeue = function() {
var oldestIndex = this._oldestIndex,
newestIndex = this._newestIndex,
deletedData;
if (oldestIndex !== newestIndex) {
deletedData = this._storage[oldestIndex];
delete this._storage[oldestIndex];
this._oldestIndex++;
return deletedData;
}
};

結束語

在本文中，我們探討了兩個線性數據結構：棧和隊列。棧按照順序存儲數據，并刪除最后添加的數據；隊列按順序存儲數據，但刪除最先的添加數據。

如果這些數據結構的實現看起來微不足道，請提醒自己數據結構的用途。它們并沒有被設計得過于復雜，它們是用來幫助我們組織數據的。在這種情況下，如果您發現有需要按順序組織數據的場合，請考慮使用棧或隊列。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。