如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列

前言

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

等等，先想象一下我們作為用戶和程序員，每天使用棧和隊(duì)列的次數(shù)，這太驚人了吧！由于它們?cè)谠O(shè)計(jì)上有普遍性和相似性，我決定從這里開始為大家介紹數(shù)據(jù)結(jié)構(gòu)。

棧

在計(jì)算機(jī)科學(xué)中，棧是一種線性數(shù)據(jù)結(jié)構(gòu)。如果你理解起來有困難，就像最初非常困惑的我一樣，不妨這樣認(rèn)為：一個(gè)棧可以對(duì)數(shù)據(jù)按照順序進(jìn)行組織和管理。

要理解這種順序，我們可以把棧這種結(jié)構(gòu)想象為自助餐廳的一堆盤子，當(dāng)一個(gè)盤子被疊加到一堆盤子上時(shí)，原有的盤子保留了它們?cè)瓉淼捻樞?；同時(shí)，當(dāng)一個(gè)新盤子被添加時(shí)，它會(huì)朝棧的底部方向堆積。每當(dāng)我們添加一個(gè)新盤子時(shí)，被稱作入棧，這個(gè)新盤子處于棧的頂部，也被稱作棧頂。

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

為了是大家理解棧更多的技術(shù)細(xì)節(jié)，讓我們回顧一下前面關(guān)于文本編輯器的“撤消”操作。每次將文本添加到文本編輯器事，該文本被壓入棧中。其中第一次添加的文本代表?xiàng)５牡撞浚５祝?；最后一次的修改表示棧的頂部（棧頂）。如果用戶希望撤銷最后一次修改，則刪除處于棧的頂部的那段文本，這個(gè)過程可以不斷重復(fù)，一直到棧中沒有更多內(nèi)容，這時(shí)我們會(huì)得到一個(gè)空白文件。

棧的操作

現(xiàn)在我們對(duì)棧的模型有了基本概念，下一步就要定義棧的兩個(gè)操作：

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

棧的實(shí)現(xiàn)

現(xiàn)在讓我們開始為棧編寫代碼吧！

棧的屬性

為了實(shí)現(xiàn)棧結(jié)構(gòu)，我們將會(huì)創(chuàng)建一個(gè)名為 Stack 的構(gòu)造函數(shù)。棧的每個(gè)實(shí)例都有兩個(gè)屬性：_size 和 _storage。

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

this._storage 屬性使棧的每一個(gè)實(shí)例都具有自己的用來存儲(chǔ)數(shù)據(jù)的容器； this._size 屬性反映了當(dāng)前棧中數(shù)據(jù)的個(gè)數(shù)。如果創(chuàng)建了一個(gè)新的棧的實(shí)例，并且有一個(gè)數(shù)據(jù)被存入棧中，那么 this._size 的值將被增加到1。如果又有數(shù)據(jù)入棧，this._size 的值將增加到2。如果一個(gè)數(shù)據(jù)從棧中被取出，this._size 的值將會(huì)減少為1。

棧的方法(操作)

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

方法1/2: push(data)

（每一個(gè)棧的實(shí)例都具有這個(gè)方法，所以我們把它添加到棧結(jié)構(gòu)的原型中）
我們對(duì)這個(gè)方法有兩個(gè)要求：

1.每當(dāng)添加數(shù)據(jù)時(shí), 我們希望能夠增加棧的大小。

2.每當(dāng)添加數(shù)據(jù)時(shí),我們希望能夠保留它的添加順序。

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;
};

我們實(shí)現(xiàn)push(data)方法時(shí)要包含以下邏輯：聲明一個(gè)變量 size 并賦值為 this._size++。指定 size 為 this._storage 的鍵;并將數(shù)據(jù)賦給相應(yīng)鍵的值。

如果我們調(diào)用push(data)方法5次，那么棧的大小將是5。第一次入棧時(shí)，將會(huì)把數(shù)據(jù)存入this._storage 中鍵名為1對(duì)應(yīng)的空間，當(dāng)?shù)?次入棧時(shí)，將會(huì)把數(shù)據(jù)存入this._storage 中鍵名為5對(duì)應(yīng)的空間。現(xiàn)在我們的數(shù)據(jù)有了順序！

方法2/2: pop()

我們已經(jīng)實(shí)現(xiàn)了把數(shù)據(jù)送入棧中，下一步我們要從棧中彈出（刪除）數(shù)據(jù)。從棧中彈出數(shù)據(jù)并不是簡(jiǎn)單的刪除數(shù)據(jù)，它只刪除最后一次添加的數(shù)據(jù)。

以下是這個(gè)方法的要點(diǎn)：

1. 使用棧當(dāng)前的大小獲得最后一次添加的數(shù)據(jù)。
2. 刪除最后一次添加的數(shù)據(jù)。
3. 使 _this._size 計(jì)數(shù)減一。
4. 返回剛剛刪除的數(shù)據(jù)。

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

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

