数据结构入门：栈实现全解析

个人专栏《数据结构-初阶》《经典OJ题目》《C语言》欢迎各位大佬交流目录一、栈的概念及结构1、栈的基本概念2、栈的结构二、代码实现0、初始化1、入栈2、出栈3、返回栈顶元素4、获取栈中有效元素个数5、检测栈是否为空6、销毁栈一、栈的概念及结构1、栈的基本概念栈Stack是一种遵循后进先出LIFO, Last In First Out原则的线性数据结构仅允许在表的一端称为栈顶Top进行插入入栈Push和删除出栈Pop操作另一端称为栈底Bottom2、栈的结构栈的存储结构既可以用数组来实现也能用链表来实现注意此处我们说的链表是单链表不考虑双向链表是因为双向链表空间较大且双向链表功能复杂性能较低那么到底是用数组来实现栈还是链表呢我们通过一些操作的时间复杂度进行分析a、对于入栈而言如果是链表实现的栈首先要找到栈顶元素显然需要O(N)级别的时间复杂度而如果是数组实现的栈我们可以直接使用 top 这个下标申请完空间之后直接尾插即可b、对于出栈而言如果是链表实现的栈首先要找到倒数第二个节点显然依旧是O(N)级别的时间复杂度而如果是数组实现的栈直接 top-- 即可综上我们选择用数组来实现栈二、代码实现注意我们是用数组来实现栈说明由于栈的实现较为简单因此所有函数都封装好之后再一起测试首先来完成准备工作同样创建三个文件Stack,c、Stack.h、test.c接着在 .h 文件中包含头文件及结构体的定义//Stack.h #include stdio.h #include stdlib.h #include assert.h typedef int STDataType; //定义栈结构体 typedef struct stack { STDataType* a; //动态数组 int top; //栈顶 int capacity; //容量 }Stack;0、初始化初始化就是将结构体中的指针置为空栈顶和容量均值为0即可这样就代表我们的 top 0 表示无元素因此判断需要扩容的条件就是 top capacity而如果将 top 初始化为 -1即代表我们的 top -1 表示无元素此时判断需要扩容的条件是 top 1 capacity两者初始化均可我们采用 top 0 作为标准//初始化 void STInit(Stack* ps) { assert(ps); ps-a NULL; ps-top ps-capacity 0; }1、入栈分析逻辑我们需要结构体指针以及入栈元素x首先判断空间够不够如果不够则申请空间直接利用 top 表示栈顶元素进行插入即可最后记得 top//入栈 void STPush(Stack* ps, STDataType x) { assert(ps); //判断空间够不够 if (ps-top ps-capacity) { //申请空间 int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity; STDataType* newa (STDataType*)realloc(ps-a,sizeof(STDataType) * newcapacity); if (newa NULL) { printf(realloc failed!\n); return; } ps-a newa; ps-capacity newcapacity; } ps-a[ps-top] x; ps-top; }2、出栈分析逻辑直接改变索引即可即 top-- //出栈 void STPop(Stack* ps) { assert(ps); assert(ps-top 0); ps-top--; }3、返回栈顶元素分析逻辑直接返回下标为 top - 1 的元素即可//获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); return ps-a[ps-top - 1]; }4、获取栈中有效元素个数分析逻辑返回 top - 1 的值即可//获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps-top; }5、检测栈是否为空为空返回非0值不为空返回0分析逻辑判断 top 是否为0//检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps-top 0; }6、销毁栈分析逻辑先 free 指针指向的空间接着将指针置为空最后将 top 和 capacity 置为0即可//销毁栈 void StackDestroy(Stack* ps) { free(ps-a); ps-a NULL; ps-capacity ps-top 0; }三、测试代码我们在 test.c 文件中进行测试1、测试入栈void test() { Stack st; StackInit(st); //入栈1 2 3 4 5 StackPush(st, 1); StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); StackPush(st, 5); while (!StackEmpty(st)) { printf(%d , StackTop(st)); StackPop(st); } printf(\n); StackDestroy(st); } int main() { test(); return 0; }我们运行来看一下没有问题2、测试出栈void test() { Stack st; StackInit(st); //入栈1 2 3 4 5 StackPush(st, 1); StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); StackPush(st, 5); StackPop(st); StackPop(st); StackPop(st); StackPop(st); while (!StackEmpty(st)) { printf(%d , StackTop(st)); StackPop(st); } printf(\n); StackDestroy(st); }出栈四次后栈内还有一个元素1此时再执行两次出栈函数看是否会引发断言没有问题3、测试获取栈顶元素其实已经在入栈时测试过了4、测试返回栈中有效元素个数5、测试检测栈是否为空如有不足之处恳请指出