堆栈链式存储及实现

堆栈是一种后进先出（Last-In-First-Out，LIFO）的数据结构，可以使用链式存储实现。链式存储的堆栈由一个链表和一个指向链表顶部的指针组成。

链表节点（Node）通常包含两个成员：数据成员和指向下一个节点的指针成员。堆栈的顶部是链表的头部，堆栈的底部是链表的尾部。

以下是链式存储堆栈的实现过程：

1. 定义节点结构体

typedef struct Node {
    int data;           // 数据成员
    struct Node* next;  // 指向下一个节点的指针成员
} Node;

2. 定义堆栈结构体

typedef struct Stack {
    Node* top;  // 指向堆栈顶部节点的指针成员
    int size;   // 堆栈大小
} Stack;

3. 创建堆栈

Stack* createStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));  // 分配堆栈空间
    stack->top = NULL;  // 初始化堆栈顶部指针为空
    stack->size = 0;    // 初始化堆栈大小为0
    return stack;
}

4. 入栈操作

void push(Stack* stack, int data) {
    Node* node = (Node*)malloc(sizeof(Node));  // 分配节点空间
    node->data = data;  // 设置节点数据成员
    node->next = stack->top;  // 将节点插入堆栈顶部
    stack->top = node;  // 更新堆栈顶部指针
    stack->size++;  // 更新堆栈大小
}

5. 出栈操作

int pop(Stack* stack) {
    if (stack->top == NULL) {  // 如果堆栈为空，返回 0
        return 0;
    }
    Node* node = stack->top;  // 获取堆栈顶部节点
    int data = node->data;    // 获取节点数据成员
    stack->top = node->next;  // 更新堆栈顶部指针
    stack->size--;  // 更新堆栈大小
    free(node);     // 释放节点空间
    return data;
}

6. 获取堆栈顶部元素

int top(Stack* stack) {
    if (stack->top == NULL) {  // 如果堆栈为空，返回 0
        return 0;
    }
    return stack->top->data;  // 返回堆栈顶部节点数据成员
}

7. 判断堆栈是否为空

int isEmpty(Stack* stack) {
    return stack->top == NULL;  // 如果堆栈顶部指针为空，返回 1；否则返回 0
}

8. 获取堆栈大小

int size(Stack* stack) {
    return stack->size;  // 返回堆栈大小
}

9. 销毁堆栈

void destroyStack(Stack* stack) {
    while (stack->top != NULL) {  // 循环弹出堆栈元素
        pop(stack);
    }
    free(stack);  // 释放堆栈空间
}