?Web 開發(fā)中最常用的兩種數(shù)據(jù)結(jié)構(gòu)是堆棧和隊列。許多 Internet 用戶，包括 Web 開發(fā)人員，都沒有意識到這一驚人的事實。如果您是這些開發(fā)人員中的一員，那么請準(zhǔn)備好兩個具有啟發(fā)性的示例：文本編輯器的撤消操作使用堆棧來組織數(shù)據(jù)，以及 Web 瀏覽器的事件循環(huán)，它處理事件（單擊、懸停等） , 使用隊列來處理數(shù)據(jù)。

現(xiàn)在暫停片刻，想象一下我們作為用戶和開發(fā)人員有多少次使用堆棧和隊列。這太神奇了，對吧？由于它們在設(shè)計上的普遍性和相似性，我決定使用它們來向您介紹數(shù)據(jù)結(jié)構(gòu)。

堆棧

在計算機(jī)科學(xué)中，堆棧是一種線性數(shù)據(jù)結(jié)構(gòu)。如果此語句對您來說具有邊際價值，就像它最初對我所做的那樣，請考慮以下替代方案：堆棧將數(shù)據(jù)組織成順序。

這種順序通常被描述為像自助餐廳里的一堆盤子。將盤子添加到一堆盤子中時，盤子會保留添加時間的順序；此外，當(dāng)添加一個盤子時，它會被推向堆棧的底部。每次我們添加一個新盤子時，該盤子都會被推向堆棧的底部，但它也代表了盤子堆棧的頂部。

使用盤子表示堆棧

這個添加盤子的過程將保留每個盤子被添加到堆棧中的順序。從堆疊中取出印版也將保留所有印版的順序。如果從堆疊頂部移除一個盤子，則堆疊中的每個其他盤子仍將保持堆疊中的正確順序。我所描述的（可能用太多詞）是大多數(shù)自助餐廳如何添加和移除盤子！

為了提供一個更技術(shù)性的堆棧示例，讓我們回顧一下文本編輯器的撤消操作。每次將文本添加到文本編輯器時，都會將該文本推入堆棧。文本編輯器的第一個添加代表堆棧的底部；最近的更改代表堆棧的頂部。如果用戶想要撤消最近的更改，則移除堆棧的頂部。可以重復(fù)這個過程，直到堆棧中沒有更多的添加，這是一個空白文件！

堆棧的表示

堆棧的操作

既然我們現(xiàn)在有了一個棧的概念模型，讓我們定義一個棧的兩個操作：

• push(data)將數(shù)據(jù)添加到棧頂。
• pop()刪除并返回最近添加的數(shù)據(jù)。

在 JavaScript 中實現(xiàn)堆棧

在我們開始之前，我應(yīng)該提到 JavaScript 有一個很棒的內(nèi)置堆棧（和隊列）實現(xiàn)：Array類型。沒錯：每個 JavaScript 數(shù)組都有push()和pop()函數(shù)。因此，如果您想在生產(chǎn)代碼中使用堆棧（或隊列），只需使用常規(guī) JavaScript 數(shù)組即可。

話雖如此，從頭開始實現(xiàn)堆棧仍然是一個很好的學(xué)習(xí)練習(xí)！

堆棧的屬性

對于我們的實現(xiàn)，我們將創(chuàng)建一個名為 Stack. 的每個實例 Stack都有兩個屬性：_size和_storage。

class Stack {

constructor() {

this._size = 0;

this._storage = {};

}

}

this._storage使每個實例Stack 都有自己的容器來存儲數(shù)據(jù)；this._size 反映數(shù)據(jù)被推送到當(dāng)前版本的次數(shù)Stack。如果創(chuàng)建了一個新的實例Stack 并將數(shù)據(jù)推入其存儲，this._size則將增加到1。如果再次將數(shù)據(jù)推入堆棧，this._size則將增加到2。如果從堆棧中刪除數(shù)據(jù)，this._size則將減少到1 .

堆棧的方法

我們需要定義可以從堆棧中添加（推送）和刪除（彈出）數(shù)據(jù)的方法。讓我們從推送數(shù)據(jù)開始。

將數(shù)據(jù)推送到堆棧push(data)

我們對這種方法有兩個要求：

1. 每次添加數(shù)據(jù)時，我們都希望增加堆棧的大小。
2. 每次添加數(shù)據(jù)時，我們都希望保留添加數(shù)據(jù)的順序。

// assigns size as a key of storage

// assigns data as the value of this key

this._storage[this._size] = data;

// Increases the size of our storage

this._size++;

}

