💨栈的概念及结构
✔概念
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
✔结构
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵循后进先出的原则。
压栈：栈的插入操作叫做 进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫出栈。出数据也在栈顶。
👇练习题
这道题很简单，栈的数据元素规则就是后进先出，这组元素中，E是最后进来的所以它先出去，其次就是元素D。 所以选B
栈可以想象成一个管道，你从管道口往里放一个东西，之后如果你还想放东西是不是还是需要从管道口往里放？那么你第一次放的东西就越靠近里面了，你没取一次东西肯定是先从靠近管道口的位置取。
便于学习时，也可以看成弹夹。
这题答案是C。
A中顺序：1进--1出--234进完--4出--3出--2出
B中顺序：12进--2出--3进--3出--4进--4出--1出
D中顺序：123进--3出--4进--4出--2出--1出
💨栈的实现
推荐使用数组来实现栈
下面我们来看具体需要实现栈的哪些需求。
🎈Stack.h
typedefintSTDataType; typedefstructStack{ STDataType*a; inttop; intcapacity; }ST; voidStackInit(ST*ps); //初始化voidStackDestory(ST*ps); //销毁voidStackPush(ST*ps, STDataTypex); //入栈voidStackPop(ST*ps); //出栈STDataTypeStackTop(ST*ps); //返回栈顶元素intStackSize(ST*ps); //求栈数据个数boolStackEmpty(ST*ps); //判断栈是否为空
一些解释：
🚩#pragma once是预编译
🚩头文件中assert是类型断言的头文件，断言函数assert()，只有当括号内判断为真时才执行程序下面的代码
🚩定义的结构体中，top是栈顶指针，capacity是容量（不够的时候要增容）
🎈Stack.c
voidStackInit(ST*ps) //初始化{ assert(ps); //结构体指针不能为空ps->a=malloc(sizeof(STDataType)*4); //动态内存开辟空间if (ps->a==NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity=4; ps->top=0 ; //如果top给0意味着指向的是栈顶元素的下一个 ； -1表示指向栈顶元素} voidStackDestory(ST*ps) //销毁{ assert(ps); free(ps->a); ps->a=NULL; ps->top=ps->capacity=0; } voidStackPush(ST*ps, STDataTypex) //入栈{ assert(ps); if (ps->top==ps->capacity) { STDataType*tmp=realloc(ps->a, ps->capacity*2*sizeof(STDataType)); if (tmp==NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a=tmp; ps->capacity*=2; } } ps->a[ps->top] =x; ps->top++; } voidStackPop(ST*ps) //出栈{ assert(ps); //栈空了，调用Pop，直接中止程序报错assert(ps->top>0); ps->top--; } STDataTypeStackTop(ST*ps) //返回栈顶元素{ assert(ps); assert(ps->top>0); returnps->a[ps->top-1]; } intStackSize(ST*ps) { assert(ps); returnps->top; } boolStackEmpty(ST*ps) //判断栈是否为空{ assert(ps); returnps->top==0; }
🎈main.c测试接口
intmain() { STst; //声明一个结构体变量StackInit(&st);//初始化栈StackPush(&st, 1); //入栈数据1,2,3,4，5StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); while (!StackEmpty(&st)) //如果栈不为空，就可以取数据 { printf("%d ", StackTop(&st)); StackPop(&st); //出栈 } printf("\n"); StackDestory(&st);//销毁栈return0; }
