😏专栏导读
👻作者简介：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文章来源：https://www.toymoban.com/news/detail-467870.html
#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;
}
总结
今天的代码讲解就到这里啦，如果你们觉得还可以的话可以一键三连！！
下一期我们讲的时队列的实现噢！！文章来源地址https://www.toymoban.com/news/detail-467870.html
到了这里，关于初阶数据结构之栈的实现（五）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