我們的實現(xiàn) push(data) 包括以下邏輯。聲明一個名為的變量size并為其賦值this._size++。賦值size 為 的鍵this._storage，賦值data 為對應(yīng)鍵的值。

如果我們的堆棧調(diào)用push(data)了五次，那么我們的堆棧大小將為 5。第一次推送到堆棧將為該數(shù)據(jù)分配一個 1 in 的鍵this._storage。第五次調(diào)用push(data) 將為該數(shù)據(jù)分配一個 5 in 的鍵this._storage。我們剛剛為我們的數(shù)據(jù)分配了順序！

從堆棧中彈出數(shù)據(jù)pop()

我們現(xiàn)在可以將數(shù)據(jù)推送到堆棧；下一個邏輯步驟是從堆棧中彈出（刪除）數(shù)據(jù)。從堆棧中彈出數(shù)據(jù)不僅僅是刪除數(shù)據(jù)；它只刪除最近添加的數(shù)據(jù)。

以下是我們對這種方法的目標(biāo)：

1. 使用堆棧的當(dāng)前大小來獲取最近添加的數(shù)據(jù)。
2. 刪除最近添加的數(shù)據(jù)。
3. 減_this._size一。
4. 返回最近刪除的數(shù)據(jù)。
5. null如果堆棧為空，則返回。

pop() {

if (this._size == 0)

return null;

let deletedData = this._storage[this._size - 1];

delete this._storage[this._size - 1];

this._size--;

return deletedData;

}

pop()滿足我們五個目標(biāo)中的每一個。首先，我們聲明兩個變量：size初始化為堆棧的大小，并deletedData 分配給最近添加到堆棧的數(shù)據(jù)。其次，我們刪除了我們最近添加的數(shù)據(jù)的鍵值對。第三，我們將堆棧的大小減 1。第四，我們返回從堆棧中刪除的數(shù)據(jù)。

如果我們測試我們當(dāng)前的實現(xiàn)pop()，我們會發(fā)現(xiàn)它適用于以下用例。如果我們push(data)將數(shù)據(jù)寫入堆棧，堆棧的大小會增加 1。如果我們pop()從堆棧中獲取數(shù)據(jù)，堆棧的大小會減一。

pop()但是，如果我們在將任何數(shù)據(jù)添加到堆棧之前嘗試使用push()，我們將得到null。

使用 JavaScriptArray作為堆棧

即使我們在本文中從頭開始實現(xiàn)堆棧，也不必每次都編寫邏輯來構(gòu)建堆棧。堆棧已在 JavaScript 數(shù)組中實現(xiàn)。JavaScript 提供了兩種方法，push并pop在數(shù)組中執(zhí)行相同的操作。

以下是如何使用 JavaScript 的內(nèi)置堆棧：

const nums = [5, 8, 1, 4];

nums.push(6);

console.log(nums); // [5, 8, 1, 4, 6]

在上面的例子中，nums是一個數(shù)字?jǐn)?shù)組。6我們使用方法推入push。

操作的用法pop也類似。您在數(shù)組上調(diào)用該pop方法，它會刪除數(shù)組的最后一個元素。

const nums = [5, 8, 1, 4];

const num = nums.pop();

console.log(num); // 4

console.log(nums); // [5, 8, 1]

從棧到隊列

當(dāng)我們想要按順序添加數(shù)據(jù)和刪除數(shù)據(jù)時，堆棧很有用。根據(jù)其定義，堆棧只能刪除最近添加的數(shù)據(jù)。如果我們想刪除最舊的數(shù)據(jù)會發(fā)生什么？我們想使用一個名為隊列的數(shù)據(jù)結(jié)構(gòu)。

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

為了幫助您概念化這將如何工作，讓我們花點時間使用一個類比。想象一個隊列與熟食店的售票系統(tǒng)非常相似。每個客戶拿一張票，并在呼叫他們的號碼時得到服務(wù)。拿第一張票的顧客應(yīng)該先得到服務(wù)。

讓我們進(jìn)一步想象這張票上顯示了數(shù)字“一”。下一張票上顯示數(shù)字“二”。拿第二張票的顧客將獲得第二張服務(wù)。（如果我們的票務(wù)系統(tǒng)像棧一樣運(yùn)行，那么首先進(jìn)入棧的客戶將是最后一個被服務(wù)的客戶！）

真實世界隊列的示例

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

隊列的操作

由于我們現(xiàn)在有一個隊列的概念模型，讓我們定義它的操作。您會注意到，隊列的操作與堆棧非常相似。不同之處在于刪除數(shù)據(jù)的位置。

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

