引入

我们之前，讲解了栈的顺序存储结构，那么既然是线性表，如何用链式存储结构来使用栈呢？链式存储和顺序存储在栈中又会有什么不一样呢？我们一起来看一下~

想一想

我们在开始之前先想一想，栈和链式存储结构的特点
链式存储结构

  • 有头部
  • 根据头部存储的指针信息，一环扣一环

顺序存储结构的栈

  • 后进先出
  • 插入和删除只能在顶端进行

链式存储结构的栈呢

  • 有头部
  • 每个结点存储着指针信息，一环扣一环
  • 后进先出
  • 插入和删除只能再顶端进行

初始化链式存储结构的栈

根据上面的想一想，我们大概就能知道，要解决这样一个链式存储结构的栈，最简单的方法可能就是，栈顶放在单链表的头部，将栈顶指针跟单链表的头指针合二为一。

初始化代码

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Stack)
#define TLEN sizeof(struct StackTop)

struct Stack{
    int data;
    struct Stack *next;
};

struct StackTop{
    struct Stack *top;
    int count;
};

struct StackTop *init(void){
    struct StackTop *tp;
    tp=(struct StackTop *)malloc(TLEN);
    tp->top=NULL;
    tp->count=0;
    return tp;
}

注意

  • 单链表栈的初始化，需要两个结构体，一个存数据，一个存头部
  • 数据的里面主要是数据域和指针域
  • 头部的里面主要是首结点地址和结点计数器
  • 初始化的时候，不需要操作结点，只需要初始化头部即可
  • 头部默认指向 NULL
  • 计数默认为 0

Push 压栈

void push(struct StackTop *tp , int data){
    struct Stack *p=(struct Stack *)malloc(LEN);
    p->data=data;
    p->next=tp->top;
    tp->top=p;
    tp->count++;
}

注意

  • 压栈的时候，先创建结点内存地址
  • 然后把数据先存进去
  • 接着把新节点的下一个改成 top 指向的结点，也就是原来的第一个结点
  • 然后把 top 存储的第一个结点，改成新节点
  • 记得把计数器加 1

Pop 出栈

void pop(struct StackTop *tp){
struct Stack *p;
    while(tp->top!=NULL){
        tp->count--;
        printf("%d\n",tp->top->data);
        p=tp->top;
        free(p);
        tp->top=tp->top->next;
    }
}

注意

  • 出栈要记得先把计数器-1
  • 输出的值不是 top，而是 top 指向的结点的 data
  • 把 top 已经输出的结点地址存下来，结束后释放
  • 然后把 top 指向输出结点的下一个结点

完整代码

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Stack)
#define TLEN sizeof(struct StackTop)

struct Stack{
    int data;
    struct Stack *next;
};

struct StackTop{
    struct Stack *top;
    int count;
};

struct StackTop *init(void){
    struct StackTop *tp;
    tp=(struct StackTop *)malloc(TLEN);
    tp->top=NULL;
    tp->count=0;
    return tp;
}

void push(struct StackTop *tp , int data){
    struct Stack *p=(struct Stack *)malloc(LEN);
    p->data=data;
    p->next=tp->top;
    tp->top=p;
    tp->count++;
}

void pop(struct StackTop *tp){
    struct Stack *p;
    while(tp->top!=NULL){
        tp->count--;
        printf("%d\n",tp->top->data);
        p=tp->top;
        free(p);
        tp->top=tp->top->next;
    }
}

int main(){
    struct StackTop *tp;
    tp=init();
    push(tp,5);
    push(tp,4);
    push(tp,3);
    push(tp,2);
    push(tp,1);
    pop(tp);
    return 0;
}

输出结果
1
2
3
4
5

输入的是5 4 3 2 1，输出是 1 2 3 4 5 ，后进先出，证明栈没有问题。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。