各位读者老爷好，鼠鼠我好久没写博客了（太摆烂了），今天就基于C语言浅介绍一下数据结构里面的栈，希望对你有所帮助吧。
目录
1.栈的概念及结构
2.栈的实现
2.1定义栈
2.2.初始化栈
2.3.入栈
2.4.出栈
2.5.获取栈顶元素
2.6.获取栈中有效元素个数
2.7.检查栈是否为空，如果为空返回真，如果不为空返回假
2.8.销毁栈
3.栈小应用
3.1.Stack.h
3.2.Stack.c
3.3.test.c
4.小知识
5.ending
1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入、删除和访问元素操作（ps：我们之前介绍的顺序表和链表都可以在任意位置插入、删除和访问）。进行数据插入、删除和访问操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
这里有几个概念需要理解，将栈比喻成手枪弹夹十分合适：
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶，弹夹出入弹口就像栈顶。出栈：栈的删除操作叫做出栈。出数据也在栈顶。
后进先出的原则：栈中的数据元素的插入、删除和访问均要遵循这个原则。栈中的数据元素就像子弹，先进入弹夹的子弹会后射出，后进入弹夹的子弹会先射出，栈中数据元素在栈中的操作就像弹夹的子弹一般。
举个列子解释栈中元素遵守的后进先出原则如图：
2.栈的实现
栈的实现一般可以使用数组或者链表实现，实现出来的栈只要满足数据结构对栈的定义即可。相对而言数组的结构实现更优一些，因为数组在尾上插删数据的代价比较小。所以下面我们实现一下以数组尾部为栈顶的数组栈。
而定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈。
我们栈主要实现以下功能：
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回真，如果不为空返回假
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);2.1定义栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;方便后续代码的维护，我们先不妨将int重命名成STDataType。由于实现动态生长的栈我们需要一个STDataType*类型指针a维护以后动态申请的空间（用来存放需存储的数据元素的）。用top指向栈顶元素的下一个元素（可以理解成元素个数）。用capacity记录以后动态图申请空间的大小。将a、top和capacity用结构体包起来并重命名成Stack。画下图方便理解：
2.2.初始化栈
//初始化栈
void StackInit(Stack*ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}断言防止传入的Stack变量地址为空。不妨将a初始化为NULL，所以易知capacity初始化为0合适，由于将top设计成指向栈顶元素下一个元素（或者理解成元素个数） ，所以top也初始化为0。
2.3.入栈
//入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//扩容
if (ps->top == ps->capacity)
{
int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);
STDataType* tmp = realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail:");
return;
}
ps->capacity = newcapacity;
ps->a = tmp;
}
ps->a[ps->top] = data;
ps->top++;
}断言防止传入的Stack变量地址为空（这点以下如有相同不再赘述）。 当top和capacity相等时说明动态申请的空间不足以支持元素入栈，调用扩容函数（扩容了记得更新capacity），将元素在数组尾部入栈，top加一即可。
2.4.出栈
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}断言防止栈为空的时候仍然出栈。元素在数组尾部出栈将top减一即可。
2.5.获取栈顶元素
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}断言防止栈为空时获取栈顶元素（栈为空时获取的栈顶元素不是有效元素）。根据设定，易知top指向栈顶元素的下一个元素，所以ps->a[ps->top-1]就是栈顶元素。
2.6.获取栈中有效元素个数
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}根据设定，我们知道top的含义之一就是有效元素个数，所以返回ps->top即可。
2.7.检查栈是否为空，如果为空返回真，如果不为空返回假
//检测栈是否为空，如果为空返回真，不为空返回假
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}实现这个功能的话返回ps->top==0能很好的形成逻辑自洽。当栈为空时，ps->top==0为真，返回真；当栈不为空时，ps->top==0为假，返回假。
2.8.销毁栈
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}我们再回顾一下栈的想象图：
对于栈的销毁来说，我们需要主动释放动态申请的内存，就是结构体Stack成员中指针a指向的空间（这块空间也是来存放需存放数据元素的）。所以free掉ps->a，再将ps->a置成NULL、将ps->top和ps->capacity置成0即可。
3.栈小应用
上面这么多代码说不定老爷们看到云里雾里，但是没关系，鼠鼠我写一个工程运用一下上面代码（该工程包含上面所有代码），有兴趣的老爷们可以将下面三个文件放到同一个工程下面玩玩，再参考上面鼠鼠的愚见所不定会明白点！
3.1.Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回真，如果不为空返回假
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);3.2.Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
//初始化栈
void StackInit(Stack*ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//扩容
if (ps->top == ps->capacity)
{
int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);
STDataType* tmp = realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail:");
return;
}
ps->capacity = newcapacity;
ps->a = tmp;
}
ps->a[ps->top] = data;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//检测栈是否为空，如果为空返回真，不为空返回假
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}3.3.test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
int main()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
StackPush(&s, 5);
printf("%d\n", StackSize(&s));
StackPop(&s);
printf("%d\n", StackSize(&s));
StackPush(&s, 6);
while (!StackEmpty(&s))
{
printf("%d ", StackTop(&s));
StackPop(&s);
}
printf("\n");
printf("%d", StackSize(&s));
StackDestroy(&s);
return 0;
}
运行结果如图可以看看：
刚开始栈顶入栈五个数据元素，所以第一个printf打印5；然后将数据元素5栈顶出栈，所以第二个printf打印4；再次入栈数据元素6，此时栈内数据元素从栈底到栈顶分别为：1、2、3、4、6。
那我们如何打印栈内所有数据元素呢？
其实写一个如图中的while循环即可，由于栈要严格按照它的规定去访问数据元素，所以访问的数据元素只能时栈顶的，想要访问栈顶数据元素的前一个数据元素就必须将栈顶数据元素出栈才能访问到栈顶数据元素前一个数据元素，所以访问一遍栈后栈也就空了。
根据分析，while循环打印出来的应该是6 4 3 2 1。后面的printf打印为0也证明栈已经空了。
4.小知识
应该有一些老爷们听说过"栈溢出"这个概念，但我们这篇博客介绍的栈不是"栈溢出"的那个栈。
咱们这篇博客讲的栈是数据结构这门学科的概念，是一种数据结构，这个“栈”不存在“栈溢出”的概念。
“栈溢出”讲的栈是操作系统或者编程语言这些学科的概念。我们知道内存会划分成各种区域，其中有一个区域为栈区，“栈溢出”这个栈就是一个内存区域。很多情况会导致栈溢出，比如一个递归程序，由于递归返回条件有问题，导致递归不断建立栈帧，使得栈区空间没了还在建立栈帧就导致“栈溢出”。
5.ending
老弟我也是小白，如果有错误恳请各位大佬指正啊，感谢各位佬阅读到这里了！
