🌟一、栈
🌏1.1栈的概念及结构：
栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last ln First Out)的原则。
压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈: 栈的删除操作叫做出栈。出数据也在栈顶。
🌏1.2实现栈的两种方式：
数组栈
链式栈
对于链式栈是不建议第一种写法的因为尾删需要找到前一个结点(单链表)
🌟二、栈实现(数组栈)
🌏2.1结构：
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Strack { 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); //获取size int STSize(ST* pst);
🌏2.2初始化：
对于初始化有两种写法，可不要小看这两种，对后面的代码每种都有每种的情况所以要分情况写。
💫2.2.1第一种代码：
void STInit(ST* pst) { assert(pst);//判空不然为空就需要传二级指针或者返回值 pst->a = NULL; pst->top = -1; pst->capacity = 0; }
💫2.2.2流程图：
💫2.2.3第二种代码：
void STInit(ST* pst) { assert(pst);//判空不然为空就需要传二级指针或者返回值 pst->a = NULL; pst->top = 0; pst->capacity = 0; }
💫2.2.4流程图：
总结：两种的区别就在于top指向哪到底是栈顶元素还是栈顶后一个元素，我们选择第二种写法
🌏2.3：释放内存
void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity =pst->top = 0; }
🌏2.4：入栈
void STPush(ST* pst, STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a [pst->top ] = x; pst->top++; }
对于初始化第一种扩容要判断pst->top+1 == pst->capacity
🌏2.5：出栈
void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--;//这里要注意top不能为空 }
🌏2.6：访问栈顶元素
STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1];//当top为空时-1就越界了所以要判空 }
对于初始化第一种写法，返回return pst->a[pst->top ];
🌏2.7：判空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
🌏2.8：获取元素个数
int STSize(ST* pst) { assert(pst); return pst->top; }
对于初始化第一种获取元素个数要返回return pst->top+1;
🌟二、栈实现完整代码
//Stack.h #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Strack { 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); //获取size int STSize(ST* pst); //Stack.c #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->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity); 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--;//这里要注意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; } //Test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void TestStack() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); printf("%d ", STTop(&st)); STPop(&st); STPush(&st, 3); STPush(&st, 4); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } STDestroy(&st); } int main() { TestStack(); return 0; }
😽总结
😽Ending,今天的栈和队列(上)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。
