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

現在暫停片刻，想象一下我們作為用戶和開發人員有多少次使用堆棧和隊列。這太神奇了，對吧？由于它們在設計上的普遍性和相似性，我決定使用它們來向您介紹數據結構。

堆棧

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

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

使用盤子表示堆棧

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

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

堆棧的表示

堆棧的操作

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

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

在 JavaScript 中實現堆棧

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

話雖如此，從頭開始實現堆棧仍然是一個很好的學習練習！

堆棧的屬性

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

class Stack {

constructor() {

this._size = 0;

this._storage = {};

}

}

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

堆棧的方法

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

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

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

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

// 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++;

}

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

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

從堆棧中彈出數據pop()

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

以下是我們對這種方法的目標：

1. 使用堆棧的當前大小來獲取最近添加的數據。
2. 刪除最近添加的數據。
3. 減_this._size一。
4. 返回最近刪除的數據。
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()滿足我們五個目標中的每一個。首先，我們聲明兩個變量：size初始化為堆棧的大小，并deletedData 分配給最近添加到堆棧的數據。其次，我們刪除了我們最近添加的數據的鍵值對。第三，我們將堆棧的大小減 1。第四，我們返回從堆棧中刪除的數據。

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

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

使用 JavaScriptArray作為堆棧

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

以下是如何使用 JavaScript 的內置堆棧：

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

nums.push(6);

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

在上面的例子中，nums是一個數字數組。6我們使用方法推入push。

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

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

const num = nums.pop();

console.log(num); // 4

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

從棧到隊列

當我們想要按順序添加數據和刪除數據時，堆棧很有用。根據其定義，堆棧只能刪除最近添加的數據。如果我們想刪除最舊的數據會發生什么？我們想使用一個名為隊列的數據結構。

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

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

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

真實世界隊列的示例

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

隊列的操作

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

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

JavaScript 中隊列的實現

現在讓我們編寫隊列的代碼！同樣，JavaScript 數組已經實現了這些隊列操作，但我們將從頭開始編寫它們以供練習。

隊列的屬性

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

class Queue {

constructor() {

this._oldestIndex = 0;

this._newestIndex = 0;

this._storage = {};

}

}

隊列的方法

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

獲取隊列的大小size()

size() {

return this._newestIndex - this._oldestIndex;

}

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

再想想熟食店的例子。當客戶進來并從票務系統取票時，隊列的大小會增加一。當工作人員呼叫該工單時，隊列的大小會減一。在此示例中，客戶最近撥打的號碼對應_newestIndex物業，員工最后撥打的號碼對應_oldestIndex物業。他們之間的區別在于仍在等待他們的號碼被呼叫的客戶數量。

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

對于enqueue，我們有兩個目標：

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

基于這兩個目標，我們將創建以下實現enqueue(data)：

enqueue(data) {

this._storage[this._newestIndex] = data;

this._newestIndex++;

}

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

這就是我們需要的所有代碼enqueue(data)。現在讓我們實施dequeue().

從隊列中刪除數據 dequeue()

以下是此方法的目標：

1. 刪除隊列中最舊的數據。
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為 分配隊列的當前值this._oldestIndex。第二個變量deletedData被賦予 中包含的值this._storage[oldestIndex]。

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

使用內置方法的隊列操作

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

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

入隊操作使用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()但它從數組的開頭刪除了元素。

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

const num = nums.shift();

console.log(num); // 5

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

盡管使用內置函數可以輕松完成堆棧和隊列操作，但了解這些數據結構背后的核心邏輯至關重要。它可以幫助你加強你的基礎。這就是從頭開始展示實現的原因。

結論

在本文中，我們探索了兩種線性數據結構：堆棧和隊列。堆棧按順序存儲數據并刪除最近添加的數據；隊列按順序存儲數據，但刪除最舊的添加數據。

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