嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记 闲言碎语小记坊 题山采玉
目录
一.栈的认识
二.存储栈的结构选取：
数组：
链表
三栈的模拟实现
结构定义：
初始化：
入栈：
销毁栈：
判空：
出栈：
获取栈顶元素
获取栈中有效元素个数
测试：
相信大家对于栈那一块还是比较了解，在学校c语言时，一定了解过函数栈帧之类的东西，我们就来用c语言来实现一下这个数据结构
一.栈的认识
栈(stack)作为一种数据结构，它遵循一个准则就是后进先出(或者是先进后出)，就像一个箱子里先放了的东西要最后才能拿出来
我们只能在一边进行操作，关于栈有一些名词
栈顶：最后入栈的那个元素 栈底：第一个入栈的元素
入栈(压栈)：向栈顶加入元素 出栈：删除栈顶元素
空栈：栈里面没有元素
二.存储栈的结构选取：
我们之前学习过数组和链表作为基础来实现数据结构，那我们的栈能不能用其中一种来实现呢，
数组：
我们如果用数组来模拟栈，栈底指向最后一个元素，然后如果是出栈操作，只需要将数组个数减减，将最后一个元素弄成了无效元素即可，入栈也很简单a[++size] = x 即可，时间复杂度都是O(1),这就是我们理想的结构，我们有同学就会发现，这玩意不就是顺序表吗，对这就是顺序表，入栈出栈操作，就是顺序表中的尾插头插操作，栈就是访问受限的顺序表。
链表
有了上面的理解，我们就知道实现栈就是要有一个容易实现尾插尾删的结构，但是我们的链表实现尾插尾删的时间复杂度都是O(n)啊，有没有办法能降低O(1)呢。我们知道链表实现头插头删的操作时间复杂度满足我的的预期，咦那我们能不能将栈顶放在头结点，入栈时我们头插，出栈时头删。
但我们为什么不选择链表而更好选择数组来实现栈呢？我们都知道我们的链表有个致命的缺点，就是容易造成空间浪费，空间利用率不高。
三栈的模拟实现
结构定义：
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;这里的top指向的是将要插入的位置。
初始化：
// 初始化栈
void StackInit(Stack* ps)
{ps->a = NULL;ps->capacity = ps->top = 0;
}入栈：
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){//扩容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("扩容失败\n");exit(1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top++] = data;
}这里的申请结点，并没有像顺序表一样单独分装一个函数，因为我们只有这一个地方会增加结点。
销毁栈：
// 销毁栈
void StackDestroy(Stack* ps)
{if (ps->a){free(ps->a);ps->a = NULL;}ps->capacity = ps->top = 0;
}判空：
bool StackEmpty(Stack* ps)
{ assert(ps);return ps->top == 0;
}出栈：
// 出栈
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->top--;
}获取栈顶元素
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}这些功能都很简单就实现了。
测试：
void test()
{Stack st;StackInit(&st);for (int i = 0; i < 10; i++){StackPush(&st, i);}while (!StackEmpty(&st)) //StackSize(&st){STDataType top = StackTop(&st);printf("%d\n", top);StackPop(&st);}StackDestroy(&st);
}int main()
{test();return 0;
}
结果：
完结撒花！
