【数据结构实战篇】深入浅出：C语言中的栈数据结构

?️专栏：【数据结构实战篇】

?主页：f狐o狸x

        前面几期内容里面我们详细的了解了数据结构中链表的结构，现在我们在来了解一下栈的结构

一、栈

        1.1 栈的概念及结构

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

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

二、栈的实现

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

        2.1 定义一个栈

        因为日常中，大多数情况我们并不知道栈需要多大的空间，所以我们需要用一个指针来管理我们的动态空间

typedef int StackDataType;typedef struct stack{int* StackData;int top;int capacity;}ST;

        2.2 栈的初始化

        与之前链表不一样，栈需要先初始化一下

//初始化void InitStack(ST* ps){assert(ps);ps->StackData = (StackDataType*)malloc(sizeof(StackDataType)*4);if (ps->StackData == NULL){perror("InitStack：：malloc");return;}ps->capacity = 4;ps->top = 0;}

        2.3 栈的增加删除

        我们只需要注意这里栈的增加删除都是在栈顶上完成的就好啦

//增加void STPush(ST* ps, StackDataType x){assert(ps);if (ps->top == ps->capacity){StackDataType* tmp = (StackDataType*)realloc(ps->StackData,sizeof(StackDataType) * ps->capacity * 2);if(tmp == NULL){perror("STPush：：realloc");return;}ps->StackData = tmp;ps->capacity *= 2;}ps->StackData[ps->top] = x;ps->top += 1;}//删除void STPop(ST* ps){assert(ps);assert(!STEmpty(ps));ps->top--;}

        2.3 检查栈是否为空、输出栈顶元素

//判断是否为空bool STEmpty(ST* ps){assert(ps);return ps->top == 0;}//栈顶位置StackDataType STTop(ST* ps){assert(ps);assert(!STEmpty(ps));return ps->StackData[ps->top - 1];}

        2.4 销毁栈

        保持好习惯，有借有还，再借不难嘛

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

        2.5 测试栈

        通过上面的操作我们已经完成了一个栈的创建，我们现在来看看效果

int main(){ST st = { 0 };InitStack(&st);STPush(&st, 1);STPush(&st, 2);printf("%d ", STTop(&st));STPop(&st);STPush(&st, 3);STPush(&st, 4);printf("%d ", STTop(&st));STPop(&st);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}DestoryStack(&st);return 0;}

        我们先来分析一下，程序先入栈了1 2 ，然后出栈了2，屏幕先打印数字2，栈里还有1，然后入栈了3 4，又出栈了4，所以屏幕上数字1后面将打印4，然后栈里还有3 1，在入栈5，此时栈里有5 3 1，一次出栈，最后结果就为：2 4 5 3 1

         现在运行一下程序看看

        嗯~不戳不戳，和我们分析的一模一样呀

        最后还请各位留下你们宝贵的三连吧~