阅读量:2
| 初阶数据结构 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 时间与空间复杂度的深度剖析 | 深入解析顺序表:探索底层逻辑 | 深入解析单链表:探索底层逻辑 | 深入解析带头双向循环链表:探索底层逻辑 | 深入解析栈:探索底层逻辑 |
| 深入解析队列:探索底层逻辑 | 深入解析循环队列:探索底层逻辑 |
🔥引言
本篇将深入解析栈:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。
🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
一、栈的概念及结构
栈是指一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
这里主要分享的是跟数据结构相关的栈，而不是指存储内存一块内存区域栈区，栈区是指CPU寄存器里的某个指针所指向的一片内存区域(存放函数的参数值，局部变量的值等)
其中有两个核心操作压栈和出栈(出入数据在栈顶实现）
压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
由于栈的特殊结构特性，所以出栈有多种方式，而入栈只有一种
2.一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ） A.ABCDE B.EDCBA C.DCEBA D.ECDBA 答案:D 二、关于实现栈的分析
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。在顺序表章节，说明了静态顺序表的实用价值不大，通常是使用动态，这里实现栈的也是是实现动态栈
三、实现栈的相关接口(Satck.h)
3.1 关于top的定义
在实现之前，对top需要有一个定义。当对栈顶元素修改的时候，top作为一个下标。既然top是一个下标，**那么top为0是代表栈为空还是栈存储一个元素，这个是需要我们去定义的(**在顺序表中，也是需要定义的)。所以栈有两种关于栈顶的定义。
top为-1代表空，top为0代表一个元素
top为0代表空，top指向下一个元素下标
其实上面的两种方式都可以的，在插入过程顺序会出现差异
下列的实现都是采用第二种top为0代表空，top指向下一个元素下标
3.2 栈的初始化
void STInit(ST *pst) { assert(pst);//指向一个有效的结构体 pst->a = NULL; pst->top =pst->capacity= 0; } 3.3 入栈操作
void STPush(ST* pst, StackDataType x) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; StackDataType *tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType)*newcapacity); if (tmp==NULL) { perror("realloc fail!!!"); return 1; } pst->capacity = newcapacity; pst->a = tmp;//保证安全返回 } pst->a[pst->top] = x;//插入 pst->top++;//注意top的意义--之后里面为1没有给数值 } 这里需要注意的是:这里插入就是相当于顺序表的尾插，只有栈顶进行插入，所以没有必要单独实现扩容接口，直接在插入时需要空间进行扩容操作
3.4 出栈操作
void STPop(ST* pst)//跳出 { assert(pst); assert(pst->top > 0);//top为0，则是为空 pst->top--;//元素个数-- } 这里需要注意的是:相当于顺序表的尾删，同时要满足保证有数据给你删除
3.5 得到栈顶元素
StackDataType STTOP(ST* pst)//得到栈顶元素 { assert(pst); return pst->a[pst->top-1];//这里减的话就会有问题 } 这里需要注意的是:这里top是指向下一个元素的下标，需要-1到达栈顶元素下标
3.6 得到栈里面元素个数
int STSize(ST* pst) { return pst->top;//个数 } 3.7 判断栈是否为空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0;//为0就是空,为真 } 3.8 栈的打印
void STPrintf(ST* pst) { while(!STEmpty(pst)) { printf("%d", STTOP(pst)); STPop(pst); printf("\n"); } } 这里需要注意的是:打印是打印栈顶元素，为了下次打印，需要出栈得到新栈顶元素。当栈里面没有数据时，就不要再打印数据，没有数据打印。
3.9 栈的销毁
void STDestroy(ST* pst)//销毁 { assert(pst); free(pst->a); pst->a = NULL; pst->top =pst->capacity = 0; } 
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！
