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++实现链栈，并提供了完整的代码示例。链栈通过链表实现，具有动态分配内存、无需预先设定栈的大小等优点。通过实现链栈的基本操作，我们可以更好地理解栈这种数据结构的工作原理。