前言以及成型代码：
学习完数据表和链表以后我们来学习一个新的数据结构：栈 。 还是老套路先把成型代码给各位看关老爷呈上方便有一个初步了解。更重要的是可以方便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; }
直接返回栈顶就可以了
