一、栈的定义
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈可以这样理解：相信大家都对枪械有一定粗略的了解，咱们就用压子弹来帮助大家进行理解。
压栈，大家可以想象为压子弹，子弹是一发一发往下压，那压栈就是在容量之内一个数据一个数据往下压。
出栈，大家可以理解为子弹射出的过程，即：最后压入的子弹先出。数据最后的先出。
这就是压栈与出栈的过程，当然也可以压一个出一个，压多个出一个都可以，大家完全就可以把栈当作压子弹和子弹射出。
好了，基础知识我们已经掌握，那么，我们该用什么结构来实现栈呢？
通过单链表，双链表还是什么？大家可以在此处进行思考，稍后公布答案。
二、栈的实现
上文说到，我们要选择一个结构来实现栈。我们来一一分析一下：
双链表全称为：带头双向循环链表，用它来实现可以吗？还用说吗？太过于完美当然可以，但是要用两个指针，同学们，一个指针已经困扰大家已久，那两个指针想必是大家不想经历的大恐怖。所以，这个时候咱们把它先列为备胎（实在没办法在想它（在特殊情况下能渣则渣）🐶）。
单链表全称为：不带头单向不循环链表，大家想单链表找到尾元素麻烦吗？找一遍时间复杂度为O（N）。虽然我们可以反转一下，但是你愿意用吗？要是放两个指针还不如用双链表。
这个时候怎么办？难道我们要使用双链表？不，绝对不行。这时，数组意外路过，对啊，我们可以用数组。
数组每次使用前像顺序表一样判断是否开辟空间，在用一个变量size来记录尾，这样不就完美符合要求了。那说干就干吧。打开我们心爱的VS。
2.1 栈的结构
栈的结构，可以借鉴一下顺序表，要有数组、容量和栈定元素。结构如下：
1. // 支持动态增长的栈 2. typedef int STDataType; 3. typedef struct Stack 4. { 5. STDataType* a; 6. int top; // 栈顶 7. int capacity; // 容量 8. }Stack;
2.2 栈的初始化
要进行初始化，大家想一想top赋值为多大合适，如果为0，那么0是不是为栈的第一个元素？是不是？答案是：是的。那么，有没有办法不叫top指向数组第一个元素？有，使top的值为-1即可。在后续代码中，我会将top初始化为0（别问，问就是top此时可以当顺序表中的size使用）。代码如下：
1. // 初始化栈 2. void StackInit(Stack* ps) 3. { 4. assert(ps); 5. ps->a = NULL; 6. ps->capacity = ps->top = 0; 7. }
2.3 栈的销毁
在我们今后写代码一定要记住：只要你malloc，realloc一定要free，你创建了就一定要销毁。
那我们创建了一个栈，那么我们一定要销毁。代码如下：
1. // 销毁栈 2. void StackDestroy(Stack* ps) 3. { 4. assert(ps); 5. free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！ 6. ps->a = NULL; 7. ps->capacity = ps->top = 0; 8. }
注意事项写在代码里了，一定要记住！！！
2.3 栈元素的插入
1. void StackPush(Stack* ps, STDataType data) 2. { 3. assert(ps); 4. if (ps->capacity == ps->top) 5. { 6. int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity); 7. STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType)); 8. if (newnode == NULL) 9. { 10. perror("realloc fail"); 11. return; 12. } 13. ps->capacity = newcapacity; 14. ps->a = newnode; 15. } 16. //这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用 17. ps->a[ps->top] = data; 18. ps->top++; 19. //这里也可以合二为一 20. //ps->a[ps->top++] = data; 21. }
此处要点与顺序表类似，就不过多强调。
2.4 栈元素的删除
1. // 出栈 2. void StackPop(Stack* ps) 3. { 4. assert(ps); 5. assert(ps->top > 0); 6. ps->top--; 7. }
此处代码过于简单，那么能不能不把这个封装了，直接写。其实你要是想这么干，你可以试一试，不过提醒一下：可能会出乱子。还是那句话：专业的事专业的人做。
2.5 栈顶元素获取
1. // 获取栈顶元素 2. STDataType StackTop(Stack* ps) 3. { 4. assert(ps); 5. assert(ps->top > 0); 6. return ps->a[ps->top - 1]; 7. }
对于此代码最后的返回值可能会有人有疑问，我简单解释一下： 
2.6 栈元素有效个数获取
1. // 获取栈中有效元素个数 2. int StackSize(Stack* ps) 3. { 4. assert(ps); 5. return ps->top; 6. }
上文说过top初始化为0时可当size来使用，代码简单，不过多解释。
2.7 栈是否为空判断
1. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 2. bool StackEmpty(Stack* ps) 3. { 4. assert(ps); 5. return ps->top == 0; 6. }
注意点：必须包含头文件：stdbool.h。
三、代码总览
Stack.h
1. #pragma once 2. #include<stdio.h> 3. #include<stdlib.h> 4. #include<assert.h> 5. #include<stdbool.h> 6. 7. // 支持动态增长的栈 8. typedef int STDataType; 9. typedef struct Stack 10. { 11. STDataType* a; 12. int top; // 栈顶 13. int capacity; // 容量 14. }Stack; 15. 16. // 初始化栈 17. void StackInit(Stack* ps); 18. // 入栈 19. void StackPush(Stack* ps, STDataType data); 20. // 出栈 21. void StackPop(Stack* ps); 22. // 获取栈顶元素 23. STDataType StackTop(Stack* ps); 24. // 获取栈中有效元素个数 25. int StackSize(Stack* ps); 26. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 27. bool StackEmpty(Stack* ps); 28. // 销毁栈 29. void StackDestroy(Stack* ps);
Stack.c
1. #include"Stack.h" 2. 3. // 初始化栈 4. void StackInit(Stack* ps) 5. { 6. assert(ps); 7. ps->a = NULL; 8. ps->capacity = ps->top = 0; 9. } 10. // 入栈 11. void StackPush(Stack* ps, STDataType data) 12. { 13. assert(ps); 14. if (ps->capacity == ps->top) 15. { 16. int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity); 17. STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType)); 18. if (newnode == NULL) 19. { 20. perror("realloc fail"); 21. return; 22. } 23. ps->capacity = newcapacity; 24. ps->a = newnode; 25. } 26. //这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用 27. ps->a[ps->top] = data; 28. ps->top++; 29. //这里也可以合二为一 30. //ps->a[ps->top++] = data; 31. } 32. // 出栈 33. void StackPop(Stack* ps) 34. { 35. assert(ps); 36. assert(ps->top > 0); 37. ps->top--; 38. } 39. // 获取栈顶元素 40. STDataType StackTop(Stack* ps) 41. { 42. assert(ps); 43. assert(ps->top > 0); 44. return ps->a[ps->top - 1]; 45. } 46. // 获取栈中有效元素个数 47. int StackSize(Stack* ps) 48. { 49. assert(ps); 50. return ps->top; 51. } 52. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 53. bool StackEmpty(Stack* ps) 54. { 55. assert(ps); 56. return ps->top == 0; 57. } 58. // 销毁栈 59. void StackDestroy(Stack* ps) 60. { 61. assert(ps); 62. free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！ 63. ps->a = NULL; 64. ps->capacity = ps->top = 0; 65. }
测试代码:test.c
1. #include"Stack.h" 2. 3. int main() 4. { 5. Stack p; 6. StackInit(&p); 7. StackPush(&p, 1); 8. StackPush(&p, 2); 9. StackPush(&p, 3); 10. StackPush(&p, 4); 11. while (!StackEmpty(&p)) 12. { 13. printf("%d ", StackTop(&p)); 14. StackPop(&p); 15. } 16. StackDestroy(&p); 17. return 0; 18. }
四、例题
既然明白了，那么来几道题巩固一下吧！
例一：
设栈S和队列 Q的初始状态均为空，元素 abcdepg 依次进入栈S。若每个元素出栈后立即进入队列 Q，且7个元素出队的顺序是 bdcfeag，则栈S的容量至少是：
例二：
若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是（）。
A. dcebfa B. cbdaef C.bcaefd D.afedcb
例三：
元素 a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 
好了，我们的学习到现在就结束了，如有疑惑可私信，也可在评论区留言。
完！