如果我們測(cè)試當(dāng)前實(shí)現(xiàn)的pop()方法，會(huì)發(fā)現(xiàn)它適用下面的案例：如果向棧內(nèi)push數(shù)據(jù)，棧的大小會(huì)增加1，如果從棧中pop()數(shù)據(jù)，棧的大小會(huì)減少1！

為了處理這個(gè)用例，我們將向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語句，可以使代碼在存儲(chǔ)中有數(shù)據(jù)時(shí)才被執(zhí)行。

棧的完整實(shí)現(xiàn)

我們已經(jīng)實(shí)現(xiàn)了完整的棧結(jié)構(gòu)。不管以怎樣的順序調(diào)用任何一個(gè)方法，代碼都可以工作！下面使代碼的最終版本：

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;
}
};

從棧到隊(duì)列

當(dāng)我們想要按順序添加數(shù)據(jù)或刪除數(shù)據(jù)時(shí)，可以使用棧結(jié)構(gòu)。根據(jù)它的定義，?？梢灾粍h除最近添加的數(shù)據(jù)。如果想要?jiǎng)h除最早的數(shù)據(jù)該怎么辦呢?這時(shí)我們希望使用名為queue的數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列

與棧類似，隊(duì)列也是一個(gè)線性數(shù)據(jù)結(jié)構(gòu)。與棧不同的是，隊(duì)列只刪除最先添加的數(shù)據(jù)。

為了幫助你明白隊(duì)列是如何工作的，讓我們花點(diǎn)時(shí)間舉個(gè)例子。我們可以把隊(duì)列想象成為熟食店的售票系統(tǒng)。每個(gè)顧客拿一張票，當(dāng)他們的號(hào)碼被呼叫時(shí)接受服務(wù)。持第一張票的顧客首先接受服務(wù)。

再進(jìn)一步想象一下，這張票上有一個(gè)數(shù)字“1”。下一張票上有數(shù)字“2”。得到二張票的顧客將會(huì)第二個(gè)接受服務(wù)。（如果我們的售票系統(tǒng)像棧一樣運(yùn)行，最先進(jìn)入堆棧的客戶將會(huì)最后一個(gè)接受服務(wù)?。?br />

隊(duì)列的一個(gè)更實(shí)際的例子是Web瀏覽器的事件循環(huán)。當(dāng)觸發(fā)不同事件時(shí)，例如單擊某個(gè)按鈕，點(diǎn)擊事件將被添加到事件循環(huán)隊(duì)列中，并按照它們進(jìn)入隊(duì)列的順序進(jìn)行處理。

現(xiàn)在我們具有了隊(duì)列的概念，接下來就要定義它的操作。你會(huì)注意到，隊(duì)列的操作和棧非常相似。區(qū)別就在被刪除的數(shù)據(jù)在什么地方。

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

隊(duì)列的實(shí)現(xiàn)

現(xiàn)在讓我們開始寫隊(duì)列的代碼吧！

隊(duì)列的屬性

在實(shí)現(xiàn)隊(duì)列的代碼中，我們將會(huì)創(chuàng)建一個(gè)名為 Queue 的構(gòu)造方法。接下來添加三個(gè)屬性：_oldestIndex, _newestIndex, 和 _storage。在下一小節(jié)中，_oldestIndex 和 _newestIndex 的作用將變得更加清晰。

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

隊(duì)列的方法

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

方法1/3：size( )

這個(gè)方法有兩個(gè)作用：

• 返回當(dāng)前隊(duì)列的長(zhǎng)度。
• 保持隊(duì)列中鍵的正確范圍。

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

實(shí)現(xiàn) size() 可能顯得微不足道，但你會(huì)很快發(fā)現(xiàn)并不是這樣的。為了理解其原因，我們必須快速重新審視 size() 在棧結(jié)構(gòu)中的實(shí)現(xiàn)。

回想一下棧的概念模型，假設(shè)我們把5個(gè)盤子添加到一個(gè)棧上。棧的大小是5，每個(gè)盤子都有一個(gè)數(shù)字，從1(第一個(gè)添加的盤子)到5(最后一個(gè)添加的盤子)。如果我們?nèi)∽呷齻€(gè)盤子，就只剩下兩個(gè)盤子。我們可以簡(jiǎn)單地用5減去3，得到正確的大小，也就是2。這是關(guān)于棧大小最重要的一點(diǎn)：當(dāng)前大小相當(dāng)于從棧頂部的盤子（2）到棧中其他盤子（1）的計(jì)數(shù)。換句話說，鍵的范圍總是從當(dāng)前大小到1之間。

