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

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

引用

CSDN

1.

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

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

引言

上一篇我们已经学会了静态栈的基本操作<让你一次了解透彻栈-CSDN博客>相当于是顺序表的一种又一形式；那么栈有没有链表的又一形式呢？

接下来我们便学习链栈

链栈的定义

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

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

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

栈的基本操作

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

//定义链栈节点结构体
typedef struct Stack {
    int data;
    struct Stack *next;
} *LinkStack;  

1.初始化栈

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

//初始化栈
LinkStack InitLinkStack() {
    LinkStack L = (LinkStack) malloc(sizeof(LinkStack));
    if(L != 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;
    while (true) {
        printf("请输入链表中的元素：");
        scanf("%d", &val);
        if (val == -1) {
            break;
        }
        LinkStack p = (LinkStack) malloc(sizeof(LinkStack));
        if (p == NULL) {
            printf("申请失败！\n");     //新结点申请失败的情况
            return;
        } else {
            p->data = val;              //设置新结点的数据域
            p->next = top->next;        //设置新结点的指针城
            top->next = p;              //设置头结点指针城指向新的栈顶元素
        }
    }
}  

4.出栈操作

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

//出栈操作
void PopLinkStack(LinkStack top, int *x) {
    LinkStack node = (LinkStack) malloc(sizeof(LinkStack));
    if (top->next == NULL) {
        return;
    } else {
        node = top->next;           //将原栈顶数据元素弹出并赋给node
        *x = node->data;            //将原栈顶数据元素的数据赋值给x
        top->next = node->next;     //top指向链栈中的下一个数据元素
        free(node);         //释放原栈顶数据元素所占的空间
        return;
    }
}  

5.获取栈顶元素

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

//获取栈顶元素
void GetTop(LinkStack L, int *elem) {
    if (L->next == NULL) {
        return;
    } else {
        *elem = L->next->data;    //获取此时栈顶元素的数据域
        return;
    }
}  

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

//遍历栈且求栈长
void PrintLinkStack(LinkStack L) {
    LinkStack p = (LinkStack) malloc(sizeof(LinkStack));
    p = L->next;        //指向栈顶结点
    int count = 0;      //设置计数器，记录元素个数
    while (p != NULL) {
        printf("%d\n", p->data);
        p = p->next;
        count++;
    }
    printf("栈的长度为：%d\n", count);
}  

完整代码：

#include "stdbool.h"
#include "stdio.h"
#include "stdlib.h"
typedef struct Stack {
    int data;
    struct Stack *next;
} *LinkStack;
//初始化栈
LinkStack InitLinkStack() {
    LinkStack L = (LinkStack) malloc(sizeof(LinkStack));
    if (L != 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;
    while (true) {
        printf("请输入链表中的元素：");
        scanf("%d", &val);
        if (val == -1) {
            break;
        }
        LinkStack p = (LinkStack) malloc(sizeof(LinkStack));
        if (p == NULL) {
            printf("申请失败！\n");     //新结点申请失败的情况
            return;
        } else {
            p->data = val;              //设置新结点的数据域
            p->next = top->next;        //设置新结点的指针城
            top->next = p;              //设置头结点指针城指向新的栈顶元素
        }
    }
}
//出栈操作
void PopLinkStack(LinkStack top, int *x) {
    LinkStack node = (LinkStack) malloc(sizeof(LinkStack));
    if (top->next == NULL) {
        return;
    } else {
        node = top->next;           //将原栈顶数据元素弹出并赋给node
        *x = node->data;            //将原栈顶数据元素的数据赋值给x
        top->next = node->next;     //top指向链栈中的下一个数据元素
        free(node);         //释放原栈顶数据元素所占的空间
        return;
    }
}
//获取栈顶元素
void GetTop(LinkStack L, int *elem) {
    if (L->next == NULL) {
        return;
    } else {
        *elem = L->next->data;
        return;
    }
}
// 判断链栈是否为空
int isEmpty(LinkStack stack) {
    return stack->next == NULL;
}
//遍历栈且求栈长
void PrintLinkStack(LinkStack L) {
    LinkStack p = (LinkStack) malloc(sizeof(LinkStack));
    p = L->next;
    int count = 0;
    while (p != NULL) {
        printf("%d\n", p->data);
        p = p->next;
        count++;
    }
    printf("栈的长度为：%d\n", count);
}
int main() {
    LinkStack L;
    L = InitLinkStack();
    printf("当前栈为空?（True/False）：%s\n", EmptyLinkStack(L) ? "true" : "false");
    PushLinkStack(L);
    PrintLinkStack(L);
    int *x;
    GetTop(L, &x);
    printf("栈顶元素为%d\n", x);
    PopLinkStack(L, &x);
    printf("元素%d出栈\n", x);
    GetTop(L, &x);
    printf("栈顶元素为%d\n", x);
    PopLinkStack(L, &x);
    printf("元素%d出栈\n", x);
    printf("当前栈为空?（True/False）：%s\n", EmptyLinkStack(L) ? "true" : "false");
    PrintLinkStack(L);
    return 0;
}  

实现图片：

有了前面单链表的知识基础，相信现在链栈的学习一定非常简单！

如有疑问，欢迎在评论区留言讨论~