数据结构专升本学习，栈篇（顺序栈）
前言：
上次我们学了，线性表里面的的链表，今天我们学栈，用官方的术语就是，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）也就是后进先出（LIFO）或者先进后出。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
每日一遍，快乐无极限，哈哈哈
1.什么是栈，理解逻辑
我们先学习一下栈的逻辑，在编程中逻辑是非常重要的东西，只要我们会了逻辑，然后会了语言，基本上是可以，用两个图来让大家理解一下栈的逻辑。
图一是一个逻辑图，很抽象，很好理解，记住后进先出或者，先进后出，是不是发现这两句话，倒时候会和队列搞反，所以，我们引用生活来记忆这个逻辑，看图二。
这个图是结合生活画的一个逻辑图，一个死胡同一个一个的进去，最后只能是后进的先出来，先进去的在最后出来，大家可以开动脑洞想一想，生活中还有那些这样的逻辑，可以方便我们记忆，博主想的有，手枪弹夹，我们以前用到老式手电筒的电池，还有我们小时候玩的压人，就几个小朋友，一个一个的往上压下面的那个小朋友，大家脑补一下那个画面，可以增强我们对栈的逻辑。????????????????
2.认识代码，认识我们的工具，大家敲起来
2.1 建立栈我们需要认识的代码，总结一下
大致流程图就是这样：
我们需要认识一些代码及含义
1.#define DataType int //把int类型自定义一下
2.#define MAXSIZE 10 //MAXSIZE代表最大的栈空间
3.typedef struct{
DataType data[MAXSIZE];
int top; //这个就是栈顶，因为我们是顺序栈所以没用指针
}SeqStack;//这个是顺序表栈的一个类型
4.(SeqStack*)malloc(sizeof(SeqStack));这个在链表中用过，划分内存空间
5.SeqStack* s; 定义一个栈
6.int Push_SeqStack(SeqStack* s, DataType x) //入栈操作，s代表栈，x代表我们入栈的值
7.int Pop_SeqStack(SeqStack* s, DataType* x){ //出栈操作，s代表栈，指针x代表输出的值，博主用的指针，实参为地址复制代码2.2 初始化顺序栈
初始化顺序栈，就是把栈生成 ，划分内存空间，然后在那个数组里面存值，讲人话就是：（一个结构体指针指向一个结构体，而这个结构体里面有一个数组和一个整形变量，就是数组的下标，然后每次存值那个整形变量自增，出栈就是整形变量自减）
typedef struct{
DataType data[MAXSIZE];
int top;
}SeqStack;
SeqStack* Init_SeqStack(){ //栈初始化
SeqStack* s;
s = (SeqStack*)malloc(sizeof(SeqStack)); //划分内存空间
if(!s){//判断内存空间的划分是否成功
printf("空间不足\n");
return NULL;
}else{
s->top = -1;//栈空以-1标记
return s; //返回栈
}
}
int Empty_SeqStack(SeqStack* s){ //判断栈空
if(s->top == -1)//我们初始化的时候定义了栈空为-1标记，所以以-1结束
return 1;
else
return 0;
}复制代码2.3 入栈和出栈操作
int Push_SeqStack(SeqStack* s, DataType x){ //入栈操作，s代表栈，x代表我们入栈的值
if(s->top == MAXSIZE - 1)//如果我们栈满了入栈就会失败，为什么要减一是因为栈是0位置开始，出栈到-1结束
return 0;//栈满不能入栈
else{
s->top++; //我们入栈栈顶要加一
s->data[s->top] = x; //将我们的值入栈
return 1;//成功
}
}
int Pop_SeqStack(SeqStack* s, DataType* x){ //出栈操作，s代表栈，指针x代表输出的值，博主用的指针，实参为地址
if(Empty_SeqStack(s))//判断是不是空栈
return 0;//栈空不能出栈
else{
*x = s->data[s->top]; //把栈顶的值赋值给指针x,代表出栈了
s->top--; //出栈之后我们要栈顶减一
return 1;
}//栈顶元素存入*x，返回
}复制代码2.4 效果演示，和整体代码
顺序栈效果就是上面这样，整体代码我放到下面，大家可以跑一下
#include <stdio.h>
#include <malloc.h>
#define DataType int
#define MAXSIZE 10
typedef struct{
DataType data[MAXSIZE];
int top;
}SeqStack;
SeqStack* Init_SeqStack(){ //栈初始化
SeqStack* s;
s = (SeqStack*)malloc(sizeof(SeqStack));
if(!s){
printf("空间不足\n");
return NULL;
}else{
s->top = -1;
return s;
}
}
int Empty_SeqStack(SeqStack* s){ //判栈空
if(s->top == -1)
return 1;
else
return 0;
}
int Push_SeqStack(SeqStack* s, DataType x){ //入栈
if(s->top == MAXSIZE - 1)
return 0;//栈满不能入栈
else{
s->top++;
s->data[s->top] = x;
return 1;
}
}
int Pop_SeqStack(SeqStack* s, DataType* x){ //出栈
if(Empty_SeqStack(s))
return 0;//栈空不能出栈
else{
*x = s->data[s->top];
s->top--;
return 1;
}//栈顶元素存入*x，返回
}
int Print_SeqStack(SeqStack* s){
int i;
printf("当前栈中的元素:\n");
for(i = s->top; i >= 0; i--)
printf("%3d", s->data[i]);
printf("\n");
return 0;
}
int main(){
SeqStack* L;//定义结构体指针
int n, num, m;
int i;
L = Init_SeqStack(); //初始化栈
printf("初始化完成\n");
printf("栈空：%d\n", Empty_SeqStack(L));
printf("请输入入栈元素个数(不得超过 %d 个)：\n",MAXSIZE);//最大入栈的个数为MAXSIZE
scanf("%d", &n);//输入我们入栈的个数
printf("请输入要入栈的%d个元素：\n", n);
for(i = 0; i < n; i++){
scanf("%d", &num);//循环调用，赋值我们要入栈的元素
Push_SeqStack(L, num);
}
Print_SeqStack(L);//这个函数是如果之前栈中有的值输出一次
printf("请输入要出栈的元素个数（不能超过%d个）：\n", n);
scanf("%d", &n);//我们需要输出的元素个数
printf("依次出栈的%d个元素：\n", n);
for(i = 0; i < n; i++){
Pop_SeqStack(L, &m);//这个函数是出栈，m实参传地址过去，对应的形参是整形指针变量
printf("%3d", m);//输出m
}
printf("\n");
return 0;
}复制代码总结：
顺序栈是比较简单的，我们可以简单的理解为一个带有下标的一维数组，并且这个下标不能随意跳转一直在最后的位置，进栈这个下标就自增，出栈就自减，栈是一个很好数据结构，它在算法中也运用的很多。例如经典的汉诺塔问题就可以用栈解决，在递归中也用的比较多，大致博主的理解就是这样，如果有错误的地方，希望大家及时指教，我们下一篇讲链式栈，创作不易希望大家，点赞，关注，评论。
作者：IC00
链接：https://juejin.cn/post/7025529549131612168