了解堆疊資料結構：在 JavaScript 中實作堆疊的逐步指南

堆疊是一種簡單的線性資料結構，其工作原理類似於一堆盤子？ ️。它遵循後進先出 (LIFO) 原則。將其視為一堆盤子：您只能添加或刪除堆頂部的盤子。

為了更好地理解棧，讓我們來一趟短暫的想像之旅吧？ .
想像您在高檔餐廳??️，廚房工作人員正在為忙碌的夜晚做準備??‍?。在餐具區，有一疊高高的盤子等待使用。當食客到來、訂單紛至沓來時，工作人員會從最上面的盤子中取出盤子。當添加乾淨的盤子時，它們會直接放在上面。這個簡單的系統確保了堆疊底部放置時間最長的盤子最後被使用，而頂部剛清潔過的盤子首先被使用✨。

本質上，這就是堆疊資料結構的工作原理。堆疊是一種遵循後進先出 (LIFO) 原則的線性資料結構。就像我們的一堆盤子一樣，最後添加到堆疊中的項目是第一個被刪除的項目。

目錄

在這個關於堆疊資料結構的綜合教程中，我們將透過簡單、適合初學者的方法探索以下主題：

1. 什麼是堆疊？
2. 使用堆疊的優點和缺點
3. 堆疊的實際應用
4. 堆疊上的關鍵操作
5. JavaScript 中的堆疊實作
6. 結論

---

---

你準備好了嗎？讓我們深入了解

什麼是堆疊？

堆疊是一種遵循後進先出（LIFO）原則的線性資料結構。這意味著最後加入堆疊的元素將是第一個被刪除的元素。將其想像為一疊書：您只能新增或刪除書堆頂部的書。

使用堆疊的優點和缺點

在我們繼續流程並編寫一些程式碼之前，了解在哪裡以及在哪裡不使用 Stack 是很有幫助的。下表詳細列出了堆疊的優缺點。

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

堆疊上的關鍵操作

可以在堆疊上執行的基本操作是：

1. push()：將一個元素加入到棧頂。
2. pop()：從堆疊中刪除最頂層的元素。
3. peek()：傳回棧頂元素，但不刪除它。
4. isEmpty()：檢查堆疊是否為空。
5. size()：傳回堆疊中元素的數量。

堆疊的實際應用

堆疊在電腦科學和軟體開發中無所不在。以下是一些常見的應用：

1. 撤銷功能：在文字編輯器或圖形設計軟體中，每個操作都被推入堆疊。當您點擊「撤銷」時，最近的操作將從堆疊中彈出並反轉。

2. 瀏覽器歷史記錄：當您造訪新頁面時，它將被推送到堆疊上。 「後退」按鈕會將目前頁面從堆疊中彈出，顯示上一頁。

3. 函數呼叫堆疊：在程式語言中，函數呼叫是使用堆疊來管理的。當一個函數被呼叫時，它被壓入呼叫堆疊。當它返回時，它會彈出。

4. 表達式計算：堆疊用於計算算術表達式，尤其是後綴表示法的表達式。

5. 回溯演算法：在解決迷宮或解謎等問題中，堆疊可以追蹤所採取的路徑，以便在需要時輕鬆回溯。

JavaScript 中的堆疊實作

現在，讓我們用 JavaScript 實作一個 Stack。重要的是要知道在 JavaScript 中實作堆疊有不同的方法。實作堆疊的常見方法之一是使用數組，另一種方法是使用鍊錶。在本文中，我們將使用鍊錶（單鍊錶）實作堆疊。

使用鍊錶實作堆疊

我希望你還記得鍊錶是如何運作的嗎？您可能需要查看我們本系列之前的一篇文章中的鍊錶實作。

如何在 JavaScript 中實作單鍊錶

偉大的解決方案？ ・ 10 月 4 日

#javascript #初學者 #程式設計 #dsa

現在，讓我們開始使用單鍊錶實作我們的堆疊。我們可以嗎？

首先，我們將建立一個 Node 類別來表示我們的堆疊單一專案。

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

然後，我們將建立一個 Stack 類別來表示我們的堆疊。

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

推播操作

push操作將一個新元素加入到堆疊頂部。它會建立一個新的 StackNode，將其下一個指標設為目前頂部，然後更新頂部以指向這個新節點。最後，它增加了大小。

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

流行操作

彈出操作從堆疊中刪除最頂層的元素。它首先檢查堆疊是否為空。如果是，則傳回錯誤訊息。否則，它刪除頂部元素，更新頂部指標到下一個節點，並減少大小。最後，它會傳回被刪除的元素。

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

窺視操作

peek 操作會傳回頂部元素而不刪除它。它首先檢查堆疊是否為空。如果是，則傳回錯誤訊息。否則，返回頂部元素的資料。

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty操作

isEmpty 操作檢查堆疊是否為空。如果堆疊為空則傳回 true，否則傳回 false。

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

取得大小操作

getSize 操作傳回堆疊的大小。它會傳回堆疊中元素的數量。

  // Return the size of the stack
  getSize() {
    return this.size;
  }

列印操作

列印操作列印堆疊。它會傳回頂部元素的資料。

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

使用範例

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

在此實作中，我們使用鍊錶（單鍊錶）結構來表示我們的堆疊。每個元素都是一個節點，具有資料值和對下一個節點的引用。堆疊頂部始終是最近新增的節點。

結論

堆疊是電腦科學中的基本資料結構，遵循後進先出（LIFO）原則。它們用於各種應用程序，包括管理函數呼叫、實現撤消功能以及計算算術表達式。

在本教程中，我們介紹了堆疊的基礎知識、使用它們的優缺點以及它們在 JavaScript 中的實作（使用鍊錶）。了解堆疊不僅僅是了解如何實現它們，還要認識到它們何時是解決問題的正確工具。

當您繼續軟體開發之旅時，您會發現堆疊是您解決問題的工具箱中不可或缺的工具。它們簡單而強大，掌握它們將顯著增強您設計高效演算法和資料結構的能力。

---

---

保持更新和聯繫

確保您不會錯過本系列的任何部分，並與我聯繫以更深入地討論軟體開發（Web、伺服器、移動或抓取/自動化）、資料結構和演算法以及其他令人興奮的技術主題，請追蹤我：

• GitHub
• 領英
• X（推特）

敬請期待並祝您編碼愉快??‍??

以上是了解堆疊資料結構：在 JavaScript 中實作堆疊的逐步指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！