栈(链表)

1.一些铺垫

在上一节中的栈我们是使用数组实现的，但是相对而言有一些缺点，比如说数组的容量有限，不能做动态的处理，所以外面引入一种新的栈，用链表去写，可以解决容量的问题，但是链表的写法对于数组而言较为复杂，鱼和熊掌不可得兼

                    ┌─────────┐
                    │  top    │ ← stack.top 指针
                    ├─────────┤
                    │  size   │ ← stack.size 记录栈大小
                    └─────────┘
                         │
                         ▼
                    ┌─────────┐    ┌─────────┐    ┌─────────┐
             ─ ─ ▶ │  data   │───▶│  data   │───▶│  data   │───▶ NULL
                    ├─────────┤    ├─────────┤    ├─────────┤
                    │  next   │    │  next   │    │  next   │
                    └─────────┘    └─────────┘    └─────────┘
                         ▲
                         │
                    栈顶元素 (后进先出)

2.1 初始化

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

// 初始化链表
typedef struct node
{
    int data;          // 数据域
    struct node *next; // 指针域
} node;

//初始化栈
typedef struct stack
{
    node *top; // 栈顶指针
    int size;
} stack;

int main()
{
    stack stack;
    stack.top = NULL;// 初始化栈顶指针为NULL
    stack.size = 0;//  初始化栈大小为0

}

这里我们不仅定义了栈的结构体，也定义了链表的结构体方便后期链表入栈

2.2 入栈

//入栈
    node *p = (node *)malloc(sizeof(node));//申请一个链表的空间
    p ->data = 1;//数据域我们填1
    p ->next = stack.top;//指针域我们指向栈顶
    stack.top = p;//栈顶指针我们指向这个节点
    stack.size++;//栈大小加1
    printf("success!n");

对于入栈的代码中，在查资料的时候有个疑问： p ->next = stack.top; stack.top = p;这俩行为什么要怎么写
后期通过通义了解到第一行代码是为了保证链表的连续性，能够让新节点的指针域指向当前的栈顶
第二行是为了让栈顶指向现在的新节点
同时在学习时总结出一个结论：对于链表实现的栈而言，他们的指针域所指向的是出于他们正下方的节点
然后这里只入栈一个元素看不出来什么，所以我们这里多入几个来理解

//循环入栈5个元素
     for (int i = 0; i < 5; i++)
    {
        node *p = (node *)malloc(sizeof(node));
        p->data = i + 1;
        p->next = stack.top;
        stack.top = p;
        stack.size++;
        printf("%d success!n",i + 1);
    }

那么，现在我们的栈的示意图是

栈顶 (stack.top) →  ┌─────────┐
                    │   5     │ ← 最后入栈的元素 (i=4)
                    ├─────────┤
                    │  ─ ─ ─  │ ← next 指向下一个节点
                    ├─────────┤
                    │   4     │ ← 第4次入栈的元素 (i=3)
                    ├─────────┤
                    │  ─ ─ ─  │ ← next 指向下一个节点
                    ├─────────┤
                    │   3     │ ← 第3次入栈的元素 (i=2)
                    ├─────────┤
                    │  ─ ─ ─  │ ← next 指向下一个节点
                    ├─────────┤
                    │   2     │ ← 第2次入栈的元素 (i=1)
                    ├─────────┤
                    │  ─ ─ ─  │ ← next 指向下一个节点
                    ├─────────┤
                    │   1     │ ← 第1次入栈的元素 (i=0)
                    ├─────────┤
                    │  NULL   │ ← next 为 NULL (栈底)
                    └─────────┘

                    ↓
                 stack.size = 5

2.3 退栈

// 退栈
    // 判栈空
    if (stack.top == NULL)
    {
        printf("stack is empty!n");
    }
    else
    {
        node *temp = stack.top; // 保存栈顶节点
        int data = temp->data;  // 取出要退栈的数据值
        stack.top = temp->next; //把栈顶指针指向下一个元素
        stack.size--; //栈大小要减一
        free (temp);
        printf("seccess!n");
    }

注意： 一定要判断是否栈空！！！

2.4 获取栈顶元素以及遍历栈

1) 取栈顶

    if (stack.top == NULL)
    {
        printf("stack is empty!n");
    }
    else
    {
        printf("stack top is %dn", stack.top->data);
    }

2) 遍历栈

    // 遍历
    if (stack.top == NULL)
    {
        printf("stack is empty!n");
    }
    else
    {
        node *p = stack.top; // 定义一个便利的指针
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }

注意： 增删查改时务必判栈空，否则会报错
以上便是用链表模拟栈的一些基本写法，完整代码可以在同文件夹下的./stackDemo2.c中找到,博客的话会把代码附在评论区
感谢支持！