現(xiàn)在，讓我們將棧大小的實(shí)現(xiàn)應(yīng)用到隊(duì)列中。假設(shè)有五個(gè)顧客從我們的售票系統(tǒng)中取到了票。第一個(gè)顧客有一張顯示數(shù)字1的票，第五個(gè)客戶有一張顯示數(shù)字5的票。現(xiàn)在有了一個(gè)隊(duì)列，拿著第一張票的第一位顧客。

假設(shè)第一個(gè)客戶接受了服務(wù)，這張票會(huì)從隊(duì)列中被移除。與棧類似，我們可以通過從5減去1來獲得隊(duì)列的正確大小。那么服務(wù)隊(duì)列中還有4張票?，F(xiàn)在出現(xiàn)了一個(gè)問題：隊(duì)列的大小不能對(duì)應(yīng)正確的票號(hào)。如果我們從五減去一個(gè)，得到大小是4，但是不能使用4來確定當(dāng)前隊(duì)列中剩余票的編號(hào)范圍。我們并不能確定隊(duì)列中票號(hào)的順序到底是1到4還是2到5。

這就是 oldestIndex 和 newestIndex 這兩個(gè)屬性 在隊(duì)列中的用途。所有這一切似乎令人困惑——到現(xiàn)在我仍然會(huì)偶爾覺得困惑。下面的例子可以幫助我門理順?biāo)械倪壿嫛?br /> 假設(shè)我們的熟食店有兩個(gè)售票系統(tǒng)：

1. _newestindex 代表顧客售票系統(tǒng)的票。
2. _oldestindex 代表員工售票系統(tǒng)的票。

對(duì)于兩個(gè)售票系統(tǒng)來說，這是最難掌握的概念：當(dāng)兩個(gè)系統(tǒng)中的數(shù)字相同時(shí)，隊(duì)列中的每個(gè)客戶都被處理了，隊(duì)列是空的。我們將使用下面的場(chǎng)景來加強(qiáng)這種邏輯：

1. 當(dāng)顧客買票時(shí)，顧客的票號(hào)從_newestIndex 得到，票的編號(hào)是1。顧客售票系統(tǒng)的下一張票號(hào)碼是2。
2. 員工不買票，員工售票系統(tǒng)中當(dāng)前票的編號(hào)是1。
3. 我們?cè)陬櫩拖到y(tǒng)中得到當(dāng)前的票號(hào)2，減去員工系統(tǒng)中的號(hào)碼1，得到的結(jié)果是1。這個(gè)數(shù)字1表示仍然在隊(duì)列中沒有被刪除的票的數(shù)量
4. 員工從它們的售票系統(tǒng)中取票，這張票代表正在被服務(wù)的顧客的票號(hào)，從_oldestIndex中得到，數(shù)字為1。
5. 重復(fù)第4步，現(xiàn)在差為0，隊(duì)列中沒有其他的票了。

現(xiàn)在屬性 _newestindex可以告訴我們被分配在隊(duì)列中票號(hào)的最大值（鍵），屬性 _oldestindex 可以告訴我們最先進(jìn)入隊(duì)列中票號(hào)（鍵）。

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

方法2/3：enqueue(data)

對(duì)于 enqueue 方法，有兩個(gè)功能：

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

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

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

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

方法2/3：dequeue( )

以下是此方法的兩個(gè)功能點(diǎn)：

• 刪除隊(duì)列中最舊的數(shù)據(jù)。
• 屬性 _oldestIndex 加1。

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

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

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

與棧的 pop() 方法第一次實(shí)現(xiàn)中出現(xiàn)的問題類似，dequeue() 在隊(duì)列中沒有數(shù)據(jù)的情況下不應(yīng)該被執(zhí)行。我們需要一些代碼來處理這種情況。

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;
}
};

每當(dāng) oldestIndex 和 newestIndex 的值不相等時(shí)，我們就執(zhí)行前面的邏輯。

隊(duì)列的完整實(shí)現(xiàn)代碼

到此為止，我們實(shí)現(xiàn)了一個(gè)完整的隊(duì)列結(jié)構(gòu)的邏輯。下面是全部代碼。

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;
}
};

結(jié)束語

在本文中，我們探討了兩個(gè)線性數(shù)據(jù)結(jié)構(gòu)：棧和隊(duì)列。棧按照順序存儲(chǔ)數(shù)據(jù)，并刪除最后添加的數(shù)據(jù)；隊(duì)列按順序存儲(chǔ)數(shù)據(jù)，但刪除最先的添加數(shù)據(jù)。

如果這些數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)看起來微不足道，請(qǐng)?zhí)嵝炎约簲?shù)據(jù)結(jié)構(gòu)的用途。它們并沒有被設(shè)計(jì)得過于復(fù)雜，它們是用來幫助我們組織數(shù)據(jù)的。在這種情況下，如果您發(fā)現(xiàn)有需要按順序組織數(shù)據(jù)的場(chǎng)合，請(qǐng)考慮使用棧或隊(duì)列。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。