【数据结构入坑指南（五）】--《手把手实现栈结构：附带完整代码与注释，深度揭秘数组实现香在哪？》
🔥@晨非辰Tong：个人主页
👀专栏：《C语言》、《数据结构与算法》、《数据结构与算法刷题集》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：当熟练驾驭了结构复杂、指针纵横的双链表后，是否意味着需要更复杂的数据结构来挑战自己？恰恰相反。接下来登场的「栈」，它摒弃了链表的灵活多变，只在一端固守“后进先出”的准则。看似简单的约束，实则培养精准操作与算法思维的绝佳“内功心法”，更是平稳过渡到「队列」的坚实桥梁。
目录
一、栈的概念和结构
1.1 栈的定义
--栈：一种特殊的线性表，只允许在固定的一端进行插入和删除操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守“后进先出”的原则。
--其中，插入、删除分别称为：
- 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈，出数据也在栈顶。
可以将栈的结构形象的看成水杯，在进行接水（进栈）在杯顶（栈顶），进行倒水也是（出栈）在杯顶（栈顶）。
1.2 栈的基本结构
问题？--栈的底层实现是数组（顺序表）呢？还是链表呢？
：一般栈的实现，数组、链表都可以。但是对结构、复杂度的考虑：选择数组——>将数组的尾部作为栈顶，数组首部作为栈底，而且尾部操作时间复杂度都是O(1)。
--链表其实也可以实现，只不过是在头部进行操作，且时间复杂度：O(1)
--那为什么数组实现更好呢？
：时间一样，那就看空间复杂度——>
- 实现顺序表时，每次申请空间（比如int）虽然是呈2倍增加，但是申请的是4个字节的倍数。
- 但链表则是每插入一个数据要申请一个节点大小的空间，空间较数组而言有点大。
Stack.h //定义栈的结构 typedef int STDataType; typedef struct Stack { STDataType* arr; int top; //指向栈顶的位置---刚好就是栈中有效数据个数 int capacity;//栈的空间大小 }ST;--为什么底层实现与顺序表相同，不用size表示有效数据个数？
：用top更能形象的表示这里栈顶，根据下标，则有效数据个数在top-1位。
二、栈的初始化、销毁
2.1 初始化
--在正式使用栈时，对栈结构进行初始化：
Stack.c #include"Stack.h" //初始化 void STInit(ST* ps) { ps->arr = NULL; ps->top = ps->capacity = 0; }--因为要改变栈的结构（在定义结构时并没有进行任何赋值操作），所以要进行传址调用，用二级指针接收。
--初始时，指针指向空（还没有开辟空间），其余指向0（栈顶、空间根据下标在0的位置）。
test.c #include"Stack.h" void test01() { ST st; STInit(&st);//改变结构 } int main() { test01(); return 0; }--定义变量不是指针变量？
：这就是与链表的区别——>栈底层是数组，其存储数据的空间是连续的，因此不需要额外定义指针变量指向空间；而链表节点的空间不一定连续，就需要通过指针进行地址链接。
--传地址，形参的改变影响实参。
2.2 销毁
--销毁操作与初始化相同，只不过多加一步-->判空，如果数组 arr 为空，代表没有进行开辟空间。
Stack.h #include"Stack.h" //销毁 void STDesTroy(ST* ps) { if (ps->arr)//为空，没进行初始化 { free(ps->arr); } ps->arr = NULL; ps->top = ps->capacity = 0; }--销毁就是将后续进行的入栈（放入数据）等操作重置：将空间释放，指针重新指向空，其余置零。
三、栈基本功能实现
--对于各种功能的实现，其算法原理与顺序表相关算法大同小异。
3.1 入栈（在栈顶放入数据）
Stack.c #include"Stack.h" //入栈——栈顶 void STPush(ST* ps, STDataType x) { assert(ps); //判断空间是否足够 if (ps->top == ps->capacity) { //增容 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //临时变量，防止扩容失败 STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail！"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } //空间足够 ps->arr[ps->top++] = x; }
--空间的判断：与顺序表一致，当 top = capacity 时，代表后面没有位置了，采用 *2 倍扩容。
--断言ps：传的结构体变量指向这块结构体空间，不能传空地址。
test.c #include"Stack.h" void test01() { ST st; STInit(&st);//改变结构 STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); } int main() { test01(); return 0; }3.1.1 定义判空（准备工作）
--在实现出栈之前，我们先要实现一个判空操作的接口。
//栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }--top当处于下标0的位置，代表没有数据，栈为空。
3.2 出栈（栈顶）
--出栈与实现顺序表的删除算法一样，只用将栈顶缩减，后续的入栈就会将旧数据覆盖。
Stach.c #include"Stack.h" //出栈--栈顶 void STPop(ST* ps) { assert(!STEmpty); ps->top--;//栈顶缩减一位 }3.3 取栈顶元素
--说是栈顶元素，看上面的图示，其实就是下标 top - 1 位的元素。
Stack.c #include"Stack.h" //取栈顶元素 STDataType STTop(ST* ps) { assert(!STEmpty(ps)); return ps->arr[ps->top - 1];//返回栈顶元素，实际是下标top-1位 }test.c #include"stack.h" void test1() { ST ps; STInit(&ps); //入栈 STPush(&ps, 1); STPush(&ps, 2); STPush(&ps, 3); STPush(&ps, 4); while (!STEmpty(&ps)) { //取栈顶元素，打印 STDataType top = STTop(&ps); printf("%d ", top); //出栈 STPop(&ps); } printf("\n"); } int main() { test1(); }
代码中的循环就相当于循环出栈顺带将栈顶元素打印出来。
--根据图示，就体现了“先进后出”或“后进先出”的原则。
3.4 获取有效数据个数
--获取有效数据个数，只需要在入栈操作完成后，返回top值就行了。
Stack.c #include"Stack.h" //获取栈中有效元素个数 int STSize(ST* ps) { assert(ps); return ps->top; }
四、实现栈的完整代码
--至此，栈的实现已经全部完成，部分实现的思路与顺序表大差不差，感兴趣的可以看看博主这几篇有关顺序表的的博文：
4.1 Stack.h
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> //定义栈的结构 typedef int STDataType; typedef struct Stack { STDataType* arr; int top; //指向栈顶的位置---刚好就是栈中有效数据个数 int capacity;//栈的空间大小 }ST; //初始化 void STInit(ST* ps); //销毁 void STDesTroy(ST* ps); //入栈 void STPush(ST* ps, STDataType x); //出栈--栈顶 void STPop(ST* ps); //判空 bool STEmpty(ST* ps); //取栈顶元素 STDataType STTop(ST* ps); //获取栈中有效元素个数 int STSize(ST* ps); 4.2 Stack.c
#include"Stack.h" //初始化 void STInit(ST* ps) { ps->arr = NULL; ps->top = ps->capacity = 0; } //销毁 void STDesTroy(ST* ps) { if (ps->arr)//为空，没进行初始化 { free(ps->arr); } ps->arr = NULL; ps->top = ps->capacity = 0; } //入栈--栈顶 void STPush(ST* ps, STDataType x) { assert(ps); //判断空间是否足够 if (ps->top == ps->capacity) { //增容 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail！"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } //空间足够 ps->arr[ps->top++] = x; } //栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } //出栈--栈顶 void STPop(ST* ps) { assert(!STEmpty(ps)); ps->top--;//栈顶缩减一位 } //取栈顶元素 STDataType STTop(ST* ps) { assert(!STEmpty(ps)); return ps->arr[ps->top - 1];//返回栈顶元素，实际是下标top-1位 } //获取栈中有效元素个数 int STSize(ST* ps) { assert(ps); return ps->top; }4.3 test.c
#include"stack.h" void test1() { ST ps; STInit(&ps); //入栈 STPush(&ps, 1); STPush(&ps, 2); STPush(&ps, 3); STPush(&ps, 4); //打印有效数据个数 printf(":%d\n", STSize(&ps)); while (!STEmpty(&ps)) { //取栈顶元素，打印 STDataType top = STTop(&ps); printf("%d ", top); //出栈 STPop(&ps); } printf("\n"); } int main() { test1(); }回顾：
《面试高频数据结构：从单链到双链的进阶，读懂“双向奔赴”的算法之美与效率权衡》
《超越单链表的局限：双链表“哨兵位”设计模式，如何让边界处理代码既优雅又健壮？》
结语：至此，我们对「栈」的探索已告一段落。它用“后进先出”的简单规则，为我们展示了数据结构中“约束”的魅力。从双链表的灵活到栈的专一，我们不仅学会了一种新结构，更学会了一种聚焦核心问题的思维。当栈的操作已内化于心，我们便做好了准备，去迎接下一个遵循“先进先出”规则的伙伴——队列。届时，一个更宏大的数据结构世界将在我们面前展开。
