目录
前言以及成型代码：
学习完数据表和链表以后我们来学习一个新的数据结构：栈 。 还是老套路先把成型代码给各位看关老爷呈上方便有一个初步了解。更重要的是可以方便CV工程师的工作
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.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);
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->top = 0;
pst->capacity = 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("realloc 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;
}
一、栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
三、代码实现以及详细解释
1. 初步介绍
定义结构体，以及栈内数据类型初始化栈 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);
2. 定义结构体，以及栈内数据类型
代码：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType; //定义栈内数据类型，方便后面修改
typedef struct Stack //创建栈的基本结构
{
STDataType* a;
int top;
int capacity;
}ST;
这几行代码是栈的地基，也是这个结构中最简单的代码了。
3. 初始化栈 void STInit(ST* pst);
代码：
// 初始化栈
void STInit(ST* pst)
{
assert(pst); //判断是否为空指针
pst->a = NULL; //栈为空的，所以先初始化为空指针
pst->top = 0;
pst->capacity = 0;
}
初始化栈，顾名思义就是把栈的结构上面添加一些初始值。让前面的地基有框架。
4. 销毁栈 void STDestroy(ST* pst);
代码：
// 销毁栈
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a); //释放指针
pst->a = NULL; //置空指针a
pst->top = 0; //把栈顶的位置降低，释放数据
pst->capacity = 0;//把栈的大小置为0
}
创建以后肯定是要销毁的，要不然就会造成内存泄漏。
5.添加数据 void STPush(ST* pst, STDataType x);
代码：
// 添加数据
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));//使用realloc扩出来一定的空间
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp; //初始化这一块空间
pst->capacity = newcapacity;
}
pst->a[pst->top] = x; //把x的直插入到栈的顶部
pst->top++;
}
添加数据也是很重要的一个步骤，这一步直接决定了这个栈的成功与否。添加的时候要首先判断后面的空间是否足够，够的话直接加上去，不够的话就扩容。
6.删除数据 void STPop(ST* pst)；
// 删除数据
void STPop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst))); //判断是否为空
pst->top--;
}
删除数据的时候要借助后面的判空函数，为空就不能再删除了
7. 弹出数据 STDataType STTop(ST* pst);
代码：
// 弹出数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst)));
return pst->a[pst->top - 1];
}
弹出数据就是：调用完这个函数以后可以返回栈顶的值
8. 判断是否为空 bool STEmpty(ST* pst);
// 判断是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;//判空
}
判空就是看里面还有数据没有了，有的话返回false 没有数据也就是空值的状态就返回true
9. 判断大小 int STSize(ST* pst);
代码：
// 判断大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
直接返回栈顶就可以了
