一.栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的模拟实现
要实现栈，首先要想清楚是用节点式（链表式结构）还是连续空间式 （顺序表）来管理、实现栈。而要想弄清楚选择种结构就要知道栈的功能需求。
根据栈的概念就知道栈的功能需求就是入栈，出栈。对应尾插，尾删。我们知道，顺序表在这方面是优于链表的。因为链表在尾插、尾删的时候要找到尾节点以及尾节点的前一个，代价较大。顺序表就可以直接进行尾插、尾删。
stack.h
stack.c
1. void IntiStack(Stack* stack)//初始化栈 2. { 3. DateType* tmp = (DateType*)malloc(4*sizeof(DateType)); 4. assert(tmp); 5. stack->arr = tmp; 6. stack->top = 0;//top置为0 7. stack->capcity = 4;//初始容量为4 8. } 9. void PushStack(Stack* stack, DateType n)//入栈，尾插 10. { 11. assert(stack); 12. if (stack->top == stack->capcity)//检查栈是否满了，满了就需要扩容 13. { 14. //扩容 15. DateType* tmp = realloc(stack->arr,2 * stack->capcity * sizeof(DateType)); 16. assert(tmp); 17. stack->arr = tmp; 18. stack->capcity *= 2;//容量变为2倍 19. } 20. stack->arr[stack->top] = n;//top位置存放数据 21. stack->top++;//top向后迭代 22. } 23. void PopStack(Stack* stack)//出栈，尾删 24. { 25. assert(stack); 26. assert(!StackEmpty(stack));//保证栈不为空，空栈不能删除 27. stack->top--; 28. } 29. bool StackEmpty(Stack* stack) 30. { 31. assert(stack); 32. return stack->top == 0;//如果top为0，代表栈为空，返回true 33. } 34. int StackSize(Stack* stack) 35. { 36. assert(stack); 37. return stack->top;//直接返回有效数据个数top 38. } 39. DateType TopStack(Stack* stack) 40. { 41. assert(stack); 42. assert(!StackEmpty(stack));//保证栈不为空，栈为空stack->top-1==-1就会越界 43. return stack->arr[stack->top - 1]; 44. } 45. void DestoryStack(Stack* stack) 46. { 47. assert(stack); 48. free(stack->arr);//释放顺序表空间 49. stack->arr = NULL; 50. stack->capcity = 0; 51. stack->top = 0; 52. }
