数据结构实现一个链栈及基本功能

链栈是一种基于链表实现的栈数据结构，它使用链表中的节点来存储和操作数据。下面是链栈的基本功能和实现方式。

1. 初始化链栈

链栈的初始化操作就是创建一个空链表。我们可以使用一个结构体来表示链表中的节点，节点包含两个部分：数据域和指针域。数据域用来存储元素的值，指针域用来指向下一个节点。

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

typedef struct LinkStack {
    Node *top;          // 栈顶指针
    int size;           // 栈中元素个数
} LinkStack;

// 初始化链栈
void initLinkStack(LinkStack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

2. 判断链栈是否为空

链栈为空的条件是栈顶指针为NULL，即链表中没有节点。

// 判断链栈是否为空
bool isLinkStackEmpty(LinkStack *stack) {
    return stack->top == NULL;
}

3. 入栈操作

链栈的入栈操作就是在链表的头部插入一个新的节点，同时更新栈顶指针和栈中元素个数。

// 入栈操作
void push(LinkStack *stack, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
}

4. 出栈操作

链栈的出栈操作就是删除链表头部的节点，并返回节点中的元素值。如果链表为空，则返回一个特定的错误码或抛出异常。

// 出栈操作
int pop(LinkStack *stack) {
    if (isLinkStackEmpty(stack)) {
        // 栈为空
        return -1;  // 或者通过抛出异常来处理
    }
    Node *p = stack->top;
    int value = p->data;
    stack->top = p->next;
    stack->size--;
    free(p);
    return value;
}

5. 获取栈顶元素

获取链栈的栈顶元素就是返回链表头部节点的元素值。如果链表为空，则返回一个特定的错误码或抛出异常。

// 获取栈顶元素
int getTop(LinkStack *stack) {
    if (isLinkStackEmpty(stack)) {
        // 栈为空
        return -1;  // 或者通过抛出异常来处理
    }
    return stack->top->data;
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

typedef struct LinkStack {
    Node *top;          // 栈顶指针
    int size;           // 栈中元素个数
} LinkStack;

// 初始化链栈
void initLinkStack(LinkStack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

// 判断链栈是否为空
bool isLinkStackEmpty(LinkStack *stack) {
    return stack->top == NULL;
}

// 入栈操作
void push(LinkStack *stack, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
}

// 出栈操作
int pop(LinkStack *stack) {
    if (isLinkStackEmpty(stack)) {
        // 栈为空
        return -1;  // 或者通过抛出异常来处理
    }
    Node *p = stack->top;
    int value = p->data;
    stack->top = p->next;
    stack->size--;
    free(p);
    return value;
}

// 获取栈顶元素
int getTop(LinkStack *stack) {
    if (isLinkStackEmpty(stack)) {
        // 栈为空
        return -1;  // 或者通过抛出异常来处理
    }
    return stack->top->data;
}

int main() {
    LinkStack stack;
    initLinkStack(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    printf("栈顶元素为：%d\n", getTop(&stack));
    printf("出栈元素为：%d\n", pop(&stack));
    printf("出栈元素为：%d\n", pop(&stack));
    printf("出栈元素为：%d\n", pop(&stack));
    printf("栈是否为空：%d\n", isLinkStackEmpty(&stack));
    return 0;
}