1.什么是栈？
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除
操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
后进先出
2.动态栈的实现
栈可以用前面章节介绍的数组或者链表的节点实现，数组相比之下更优越一下，动态开辟内存实现扩容，且在数组尾上插入数据代价较小（链表节点还得创建next指针）。
2.1栈的形式
2.2初始化
2.3入栈
2.4出栈
直接top-1就行，如果后序入栈会直接覆盖，也不影响后续出栈，调用栈顶等操作，因为这些操作都基于top的数值来进行的。
2.5调用栈顶
2.6返回有效数据个数
2.7判断是否为空栈
2.8销毁
3.代码
//Stack.h#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int StackDataType;
//栈（stack）
typedef struct Stack
{StackDataType* arr;//数据int capacity;//容量int top;//栈顶，top初始化为0，则top为最后一个有效数据的下一位下标；\top初始化为-1，则为最后一个有效数据下标
}Stack;//初始化
void StackInit(Stack* ps);
//销毁
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, StackDataType x);
//出栈
void StackPop(Stack* ps);
//调用栈顶
StackDataType StackTop(Stack* ps);
//返回个数
int StackSize(Stack* ps);
//判断是否为空栈
bool StackEmpty(Stack* ps);//Stack.c#include "Stack.h"//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = (StackDataType*)malloc(sizeof(StackDataType) * 4);//初始开辟容量4个if (ps->arr == NULL)//开辟失败{perror("Malloc Fail!");exit(1);}ps->capacity = 4; // 初始开辟容量4个ps->top = 0;//top初始化为0，则top为最后一个有效数据的下一位下标
}
//销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}
//入栈
void StackPush(Stack* ps, StackDataType x)
{assert(ps);//需要扩容if (ps->top == ps->capacity){//扩容为原来2倍StackDataType* temp = (StackDataType*)realloc(ps->arr, ps->capacity * 2 * sizeof(StackDataType));if (temp == NULL)//扩容失败{perror("Realloc Fail!");exit(1);}ps->arr = temp;ps->capacity = ps->capacity * 2;}//加入数据ps->arr[ps->top] = x;ps->top++;
}
//出栈
void StackPop(Stack* ps)
{assert(ps);//栈为空不能删assert(ps->top > 0);ps->top--;
}
//调用栈顶
StackDataType StackTop(Stack* ps)
{assert(ps);//栈为空不能调用assert(ps->top > 0);return ps->arr[ps->top - 1];
}
//返回个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
//判断是否为空栈
bool StackEmpty(Stack* ps)
{assert(ps);//真为空，假不为空return ps->top == 0;
}//Test.c#include "Stack.h"void test1()
{Stack ps;StackInit(&ps);StackPush(&ps, 1);StackPush(&ps, 2);StackPush(&ps, 3);StackPush(&ps, 4);StackPush(&ps, 5);printf("%d\n", StackSize(&ps));while (!StackEmpty(&ps)){printf("%d ", StackTop(&ps));StackPop(&ps);}printf("\n%d\n", StackSize(&ps));StackDestroy(&ps);
}int main()
{test1();return 0;
}
