前言

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

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

棧

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

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

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

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

棧的操作

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

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

棧的實現(xiàn)

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

棧的屬性

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

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

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

棧的方法(操作)

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

方法1/2: push(data)

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

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

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

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

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

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

方法2/2: pop()

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

以下是這個方法的要點：

1. 使用棧當(dāng)前的大小獲得最后一次添加的數(shù)據(jù)。
2. 刪除最后一次添加的數(shù)據(jù)。
3. 使 _this._size 計數(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()方法滿足以上四個要點。首先，我們聲明了兩個變量：size 用來初始化棧的大?。籨eletedData 用來保存棧中最后一次添加的數(shù)據(jù)。第二，我們刪除了最后一次添加的數(shù)據(jù)的鍵值對。第三，我們把棧的大小減少了1.第四，返回從棧中刪除的數(shù)據(jù)。

如果我們測試當(dāng)前實現(xiàn)的pop()方法，會發(fā)現(xiàn)它適用下面的案例：如果向棧內(nèi)push數(shù)據(jù)，棧的大小會增加1，如果從棧中pop()數(shù)據(jù)，棧的大小會減少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語句，可以使代碼在存儲中有數(shù)據(jù)時才被執(zhí)行。

棧的完整實現(xiàn)

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

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

從棧到隊列

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

隊列

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

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

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

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

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

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

隊列的實現(xiàn)

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

隊列的屬性

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

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

隊列的方法

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

方法1/3：size( )

這個方法有兩個作用：

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

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

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

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

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

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

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

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

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

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

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

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

方法2/3：enqueue(data)

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

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

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

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

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

方法2/3：dequeue( )

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

• 刪除隊列中最舊的數(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( )的代碼中，我們聲明兩個變量。 第一個變量 oldestIndex 給 this._oldestIndex 賦值。第二個變量 deletedData 被賦予 this._storage[oldestIndex] 的值。

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

與棧的 pop() 方法第一次實現(xiàn)中出現(xiàn)的問題類似，dequeue() 在隊列中沒有數(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 的值不相等時，我們就執(zhí)行前面的邏輯。

隊列的完整實現(xiàn)代碼

到此為止，我們實現(xiàn)了一個完整的隊列結(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é)束語

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

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論