链表掌握了，那链栈你拿捏了吗？【数据结构】

链表掌握了，那链栈你拿捏了吗？【数据结构】

引用

CSDN

1.

https://blog.csdn.net/Wanghh520max/article/details/137412469

链栈是使用链表实现的栈结构，每个节点包含数据元素和指向下一个节点的指针。链栈的优点是不会出现栈满的情况，可以动态调整大小，但相比顺序栈，链栈的操作会稍微复杂一些。

链栈的定义

链栈是使用链表来实现的栈结构，每个节点包含数据元素和指向下一个节点的指针。链栈的优点是不会出现栈满的情况，可以动态调整大小，但相比顺序栈，链栈的操作会稍微复杂一些。

在操作角度上，链栈就是进行头插法创建的单链表，只不过不能在中间位置进行元素的增加和删除，只能在栈顶处进行操作。

创建链栈就是在头结点后将新元素压入栈内，可以类别单链表进行学习。

栈的基本操作

链栈的操作主要包括初始化栈、进栈、出栈、获取栈顶元素、判断栈空等。

1. 初始化栈

链栈初始化即先构造一个空栈，将栈顶指针top所指的头结点的指针域置空。

LinkStack InitLinkStack() {
    LinkStack L = (LinkStack) malloc(sizeof(LinkStack));
    if (L == NULL) {
        printf("申请失败！\n");
        return NULL;
    }
    L->next = NULL;
    return L;
}

2. 判断栈空

如果栈顶指针指向NULL则返回True，否则返回false。

bool EmptyLinkStack(LinkStack L) {
    if (L->next == NULL) //检查栈顶指针的值
        return true; //栈L为空，函数返回true
    else
        return false;
}

3. 入栈操作

将数据元素val插入链栈的栈顶，将头结点的指针域指向新插入的栈顶元素。

当输入的val为-1时则表示输入结束。

void PushLinkStack(LinkStack top, int val) {
    LinkStack p = (LinkStack) malloc(sizeof(LinkStack));
    if (p == NULL) {
        printf("申请失败！\n"); //新结点申请失败的情况
        return;
    }
    p->data = val; //设置新结点的数据域
    p->next = top->next; //设置新结点的指针域
    top->next = p; //设置头结点指针域指向新的栈顶元素
}

4. 出栈操作

删除栈顶数据元素，通过X返回删除数据的值，然后top指针指向下一个数据元素。

void PopLinkStack(LinkStack top, int *x) {
    LinkStack node = top->next;
    if (node == NULL) {
        printf("栈为空，无法出栈！\n");
        return;
    }
    *x = node->data; //将原栈顶数据元素的数据赋值给x
    top->next = node->next; //top指向链栈中的下一个数据元素
    free(node); //释放原栈顶数据元素所占的空间
}

5. 获取栈顶元素

读取栈顶元素，并且返回该值。

void GetTop(LinkStack L, int *elem) {
    if (L->next == NULL) {
        printf("栈为空，无法获取栈顶元素！\n");
        return;
    }
    *elem = L->next->data; //获取此时栈顶元素的数据域
}

6. 遍历链栈并且求链栈长

void PrintLinkStack(LinkStack L) {
    LinkStack p = L->next;
    int count = 0; //设置计数器，记录元素个数
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
        count++;
    }
    printf("\n栈的长度为：%d\n", count);
    printf("当前栈为空?（True/False）：%s\n", EmptyLinkStack(L) ? "true" : "false");
}

完整代码

typedef struct LinkStackNode {
    int data;
    struct LinkStackNode *next;
} LinkStackNode, *LinkStack;

LinkStack InitLinkStack() {
    LinkStack L = (LinkStack) malloc(sizeof(LinkStackNode));
    if (L == NULL) {
        printf("申请失败！\n");
        return NULL;
    }
    L->next = NULL;
    return L;
}

bool EmptyLinkStack(LinkStack L) {
    if (L->next == NULL) //检查栈顶指针的值
        return true; //栈L为空，函数返回true
    else
        return false;
}

void PushLinkStack(LinkStack top, int val) {
    LinkStack p = (LinkStack) malloc(sizeof(LinkStackNode));
    if (p == NULL) {
        printf("申请失败！\n"); //新结点申请失败的情况
        return;
    }
    p->data = val; //设置新结点的数据域
    p->next = top->next; //设置新结点的指针域
    top->next = p; //设置头结点指针域指向新的栈顶元素
}

void PopLinkStack(LinkStack top, int *x) {
    LinkStack node = top->next;
    if (node == NULL) {
        printf("栈为空，无法出栈！\n");
        return;
    }
    *x = node->data; //将原栈顶数据元素的数据赋值给x
    top->next = node->next; //top指向链栈中的下一个数据元素
    free(node); //释放原栈顶数据元素所占的空间
}

void GetTop(LinkStack L, int *elem) {
    if (L->next == NULL) {
        printf("栈为空，无法获取栈顶元素！\n");
        return;
    }
    *elem = L->next->data; //获取此时栈顶元素的数据域
}

int isEmpty(LinkStack stack) {
    return stack->next == NULL;
}

void PrintLinkStack(LinkStack L) {
    LinkStack p = L->next;
    int count = 0; //设置计数器，记录元素个数
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
        count++;
    }
    printf("\n栈的长度为：%d\n", count);
    printf("当前栈为空?（True/False）：%s\n", EmptyLinkStack(L) ? "true" : "false");
}

有了前面单链表的知识基础，相信现在链栈的学习一定非常简单！如果有任何问题欢迎留言~