當我們談論堆疊（Stack）時，它可以透過兩種主要方式來實作：一是陣列，另一是鏈結串列。在上一篇文章中，我們已經介紹了如何使用陣列來實作堆疊。在本文中，我們將探討如何使用鏈結串列來實作堆疊。

使用鏈結串列來實作堆疊的主要優勢是它可以動態地調整大小，因此沒有固定的大小限制。

基本結構
鏈結串列基於節點的概念，每個節點包含一個數據元素和一個指向下一個節點的指針。對於堆疊，我們主要操作其頭部（或稱為 top）。

以下是基本的節點結構：

struct Node {
    int data;
    Node* next;
};

C++中的串列實作堆疊

#include <iostream>
#include <stdexcept>

class Stack {
private:
    struct Node {
        int data;
        Node* next;
    };

    Node* top;

public:
    Stack() : top(nullptr) {}

    // 添加元素到堆疊
    void push(int value) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->next = top;
        top = newNode;
    }

    // 從堆疊刪除頂部元素
    int pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack underflow");
        }
        int poppedValue = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    // 查看堆疊頂部的元素
    int peek() const {
        if (isEmpty()) {
            throw std::underflow_error("Stack is empty");
        }
        return top->data;
    }

    // 檢查堆疊是否為空
    bool isEmpty() const {
        return top == nullptr;
    }

    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

int main() {
    Stack s;
    s.push(5);
    s.push(10);
    s.push(15);
    std::cout << s.peek() << std::endl;  // 顯示 15
    s.pop();
    std::cout << s.peek() << std::endl;  // 顯示 10
    return 0;
}

串列實作堆疊的優點和缺點
優點：

• 動態大小：鏈結串列堆疊可以根據需要動態調整大小。
• 內存效率：只為需要的元素分配內存，不會浪費空間。

缺點：

• 較高的內存消耗：每個節點需要額外的指針來存儲下一個節點的地址。
• 較慢的隨機存取速度：與陣列相比，鏈結串列需要O(n)的時間來存取隨機元素。

總結
鏈結串列實作提供了一個動態的方法來處理堆疊，這對於不確定堆疊大小的情境非常有用。選擇陣列還是鏈結串列主要取決於具體的需求和應用場景。