一、 栈的概念以及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为 栈顶 ，另一端称为 栈底 。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。【后进先出】
压栈：栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶。
出栈：栈的删除操作叫做出栈。 出数据也在栈顶。
一个是数据结构中的栈，是一个数据结构；一个是操作系统中内存划分的一个区域，也叫作栈，是用来函数调用时，建立栈帧。相似点是，都是后进先出。【这两个没有特别的关系，属于两个学科中的名词】入栈时是：1234,，出栈时是4321吗？答案是不一定的，后进先出，是相对而言的，如果2进的时候，1已经出来了，那么1就会在2的前面，所以是不一定的。
二、 栈的实现
栈的实现，是选择数组还是链表呢？答案是：数组。 单链表也可以，但是数组更好
ღ理由是：可以把数组的后面当做栈顶，前面当做栈底。插入，删除方便，但是要扩容。CPU高速缓存命中率会更高。
stack.h
1. #pragma once 2. #include <stdio.h> 3. #include <stdlib.h> 4. #include <assert.h> 5. #include <stdbool.h> 6. 7. typedef int STDataType; 8. 9. typedef struct stack 10. { 11. STDataType* a; 12. int top;//栈顶的位置 13. int capacity;//容量 14. }ST; 15. 16. void StackInit(ST* ps); 17. void StackDestory(ST* ps); 18. //插入 19. void StackPush(ST* ps, STDataType x); 20. //删除 21. void StackPop(ST* ps); 22. //判断栈是否为空 23. bool StackEmpty(ST* ps); 24. //栈有多少个数 25. int StackSize(ST* ps); 26. //访问栈顶的数据 27. STDataType StackTop(ST* ps);
stack.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include "stack.h" 3. 4. void StackInit(ST* ps) 5. { 6. assert(ps); 7. ps->a = NULL; 8. ps->top = 0; 9. ps->capacity = 0; 10. } 11. void StackDestory(ST* ps) 12. { 13. assert(ps); 14. free(ps->a); 15. ps->a = NULL; 16. ps->top = ps->capacity = 0; 17. } 18. //插入 19. void StackPush(ST* ps, STDataType x) 20. { 21. assert(ps); 22. //扩容 23. if (ps->capacity == ps->top)// 24. { 25. int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);//容量 26. ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));// 27. if (ps->a == NULL) 28. { 29. printf("realloc fail \n"); 30. exit(-1); 31. } 32. ps->capacity = newCapacity; 33. } 34. 35. ps->a[ps->top] = x; 36. ps->top++; 37. } 38. //删除 39. void StackPop(ST* ps) 40. { 41. assert(ps); 42. assert(ps->top > 0); 43. --ps->top; 44. } 45. //判断栈是否为空 46. bool StackEmpty(ST* ps) 47. { 48. assert(ps); 49. return ps->top == 0;//等于0的话，就是真，不等于0的话，就是假 50. } 51. //栈有多少个数 52. int StackSize(ST* ps) 53. { 54. assert(ps); 55. return ps->top; 56. } 57. //访问栈顶的数据 58. STDataType StackTop(ST* ps) 59. { 60. assert(ps); 61. return ps->a[ps->top - 1]; 62. }
元素插入的时候（1）如果top初始化的是0，那么就是栈顶元素的后一个位置。【就是在插入元素的后一个位置】先插入元素，top再++（2）top刚开始是-1，top指向栈顶元素，top先++，再放数据。【top指的是下标】
打印栈的元素，需要首先判断栈是否为空，不为空的话，就打印栈顶的元素，然后再删除栈顶的元素，再次进入循环判断栈是否为空。
1. while (!StackEmpty(&st)) 2. { 3. printf("%d ", StackTop(&st)); 4. StackPop(&st); 5. }
三、习题
3.1 选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（B）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
【进栈过程中可以出栈】
3.2 括号匹配问题
https://leetcode.cn/problems/valid-parentheses/
代码如下：【此代码里面不包括栈,仅仅把栈的实现的上述代码把int换成char】
1. bool isValid(char * s) 2. { 3. ST st; 4. StackInit(&st); 5. while(*s) 6. { 7. if (*s == '(' || *s == '[' || *s == '{') 8. { 9. StackPush(&st, *s); 10. s++; 11. } 12. else 13. { 14. if (StackEmpty(&st)) 15. { 16. return false; 17. } 18. char top = StackTop(&st); 19. StackPop(&st); 20. if ((*s == ']' && top != '[') || (*s == ')' && top != '(') || (*s == '}' && top != '{')) 21. { 22. StackDestory(&st); 23. return false; 24. } 25. else 26. { 27. s++; 28. } 29. } 30. } 31. bool ret = StackEmpty(&st); 32. StackDestory(&st); 33. return ret; 34. }
思路：用栈。遍历字符串，如果遇到左括号就入栈，如果是右括号就进行匹配，不匹配就返回false,当遍历完字符串，如果全部匹配，就返回true
注意：C语言比较局限，要先写一个栈。代码区域必须包括栈。
