📭今天我们讲数据结构里面的栈，有了顺序表的基础后学习栈那真是唰唰唰的瞬间理解这些东西，非常的easy~~

1：栈的基本概念和结构

栈的概念📝

 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，（入数据在栈顶）

出栈：栈的删除操作叫做出栈。（出数据也在栈顶）

栈的结构📝

 🤔函数的调用需要开辟栈，这两个栈是一回事吗？

函数调用开辟的栈是从内存中申请一块空间，属于虚拟进程地址空间，当程序运行起来执行函数时，函数栈帧用来存放局部变量、参数、返回值等等。和数据结构中的栈没有关联。这两个一个是数据结构中的栈，是一个数据结构。另一个是操作系统中内存划分的一个区域，叫做栈，用来函数调用时建立栈帧。

 下面我们进入第二阶段

 2：栈的实现

🖊：栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入删除数据的代价比较小。

  

 2-1：创建栈

Stack.h文件

//创建栈typedef int STDataType;typedef struct Stack{STDataType* a; //存储数据int top;//记录栈顶的位置int capacity;  //记录栈的容量}ST;

  2-2：初始化栈

思路：

初始化栈和顺序表的初始化大致相同。

Stack.h文件

//初始化栈void StackInit(ST* ps);

Stack.c文件

//初始化栈void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}

2-3：销毁栈 

思路：

销毁栈和顺序表的销毁也大致一样，将开辟的数组空间free掉，把其余数据置为0.

Stack.h文件

//销毁栈void StackDestory(ST* ps);

Stack.c文件

//销毁栈void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}

 2-4：压栈 

思路：

在我们要插入数据前，我们要判断栈的空间是否够用，如果top=capacity，则栈的空间已满，需要扩容，如果未满我们就压入数据，top++

 Stack.h文件

//压栈(栈规定数据只能在栈顶插入，所以只有一种插入方式)void StackPush(ST* ps, STDataType x);

Stack.c文件

//压栈(栈规定数据只能在栈顶插入，所以只有一种插入方式)void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity; //扩容}ps->a[ps->top] = x; //数据压栈(ps->top)++; //栈顶更新}

 2-5：出栈 

思路：

如果想要出栈，至少要保证栈中有元素，也就是pos->top>0,判断完如果符合条件，则和顺序表删除元素一样，将栈顶位置下移一位。

Stack.h文件

//出栈void StackPop(ST* ps);

Stack.c文件

//出栈void StackPop(ST* ps){assert(ps);assert(ps->top > 0);//如果要出栈，至少要保证栈中有元素(ps->top)--;}

 2-6：判断栈是否为空

思路：

判断栈是否为空只需判断top的值是否为0即可。

Stack.h文件

//判断栈中的数据是否为空bool StackEmpty(ST* ps);

Stack.c文件

//判断栈中的数据是否为空bool StackEmpty(ST* ps){/*法一assert(ps);if (ps->top > 0){return false;}else{return true;}*///法二return ps->top == 0;}

 2-7：访问栈顶元素

思路：

通过上文我们初始化top为0知道，当我们压栈时，是先把数据放进去然后top++；很明显栈顶的元素下标为top-1，所以我们访问栈顶元素就是访问数组所对应下标为top-1的元素。

Stack.h文件

//访问栈顶元素STDataType StackTop(ST* ps);

Stack.c文件

//访问栈顶元素STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}

 2-8：获取栈中有效元素个数

思路：

数组下标是从0开始的，我们要获取栈中有效元素个数即为top的值，所以我们直接返回top即可。

Stack.h文件

//获取栈中有效元素个数int StackSize(ST* ps);

Stack.c文件

//获取栈中有效元素个数int StackSize(ST* ps){assert(ps);return ps->top;}

  2-9：遍历打印栈

思路：

要遍历打印栈是要付出代价的，因为栈中的元素遵循后进先出，所以当栈不为空时打印栈顶元素，要访问下一个元素就把原先的栈顶元素删除，然后再次访问栈顶，直到栈中的元素为空。

Test.c文件

void TestStack(){ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n");StackDestory(&st);}int main(){TestStack();return 0;}

🚀 看了上面栈的实现是不是觉得很easy~~

 3：总代码

Stack.h文件

#pragma once#include #include #include #include //创建栈typedef int STDataType;typedef struct Stack{STDataType* a; //存储数据int top;//记录栈顶的位置int capacity;  //记录栈的容量}ST;//初始化栈void StackInit(ST* ps);//销毁栈void StackDestory(ST* ps);//压栈(栈规定只能在栈顶插入，所以只有一种插入方式)void StackPush(ST* ps, STDataType x);//出栈void StackPop(ST* ps);//判断栈中的数据是否为空bool StackEmpty(ST* ps);//访问栈顶元素STDataType StackTop(ST* ps);//获取栈中有效元素个数int StackSize(ST* ps);

Stack.c文件

#include "Stack.h"//初始化栈void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;}//销毁栈void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}//压栈(栈规定数据只能在栈顶插入，所以只有一种插入方式)void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newCapacity; //扩容}ps->a[ps->top] = x; //数据压栈(ps->top)++; //栈顶更新}//出栈void StackPop(ST* ps){assert(ps);assert(ps->top > 0);//如果要出栈，至少要保证栈中有元素(ps->top)--;}//判断栈中的数据是否为空bool StackEmpty(ST* ps){/*法一assert(ps);if (ps->top > 0){return false;}else{return true;}*///法二return ps->top == 0;}//访问栈顶元素STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}//获取栈中有效元素个数int StackSize(ST* ps){assert(ps);return ps->top;}

Test.c文件

#include "Stack.h"void TestStack(){ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n");StackDestory(&st);}int main(){TestStack();return 0;}

栈的讲解就到这里了，大家觉得有收获的话记得点个赞噢~ 💙💜🧡