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

前言

創(chuàng)新互聯(lián)公司主要為客戶提供服務(wù)項(xiàng)目涵蓋了網(wǎng)頁(yè)視覺(jué)設(shè)計(jì)、VI標(biāo)志設(shè)計(jì)、成都全網(wǎng)營(yíng)銷推廣、網(wǎng)站程序開(kāi)發(fā)、HTML5響應(yīng)式成都網(wǎng)站建設(shè)、成都手機(jī)網(wǎng)站制作、微商城、網(wǎng)站托管及網(wǎng)頁(yè)維護(hù)、WEB系統(tǒng)開(kāi)發(fā)、域名注冊(cè)、國(guó)內(nèi)外服務(wù)器租用、視頻、平面設(shè)計(jì)、SEO優(yōu)化排名。設(shè)計(jì)、前端、后端三個(gè)建站步驟的完善服務(wù)體系。一人跟蹤測(cè)試的建站服務(wù)標(biāo)準(zhǔn)。已經(jīng)為成都辦公空間設(shè)計(jì)行業(yè)客戶提供了網(wǎng)站營(yíng)銷服務(wù)。

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

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

棧

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

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

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

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

棧的操作

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

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

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

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

棧的屬性

為了實(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í)例都具有自己的用來(lái)存儲(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ù)開(kāi)始。

方法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)的空間?，F(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)：

使用棧當(dāng)前的大小獲得最后一次添加的數(shù)據(jù)。
刪除最后一次添加的數(shù)據(jù)。
使 _this._size 計(jì)數(shù)減一。
返回剛剛刪除的數(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 用來(lái)初始化棧的大??；deletedData 用來(lái)保存棧中最后一次添加的數(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語(yǔ)句。

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

通過(guò)添加if語(yǔ)句，可以使代碼在存儲(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ù)?。?/p>

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

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

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

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

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

隊(duì)列的屬性

在實(shí)現(xiàn)隊(duì)列的代碼中，我們將會(huì)創(chuàng)建一個(gè)名為 Queue 的構(gòu)造方法。接下來(lái)添加三個(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ù)。換句話說(shuō)，鍵的范圍總是從當(dāng)前大小到1之間。

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

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

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

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

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

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

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

探討完了size()，接下來(lái)看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開(kāi)始。在第二行代碼中，我們將 this._newestIndex 的值增加1，將其更新為2。
以上是方法 enqueue(data) 的所有代碼。下面我們來(lái)實(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)的問(wèn)題類似，dequeue() 在隊(duì)列中沒(méi)有數(shù)據(jù)的情況下不應(yīng)該被執(zhí)行。我們需要一些代碼來(lái)處理這種情況。

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é)束語(yǔ)

在本文中，我們探討了兩個(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)看起來(lái)微不足道，請(qǐng)?zhí)嵝炎约簲?shù)據(jù)結(jié)構(gòu)的用途。它們并沒(méi)有被設(shè)計(jì)得過(guò)于復(fù)雜，它們是用來(lái)幫助我們組織數(shù)據(jù)的。在這種情況下，如果您發(fā)現(xiàn)有需要按順序組織數(shù)據(jù)的場(chǎng)合，請(qǐng)考慮使用?；蜿?duì)列。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。

本文標(biāo)題：如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列
網(wǎng)頁(yè)路徑：http://muchs.cn/article14/gespge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、定制開(kāi)發(fā)、用戶體驗(yàn)、手機(jī)網(wǎng)站建設(shè)、App設(shè)計(jì)、靜態(tài)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容