栈的概念
栈是一种特殊的线性表，只允许在固定的一段进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFOA(Last In First Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作也叫出栈，出数据也在栈顶。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的实现
头文件 039-Stack.h
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. #include<stdbool.h> 4. #include<stdio.h> 5. #include<assert.h> 6. #include<stdlib.h> 7. 8. typedef int STDataType; 9. 10. struct Stack 11. { 12. STDataType* a; 13. int top;//栈顶，top指向最后一个数据的下一个位置 14. int capacity;//容量，方便增容 15. }; 16. 17. typedef struct Stack Stack; 18. 19. //初始化 20. void StackInit(Stack* pst); 21. 22. //销毁 23. void StackDestroy(Stack* pst); 24. 25. //栈顶插入元素 26. void StackPush(Stack* pst, STDataType x); 27. 28. //栈顶删除元素 29. void StackPop(Stack* pst); 30. 31. //取栈顶元素 32. STDataType StackTop(Stack* pst); 33. 34. //判断栈空 35. bool StackEmpty(Stack* pst); 36. 37. //求栈元素个数 38. int StackSize(Stack* pst);
源文件 039-Stack.c
1. #include "039-Stack.h" 2. 3. //初始化 4. void StackInit(Stack* pst) 5. { 6. assert(pst); 7. pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); 8. pst->top = 0; 9. pst->capacity = 4; 10. } 11. 12. //销毁 13. void StackDestroy(Stack* pst) 14. { 15. assert(pst); 16. free(pst->a); 17. pst->a = NULL; 18. pst->capacity = pst->top = 0; 19. } 20. 21. //插入元素 22. void StackPush(Stack* pst, STDataType x) 23. { 24. assert(pst); 25. if (pst->top == pst->capacity) 26. { 27. STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2); 28. if (tmp == NULL) 29. { 30. printf("realloc fail\n"); 31. exit(-1); 32. } 33. pst->a = tmp; 34. pst->capacity *= 2; 35. } 36. 37. pst->a[pst->top] = x; 38. pst->top++; 39. } 40. 41. //删除元素 42. void StackPop(Stack* pst) 43. { 44. assert(pst); 45. assert(!StackEmpty(pst)); 46. pst->top--; 47. } 48. 49. //返回栈顶元素 50. STDataType StackTop(Stack* pst) 51. { 52. assert(pst); 53. assert(!StackEmpty(pst)); 54. return pst->a[pst->top - 1]; 55. } 56. 57. //判断栈是否已满，空返回1，非空返回0 58. bool StackEmpty(Stack* pst) 59. { 60. assert(pst); 61. return pst->top == 0; 62. } 63. 64. //求栈中元素个数 65. int StackSize(Stack* pst) 66. { 67. assert(pst); 68. return pst->top; 69. }
测试文件 039-test.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include "039-Stack.h" 3. 4. void TestStack() 5. { 6. Stack st; 7. StackInit(&st); 8. StackPush(&st, 1); 9. StackPush(&st, 2); 10. StackPush(&st, 3); 11. 12. while (!StackEmpty(&st)) 13. { 14. printf("%d ", StackTop(&st)); 15. StackPop(&st); 16. } 17. 18. StackDestroy(&st); 19. 20. } 21. int main() 22. { 23. TestStack(); 24. return 0; 25. }
栈的应用
1.有效的括号 OJ链接
分析：
（1）将栈的实现可以直接copy进去（返回栈顶元素需要做小小的改动：如果栈为空，不能直接assert断言终止，而要返回'\0'），后面只需要实现括号的匹配即可。
（2）如何实现括号匹配？如果是左括号，那么入栈，如果是右括号就判断栈顶元素该右括号是否能够匹配，如果可以就从栈里弹出一个左括号，如果不匹配就直接返回false。
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #pragma once 3. #include<stdbool.h> 4. #include<stdio.h> 5. #include<assert.h> 6. #include<stdlib.h> 7. 8. typedef int STDataType; 9. struct Stack 10. { 11. STDataType* a; 12. int top;//栈顶，top指向最后一个数据的下一个位置 13. int capacity;//容量，方便增容 14. }; 15. 16. typedef struct Stack Stack; 17. 18. //初始化 19. void StackInit(Stack* pst); 20. 21. //销毁 22. void StackDestroy(Stack* pst); 23. 24. //栈顶插入元素 25. void StackPush(Stack* pst, STDataType x); 26. 27. //栈顶删除元素 28. void StackPop(Stack* pst); 29. 30. //取栈顶元素 31. STDataType StackTop(Stack* pst); 32. 33. //判断栈空 34. bool StackEmpty(Stack* pst); 35. 36. //求栈元素个数 37. int StackSize(Stack* pst); 38. 39. //初始化 40. void StackInit(Stack* pst) 41. { 42. assert(pst); 43. pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); 44. pst->top = 0; 45. pst->capacity = 4; 46. } 47. 48. //销毁 49. void StackDestroy(Stack* pst) 50. { 51. assert(pst); 52. free(pst->a); 53. pst->a = NULL; 54. pst->capacity = pst->top = 0; 55. } 56. 57. //插入元素 58. void StackPush(Stack* pst, STDataType x) 59. { 60. assert(pst); 61. if (pst->top == pst->capacity) 62. { 63. STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2); 64. if (tmp == NULL) 65. { 66. printf("realloc fail\n"); 67. exit(-1); 68. } 69. pst->a = tmp; 70. pst->capacity *= 2; 71. } 72. 73. pst->a[pst->top] = x; 74. pst->top++; 75. } 76. 77. //删除元素 78. void StackPop(Stack* pst) 79. { 80. assert(pst); 81. assert(!StackEmpty(pst)); 82. pst->top--; 83. } 84. 85. //返回栈顶元素 86. STDataType StackTop(Stack* pst) 87. { 88. assert(pst); 89. if(StackEmpty(pst)) 90. { 91. return '\0'; 92. } 93. //assert(!StackEmpty(pst)); 94. return pst->a[pst->top - 1]; 95. } 96. 97. //判断栈是否已满，空返回1，非空返回0 98. bool StackEmpty(Stack* pst) 99. { 100. assert(pst); 101. return pst->top == 0; 102. } 103. 104. //求栈中元素个数 105. int StackSize(Stack* pst) 106. { 107. assert(pst); 108. return pst->top; 109. } 110. 111. 112. bool isValid(char * s) { 113. Stack st; 114. StackInit(&st); 115. while (*s) 116. { 117. //左括号入栈 118. if (*s == '(' || *s == '[' || *s == '{') 119. { 120. StackPush(&st, *s); 121. s++;//迭代 122. } 123. else 124. { 125. if (StackEmpty(&st)) 126. { 127. return false; 128. } 129. //右括号找最近的左括号匹配 130. char top = StackTop(&st); 131. if (top == '(' && *s != ')' 132. || top == '[' && *s != ']' 133. || top == '{' && *s != '}') 134. { 135. StackDestroy(&st); 136. return false; 137. } 138. else 139. { 140. //匹配就弹出左括号 141. StackPop(&st); 142. s++;//迭代 143. } 144. } 145. } 146. 147. bool ret = StackEmpty(&st); 148. StackDestroy(&st); 149. return ret; 150. } 151. 152. 153. 154.
