一.栈的概念和结构
1.一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作；
2.进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；
3.栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则；
压栈：向栈中插入数据；
出栈：从栈中取出数据；
图示：
其实用链表和数组都可以实现栈，但栈底就相当于链表的头，数组的第一个元素，栈顶就相当与链表的尾，数组的最后一个元素，当我们进行压栈或是出栈操作时，链表就需要找到尾，所以时间复杂度为O（N），而数组则是O（1），所以这里选择用数组实现栈比较好。
用数组实现的话，就和前面的顺序表类似了。
二.接口实现
A.初始化 Stackinit 销毁 Stackdestroy
1.Stackinit
1.这里数组的初始化就和顺序表那里是一样的了，需要用到动态内存管理的函数，如果不懂的话，建议去补一下这一块的知识哦；
2.这个top用来记录实时数据的数量，和顺序表那里的 sz 是一样的，但注意：
<1> 如果初始化成0，那么这个 top 就指的是栈顶的下一个位置；
<2> 如果初始化成-1，那么这个 top 就指的是栈顶的位置；
3.初始化容量，这由你自己决定。
1. void Stackinit(Stack* ps) 2. { 3. assert(ps); 4. 5. ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP); 6. if (ps->arr == NULL) 7. { 8. perror("malloc fail"); 9. exit(-1); 10. } 11. ps->top = 0; //表示的是栈顶的下一个位置 12. ps->capacity = MR_CAP; //默认容量 13. }
2.Stackdestroy
这个非常简单，直接看代码吧。
1. void Stackdestroy(Stack* ps) 2. { 3. assert(ps); 4. 5. free(ps->arr); 6. ps->arr = NULL; 7. ps->top = 0; 8. ps->capacity = 0; 9. }
B.插入 Stackpush 删除 Stackpop
1.Stackpush
在插入前，我们需要判断容量是否已满，若已满，则需要扩容。
1. void Stackpush(Stack* ps, STdatatype x) 2. { 3. assert(ps); 4. if (ps->top == ps->capacity) //判断是否已满 5. { 6. STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity); 7. if (tmp == NULL) 8. { 9. perror("realloc fail"); 10. exit(-1); 11. } 12. ps->arr = tmp; 13. ps->capacity *= 2; 14. } 15. ps->arr[ps->top] = x; 16. ps->top++; //数据入栈后，实时数据数量加1 17. }
2.Stackpop
删除前要注意栈是否为空，若为空则不能进行删除操作；
删除就是使 top 减1。
1. void Stackpop(Stack* ps) 2. { 3. assert(ps); 4. assert(ps->top); //判断栈是否为空 5. 6. ps->top--; //删除数据 7. }
C.出栈 Stacktop
出栈前需要判断栈是否为空，为空则无数据可出栈；
因为前面初始化的 top 是0，所以栈顶数据的下标是 top-1 ，如果初始化的 top 是-1，那么栈顶数据的下标则是 top 。
1. STdatatype Stacktop(Stack* ps) 2. { 3. assert(ps); 4. assert(ps->top); //判断栈是否为空 5. return ps->arr[ps->top - 1]; //栈顶数据的下标是 top-1 6. }
D. 栈的有效元素 Stacksize 判空 Stackempty
1.Stacksize
1.若初始化的 top 是0，则 top 就是栈的有效元素个数；
2.若初始化的 top 是-1，则 top+1 为栈的有效元素个数。
1. int Stacksize(Stack* ps) 2. { 3. assert(ps); 4. 5. return ps->top; 6. }
2.Stackempty
1.如果 top 是0，则为空，返回 true；
2.如果 top 不是0，则不为空，返回 false 。
1. bool Stackempty(Stack* ps) 2. { 3. assert(ps); 4. 5. return ps->top == 0; //如果 top ==0 ，则这句代码为真，返回 true；反之，返回 false 6. }
三.源码
Stack.h
1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <assert.h> 4. #include <stdbool.h> 5. 6. #define MR_CAP 5 7. 8. typedef int STdatatype; 9. 10. typedef struct Stack 11. { 12. STdatatype* arr; 13. int top; 14. int capacity; 15. }Stack; 16. 17. void Stackinit(Stack* ps); 18. 19. void Stackpush(Stack* ps,STdatatype x); 20. 21. void Stackpop(Stack* ps); 22. 23. STdatatype Stacktop(Stack* ps); 24. 25. int Stacksize(Stack* ps); 26. 27. bool Stackempty(Stack* ps); 28. 29. void Stackdestroy(Stack* ps);
Stack.c
1. #include "Stack.h" 2. 3. void Stackinit(Stack* ps) 4. { 5. assert(ps); 6. 7. ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP); 8. if (ps->arr == NULL) 9. { 10. perror("malloc fail"); 11. exit(-1); 12. } 13. ps->top = 0; 14. ps->capacity = MR_CAP; 15. } 16. 17. void Stackpush(Stack* ps, STdatatype x) 18. { 19. assert(ps); 20. if (ps->top == ps->capacity) 21. { 22. STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity); 23. if (tmp == NULL) 24. { 25. perror("realloc fail"); 26. exit(-1); 27. } 28. ps->arr = tmp; 29. ps->capacity *= 2; 30. } 31. ps->arr[ps->top] = x; 32. ps->top++; 33. } 34. 35. void Stackpop(Stack* ps) 36. { 37. assert(ps); 38. assert(ps->top); 39. 40. ps->top--; 41. } 42. 43. STdatatype Stacktop(Stack* ps) 44. { 45. assert(ps); 46. assert(ps->top); 47. return ps->arr[ps->top - 1]; 48. } 49. 50. int Stacksize(Stack* ps) 51. { 52. assert(ps); 53. 54. return ps->top; 55. } 56. 57. bool Stackempty(Stack* ps) 58. { 59. assert(ps); 60. 61. return ps->top == 0; 62. } 63. 64. void Stackdestroy(Stack* ps) 65. { 66. assert(ps); 67. 68. free(ps->arr); 69. ps->arr = NULL; 70. ps->top = 0; 71. ps->capacity = 0; 72. }
test.c
1. #include "Stack.h" 2. 3. void testStack() 4. { 5. Stack st; 6. 7. Stackinit(&st); 8. 9. int i = 0; 10. for (i = 1; i <= 8; i++) 11. { 12. Stackpush(&st, i); 13. } 14. printf("%d\n ", Stacksize(&st)); 15. /*while (!Stackempty(&st)) 16. { 17. printf("%d ", Stacktop(&st)); 18. Stackpop(&st); 19. }*/ 20. printf("\n"); 21. Stackdestroy(&st); 22. } 23. 24. int main() 25. { 26. testStack(); 27. 28. return 0; 29. 30. }
🐲👻关于栈的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖
🥰🤩希望小伙伴们可以多多支持博主哦。😍😃
😁😄谢谢你的阅读。😼😸
