我要评论前言
hello，小伙伴们，今天我们继续数据结构的学习，前面我们学习了顺序表和链表的实现，今天的栈知识也是和前面的知识相辅相成。
如果你喜欢我的内容的话，就请不要吝啬自己手中的三连哟，万分感谢！！好，废话不多说，开始我们今天的正题。
1.栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和数据删除的一端，我们称之为栈顶，另一端我们称之为栈底。栈中的数据元素遵守后进先出的原则（last in first out)
栈的底层结构选型：
栈的实现一般可以使用数组或者链表，相对而言数组的结构要更加的简洁。因为数组在尾上插入数据的代价比较小。
2.栈的实现
更前几期的数据结构实现一样，我们还是先在vs2022上创建三个文件：
2.1 栈的定义：
前面我们说到，栈的底层结构我们采用数组的方式是最好的，所以我们可以怎样来定义栈呢？
诶，我们是不是可以想到我们之前学习过的顺序表呢，他们们的底层逻辑都可以通过数组来实现，整体功能大同小异。
那我们就来试试这样定义栈的结构：
typedef int sdatatype;
typedef struct stack
{
sdatatype* arr;
int capacity;
int top;
}stack;
而在实现栈的功能时我们只要注意，栈的数据插入和数据删除都只是在一端进行就好了！！
2.2 栈的初始化
初始化栈，我们应当怎么来做呢？
我们先来看实现该功能的函数：
2.2.1 void initstack(stack* ps)函数的定义和实现
/首先实现栈的初始化
void initstack(stack* ps);看到这这里有没有人觉得很熟悉呢？
对，其实这里的初始化就是和顺序表的初始化一样的所以开始的时候，我们需要
函数我们就可以这样实现：
//首先实现栈的初始化
void initstack(stack* ps)
{
assert(ps);
ps->arr = null;
ps->capacity = ps->top = 0;
}2.2.2 函数功能测试
2.3压栈的实现
2.3.1 void stackpush(stack* ps, sdatatype x)的定义和实现
其实，压栈的函数和前面我们遇到的顺序表和链表的实现大致相同：
我们先来看压栈函数的定义：
//实现入栈操作
void stackpush(stack* ps, sdatatype x);再来看看函数的实现逻辑：
在这里我们还是要注意，插入数据的前提就是必须要有足够的空间来存储数据。
所以我们还是要用到checkcapacity函数来检查存储空间
还不了解这个函数的同学，可以看看我往期的文章中关于顺序表的尾插，里面对该函数有介绍：
文章链接为：http://t.csdnimg.cn/shzpc
void checkcapacity(stack* ps)
{
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
sdatatype* newstack = (sdatatype*)realloc(ps->arr, newcapacity * sizeof(sdatatype));
if (newstack == null)
{
perror("checkcapacity, realloc:");
exit(1);
}
ps->arr = newstack;
ps->capacity = newcapacity;
}
}
//实现入栈操作
void stackpush(stack* ps, sdatatype x)
{
assert(ps);
checkcapacity(ps);
ps->arr[ps->top++] = x;//ps->表示栈中有效数据的个数，每插入数据一次，ps->top就+1
}2.3.2压栈函数的测试：
2.4 出栈函数的实现
2.4.1 void stackpop(stack* ps)函数的定义和实现
//出栈函数的实现
void stackpop(stack* ps);实现出栈函数其实就和顺序表元素的尾删相似：
在这里我们需要注意尾删的前提就是必须要有数据可删
bool isempty(stack *ps)
{
return ps->top == 0;
}
//出栈操作只能在栈顶进行
void stackpop(stack* ps)
{
assert(ps);
assert(!isempty(ps));
ps->top--;
} 
出栈，就是将当前的栈顶元素排除在有效的数据范围之外，使栈不再包含该数据，在后面插入数据时，新的数据会直接将原来的数据覆盖，不会对栈产生什么影响。
2.4.2 出栈函数的测试：
2.5获取栈顶元素
2.5.1 gettop(satck* ps)函数的定义和实现
定义：
sdatatype gettop(stack *ps);实现：
sdatatype gettop(stack* ps)
{
assert(ps && !isempty(ps));
return ps->arr[ps->top - 1];
}得到栈顶元素十分的简单，这里实现他，是为下面一个能够展示栈的重要特性的函数的实现做好铺垫！！
2.5.2 获取栈顶元素测试：
2.6 展示栈中的元素
2.6.1 stackshow 函数的定义和实现
定义：
void stackshow(stack* ps);实现：
注意：根据栈的特性，栈中的数据不能被遍历也不能被随机访问，只能从栈顶依次取出。
void stackshow(stack* ps)
{
assert(ps);
//所以在ps->不为null的前提下，依次出栈，使所有的数据都有机会成为栈顶元素，这样才能被取出
//这是栈结构的特性！！！
while (!isempty(ps))
{
sdatatype data = gettop(ps);
printf("%d ", data);
stackpop(ps);
}
}因此，一个栈的数据只能展示一次，之后，栈中的数据全部出栈，失去了访问权限！！
2.6.2 栈元素展示测试：
接下来我们来实现最后一个栈函数。
2.7 获取栈中元素的个数
这个函数的实现十分的简单，因为栈中的元素个数就是ps->top
定义：
sdatatype stackcount(stack* ps);实现：
sdatatype stackcount(stack* ps)
{
assert(ps);
return ps->top;
}2.7.1 stackcount 函数的测试
到这里，栈的结构就是实现完了，虽然栈相比于前的链表和顺序表要简单，但他在数据结构中的地十分的重要，在后面的学习中，我们经常会使用栈来解决问题，所以大家一定要认真地理解栈！！
结语
今天关于栈的学习就到这里，如果你喜欢我的内容就请不要吝啬自己的三连哟！！
咱们下期再见！！！
发表评论