😏专栏导读
👻作者简介：M malloc，致力于成为嵌入式大牛的男人
👻专栏简介：本文收录于 初阶数据结构，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。
👻相关专栏推荐：LeetCode刷题集，C语言每日一题。
🤖文章导读
本章我将详细的讲解关于栈的知识点
🙀什么是栈？
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
栈的两种概念：
1、压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
2、出栈：栈的删除操作叫做出栈。出数据也在栈顶
🙀画图描述
如下图所示，就是出栈入栈全过程啦！关于栈有一个特点就是后进先出不要忘记啦！
😳栈的代码实现及其各类讲解
😳栈的初始化代码实现及其讲解
首先我们要清晰栈是如何实现的
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
所以这里我们选择用数组来实现顺序栈！
如图所示：假设用数组实现的话，就像有限制条件的顺序表，尾插就相对的方便一些。
如果用链式栈实现的话，就相对的消耗会更大一些
😳栈的初始化
这里我们采用的是动态开辟版的顺序栈，所以首先我们先定义一个结构体类型
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST;
这是类型的定义。
初始化函数代码如下：
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; }
那么我们为什么要这样初始化呢？为什么我们的top初始化要赋值为0呢？这里就是方便于我们正常的理解啦，因为正常的来说，我们数组的下标一般都是从0开始的！但是如果这样考虑的话，
我们就应该清楚top所处于的位置了，当a1插入数据时，我们的top就应该是在下一个位置了，而不是相对应的位置。
😳栈的销毁代码实现及其讲解
代码如下：
void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; }
由于我们用的是顺序栈，它是一块连续的地址，所以我们只需要free掉首结点，它那一块连续的空间都会被销毁，并且我们再把对应的容量和栈顶指向的位置都归回原位就行啦！
😳栈的入栈代码的实现及其讲解
栈的入栈实现其实是有限制条件的，就是要从栈顶入数据，然后还从栈顶出数据，其实就是根据我们的top位置去插入元素，下面我们进入画图讲解！
最初的栈是空的图：
然后我们开始入栈元素，此时的元素是从栈顶开始入栈，此时的数据已经入进去了，我们发现此时的top也向前移动了一个位置，此时也就是当数据成功入栈时，我们的top会自动的进行++
下面是代码实现
在实现代码的过程中，我们发现有一个if然后一大串的看不懂的一堆代码对不对。
这一段的代码主要的作用就是当我们的入栈满了的时候，我们可以进行动态扩容，那么这个realloc的作用是啥呢？我们可以登录cplusplus查看一下，网址时这个噢！这就是cplusplus网站点我就好啦
我们可以发现这里面有两个参数一个是指针，一个是大小，我就直接告诉大家啦，这里的指针是指向我们要扩容的地址处，然后大小是指我们要在这块需要扩容的地方开辟多少大小。
void STPush(ST* pst, STDatatype x) { if (pst->capacity == pst->top) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, newCapacity * sizeof(STDatatype)); if (tmp == NULL) { perror("mallo fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; }
😳栈的出栈(也称弹栈)的代码实现及其讲解
顺序站的出栈，其实就和顺序表的尾删很像，就直接把栈顶的top–就行啦，但是我们得确定一件事，就是当这个顺序栈是空的时候，我们就应该停止删除了，所以这里我选择用assert直接暴力一点。
void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; }
😳栈的判空函数的代码实现
我们在写一个判空的接口函数吧！根据下图我们可以发现，当top==0时，此时的栈就是空的。
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
😳栈的栈顶结点的取得
首先我们得确定我们的栈不能是一个空栈，其次我们会发现去栈顶元素其实就是去栈顶结点的位置的数，但是我们得注意了，我们的思维其实时偏向于数组的，所以我们取栈顶数据时，应该让top-1，就跟我们正常思考一样。
STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; }
😳栈的整体代码的实现
stack.c
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; void STInit(ST* pst); void STDestroy(ST* pst); void STPush(ST* pst, STDatatype x); void STPop(ST* pst); STDatatype STTop(ST* pst); bool STEmpty(ST* pst); int STSize(ST* pst);
stack.h
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; } void STPush(ST* pst, STDatatype x) { if (pst->capacity == pst->top) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, newCapacity * sizeof(STDatatype)); if (tmp == NULL) { perror("mallo fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; }
总结
今天的代码讲解就到这里啦，如果你们觉得还可以的话可以一键三连！！
下一期我们讲的时队列的实现噢！！
