前言：
上次我们学了，线性表里面的的链表，今天我们学栈，用官方的术语就是，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）也就是后进先出（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;}
复制代码
总结：
顺序栈是比较简单的，我们可以简单的理解为一个带有下标的一维数组，并且这个下标不能随意跳转一直在最后的位置，进栈这个下标就自增，出栈就自减，栈是一个很好数据结构，它在算法中也运用的很多。例如经典的汉诺塔问题就可以用栈解决，在递归中也用的比较多，大致博主的理解就是这样，如果有错误的地方，希望大家及时指教，我们下一篇讲链式栈，创作不易希望大家，点赞，关注，评论。
上一篇： 数据结构专升本学习笔记，线性表链表(内卷篇)</br>下一篇： # 数据结构专升本学习，栈篇（链式栈)
评论