JavaScript 中隊列的實現(xiàn)

現(xiàn)在讓我們編寫隊列的代碼！同樣，JavaScript 數(shù)組已經(jīng)實現(xiàn)了這些隊列操作，但我們將從頭開始編寫它們以供練習(xí)。

隊列的屬性

對于我們的實現(xiàn)，我們將創(chuàng)建一個名為Queue. 然后我們將添加三個屬性：_oldestIndex、_newestIndex和_storage。_oldestIndex兩者的需求 _newestIndex將在下一節(jié)中變得更加清晰。

class Queue {

constructor() {

this._oldestIndex = 0;

this._newestIndex = 0;

this._storage = {};

}

}

隊列的方法

我們現(xiàn)在將創(chuàng)建在隊列的所有實例之間共享的三個方法：size()、enqueue(data)和dequeue(data)。我將概述每種方法的目標(biāo)，揭示每種方法的代碼，然后解釋每種方法的代碼。

獲取隊列的大小size()

size() {

return this._newestIndex - this._oldestIndex;

}

實現(xiàn)size()可能看起來微不足道，但它可能有點棘手。讓我解釋一下原因：我們必須同時跟蹤隊列的開頭和結(jié)尾。由于我們在一端添加并從另一端移除，因此隊列的大小是它們之間的差異。

再想想熟食店的例子。當(dāng)客戶進(jìn)來并從票務(wù)系統(tǒng)取票時，隊列的大小會增加一。當(dāng)工作人員呼叫該工單時，隊列的大小會減一。在此示例中，客戶最近撥打的號碼對應(yīng)_newestIndex物業(yè)，員工最后撥打的號碼對應(yīng)_oldestIndex物業(yè)。他們之間的區(qū)別在于仍在等待他們的號碼被呼叫的客戶數(shù)量。

將數(shù)據(jù)添加到隊列中enqueue(data)

對于enqueue，我們有兩個目標(biāo)：

1. 將值添加到作為鍵this._storage的值。_newestIndex
2. 將 的值增加_newestIndex一。

基于這兩個目標(biāo)，我們將創(chuàng)建以下實現(xiàn)enqueue(data)：

enqueue(data) {

this._storage[this._newestIndex] = data;

this._newestIndex++;

}

如您所見，這段代碼正是我們需要的。

這就是我們需要的所有代碼enqueue(data)?，F(xiàn)在讓我們實施dequeue().

從隊列中刪除數(shù)據(jù) dequeue()

以下是此方法的目標(biāo)：

1. 刪除隊列中最舊的數(shù)據(jù)。
2. 加_oldestIndex一。
3. null如果隊列為空，則返回。

dequeue() {

if (this._oldestIndex == this._newestIndex)

return null;

let deletedData = this._storage[this._oldestIndex];

delete this._storage[this._oldestIndex];

this._oldestIndex++;

return deletedData;

}

在主體中dequeue()，我們聲明了兩個變量。第一個變量oldestIndex為 分配隊列的當(dāng)前值this._oldestIndex。第二個變量deletedData被賦予 中包含的值this._storage[oldestIndex]。

接下來，我們刪除隊列中最舊的索引。刪除后，我們遞增this._oldestIndex1。最后，我們返回剛剛刪除的數(shù)據(jù)。oldestIndex當(dāng)和的值newestIndex相等時，隊列為空，我們返回null。

使用內(nèi)置方法的隊列操作

與內(nèi)置的 Stack 實現(xiàn)類似，隊列也可以通過一些 JavaScript 方法使用。JavaScript 提供了兩種方法，shift和push.

您可以將該push()方法視為將提供的數(shù)據(jù)添加到數(shù)組末尾的入隊操作。

入隊操作使用push()

const nums = [5, 8, 1, 4];

nums.push(2, 3);

console.log(nums); //[5, 8, 1, 4, 2, 3 ]

出隊操作使用shift

該shift()方法從索引位置 0 中刪除一個元素并返回該值，就像該dequeue方法一樣。實際上，它的shift()工作原理與它相同，pop()但它從數(shù)組的開頭刪除了元素。

const nums = [5, 8, 1, 4];

const num = nums.shift();

console.log(num); // 5

console.log(nums); // [8, 1, 4]

盡管使用內(nèi)置函數(shù)可以輕松完成堆棧和隊列操作，但了解這些數(shù)據(jù)結(jié)構(gòu)背后的核心邏輯至關(guān)重要。它可以幫助你加強(qiáng)你的基礎(chǔ)。這就是從頭開始展示實現(xiàn)的原因。

結(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ù)，請考慮使用堆?；蜿犃小?