堆栈链式存储表示及实现

堆栈是一种先进后出（Last-In-First-Out，LIFO）的数据结构，链式存储是堆栈的一种实现方式。链式存储的堆栈不需要预先指定堆栈的长度，可以动态地分配内存，具有灵活性和可扩展性。

链式存储的堆栈可以使用单向链表或双向链表来实现。以单向链表为例，堆栈的顶端称为栈顶，堆栈的底部称为栈底。

堆栈的基本操作包括入栈（Push）、出栈（Pop）、获取栈顶元素（Top）和判断堆栈是否为空（IsEmpty）。

下面是堆栈链式存储的实现代码：

#include <iostream>

using namespace std;

// 定义堆栈的结点结构体
struct StackNode {
    int data; // 数据域
    StackNode *next; // 指针域，指向下一个结点
};

// 定义堆栈类
class Stack {
private:
    StackNode *top; // 栈顶指针

public:
    Stack() { top = NULL; } // 构造函数，初始化栈顶指针为空
    ~Stack(); // 析构函数，释放内存

    bool IsEmpty(); // 判断堆栈是否为空
    void Push(int x); // 入栈
    int Pop(); // 出栈
    int Top(); // 获取栈顶元素
};

// 判断堆栈是否为空
bool Stack::IsEmpty() {
    return top == NULL;
}

// 入栈
void Stack::Push(int x) {
    StackNode *newNode = new StackNode; // 创建新结点
    newNode->data = x; // 设置数据域
    newNode->next = top; // 将新结点插入到栈顶
    top = newNode; // 更新栈顶指针
}

// 出栈
int Stack::Pop() {
    if (IsEmpty()) { // 判断是否为空栈
        cout << "Error: Stack is empty!" << endl;
        return -1;
    } else {
        StackNode *temp = top; // 保存栈顶结点
        int x = temp->data; // 获取栈顶元素
        top = top->next; // 更新栈顶指针
        delete temp; // 释放内存
        return x;
    }
}

// 获取栈顶元素
int Stack::Top() {
    if (IsEmpty()) { // 判断是否为空栈
        cout << "Error: Stack is empty!" << endl;
        return -1;
    } else {
        return top->data; // 返回栈顶元素
    }
}

// 析构函数，释放内存
Stack::~Stack() {
    while (!IsEmpty()) { // 循环弹出栈中所有元素
        Pop();
    }
}

// 测试堆栈链式存储的实现
int main() {
    Stack s; // 创建堆栈对象

    // 入栈操作
    s.Push(1);
    s.Push(2);
    s.Push(3);

    // 获取栈顶元素
    cout << "Top element: " << s.Top() << endl;

    // 出栈操作
    cout << "Pop element: " << s.Pop() << endl;
    cout << "Pop element: " << s.Pop() << endl;

    // 获取栈顶元素
    cout << "Top element: " << s.Top() << endl;

    // 出栈操作
    cout << "Pop element: " << s.Pop() << endl;

    // 判断堆栈是否为空
    if (s.IsEmpty()) {
        cout << "Stack is empty!" << endl;
    } else {
        cout << "Stack is not empty!" << endl;
    }

    return 0;
}