C++鏈棧的實現代碼怎么寫

C++鏈棧的實現代碼怎么寫

鏈棧是一種基于鏈表實現的棧結構，它具有動態分配內存、無需預先設定棧的大小等優點。本文將詳細介紹如何使用C++實現鏈棧，并提供完整的代碼示例。

1. 鏈棧的基本概念

棧是一種后進先出（LIFO, Last In First Out）的數據結構，鏈棧則是通過鏈表來實現棧的操作。鏈棧的每個節點包含兩個部分：數據域和指針域。數據域用于存儲數據，指針域用于指向下一個節點。

鏈棧的基本操作包括： - Push: 將元素壓入棧頂。 - Pop: 彈出棧頂元素。 - Top: 獲取棧頂元素。 - IsEmpty: 判斷棧是否為空。

2. 鏈棧的節點結構

首先，我們需要定義一個節點結構，用于表示鏈棧中的每個節點。

struct Node {
    int data;       // 數據域
    Node* next;    // 指針域，指向下一個節點

    Node(int val) : data(val), next(nullptr) {}
};

在這個結構中，data用于存儲節點的數據，next指針用于指向下一個節點。

3. 鏈棧類的定義

接下來，我們定義一個LinkedStack類，用于封裝鏈棧的操作。

class LinkedStack {
private:
    Node* top;  // 棧頂指針

public:
    LinkedStack() : top(nullptr) {}  // 構造函數，初始化棧頂指針為空
    ~LinkedStack();                 // 析構函數，用于釋放內存

    void push(int val);  // 壓棧操作
    void pop();          // 彈棧操作
    int topElement();    // 獲取棧頂元素
    bool isEmpty();      // 判斷棧是否為空
};

4. 鏈棧操作的實現

4.1 壓棧操作（Push）

壓棧操作是將一個新元素添加到棧頂。我們需要創建一個新節點，并將其插入到鏈表的頭部。

void LinkedStack::push(int val) {
    Node* newNode = new Node(val);  // 創建新節點
    newNode->next = top;            // 新節點的next指向當前棧頂
    top = newNode;                  // 更新棧頂指針
}

4.2 彈棧操作（Pop）

彈棧操作是移除棧頂元素。我們需要刪除鏈表頭部的節點，并更新棧頂指針。

void LinkedStack::pop() {
    if (isEmpty()) {
        std::cout << "棧為空，無法執行彈棧操作！" << std::endl;
        return;
    }
    Node* temp = top;  // 臨時保存棧頂節點
    top = top->next;   // 更新棧頂指針
    delete temp;       // 釋放原棧頂節點的內存
}

4.3 獲取棧頂元素（Top）

獲取棧頂元素的操作是返回棧頂節點的數據。

int LinkedStack::topElement() {
    if (isEmpty()) {
        std::cout << "棧為空，無法獲取棧頂元素！" << std::endl;
        return -1;  // 返回一個無效值表示棧為空
    }
    return top->data;  // 返回棧頂元素的數據
}

4.4 判斷棧是否為空（IsEmpty）

判斷棧是否為空的操作是檢查棧頂指針是否為nullptr。

bool LinkedStack::isEmpty() {
    return top == nullptr;  // 如果棧頂指針為空，則棧為空
}

4.5 析構函數

析構函數用于釋放鏈棧中所有節點的內存，防止內存泄漏。

LinkedStack::~LinkedStack() {
    while (!isEmpty()) {
        pop();  // 逐個彈出棧頂元素，釋放內存
    }
}

5. 完整代碼示例

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedStack {
private:
    Node* top;

public:
    LinkedStack() : top(nullptr) {}
    ~LinkedStack();

    void push(int val);
    void pop();
    int topElement();
    bool isEmpty();
};

LinkedStack::~LinkedStack() {
    while (!isEmpty()) {
        pop();
    }
}

void LinkedStack::push(int val) {
    Node* newNode = new Node(val);
    newNode->next = top;
    top = newNode;
}

void LinkedStack::pop() {
    if (isEmpty()) {
        std::cout << "棧為空，無法執行彈棧操作！" << std::endl;
        return;
    }
    Node* temp = top;
    top = top->next;
    delete temp;
}

int LinkedStack::topElement() {
    if (isEmpty()) {
        std::cout << "棧為空，無法獲取棧頂元素！" << std::endl;
        return -1;
    }
    return top->data;
}

bool LinkedStack::isEmpty() {
    return top == nullptr;
}

int main() {
    LinkedStack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    std::cout << "棧頂元素: " << stack.topElement() << std::endl;

    stack.pop();
    std::cout << "彈棧后棧頂元素: " << stack.topElement() << std::endl;

    stack.pop();
    stack.pop();

    if (stack.isEmpty()) {
        std::cout << "棧為空" << std::endl;
    }

    return 0;
}

6. 運行結果

運行上述代碼，輸出結果如下：

棧頂元素: 30
彈棧后棧頂元素: 20
棧為空

7. 總結

本文詳細介紹了如何使用C++實現鏈棧，并提供了完整的代碼示例。鏈棧通過鏈表實現，具有動態分配內存、無需預先設定棧的大小等優點。通過實現鏈棧的基本操作，我們可以更好地理解棧這種數據結構的工作原理。