引入
我们之前,讲解了栈的顺序存储结构,那么既然是线性表,如何用链式存储结构来使用栈呢?链式存储和顺序存储在栈中又会有什么不一样呢?我们一起来看一下~
想一想
我们在开始之前先想一想,栈和链式存储结构的特点
链式存储结构
- 有头部
- 根据头部存储的指针信息,一环扣一环
顺序存储结构的栈
- 后进先出
- 插入和删除只能在顶端进行
链式存储结构的栈呢
- 有头部
- 每个结点存储着指针信息,一环扣一环
- 后进先出
- 插入和删除只能再顶端进行
初始化链式存储结构的栈
根据上面的想一想,我们大概就能知道,要解决这样一个链式存储结构的栈,最简单的方法可能就是,栈顶放在单链表的头部,将栈顶指针跟单链表的头指针合二为一。
初始化代码
1 |
|
注意
- 单链表栈的初始化,需要两个结构体,一个存数据,一个存头部
- 数据的里面主要是
数据域
和指针域
- 头部的里面主要是
首结点地址
和结点计数器
- 初始化的时候,不需要操作结点,只需要初始化头部即可
- 头部默认指向 NULL
- 计数默认为 0
Push 压栈
1 | void push(struct StackTop *tp , int data){ |
注意
- 压栈的时候,先创建结点内存地址
- 然后把数据先存进去
- 接着把新节点的下一个改成 top 指向的结点,也就是原来的第一个结点
- 然后把 top 存储的第一个结点,改成新节点
- 记得把计数器加 1
Pop 出栈
1 | void pop(struct StackTop *tp){ |
注意
- 出栈要记得先把计数器-1
- 输出的值不是 top,而是 top 指向的结点的 data
- 把 top 已经输出的结点地址存下来,结束后释放
- 然后把 top 指向输出结点的下一个结点
完整代码
1 |
|
输出结果
1
2
3
4
5
输入的是5 4 3 2 1,输出是 1 2 3 4 5 ,后进先出,证明栈没有问题。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。