【初阶数据结构】深入解析栈:探索底层逻辑
🔥引言
本篇将深入解析栈:探索底层逻辑，理解底层是如何实现并了解该接口实现的优缺点，以便于我们在编写程序灵活地使用该数据结构。
🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
- 一、栈的概念及结构
- 二、关于实现栈的分析
- 三、实现栈的相关接口(Satck.h)
- 3.1 关于top的定义
- 3.2 栈的初始化
- 3.3 入栈操作
- 3.4 出栈操作
- 3.5 得到栈顶元素
- 3.6 得到栈里面元素个数
- 3.7 判断栈是否为空
- 3.8 栈的打印
- 3.9 栈的销毁
一、栈的概念及结构
栈是指一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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;
}
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！