前言
今天这篇文章继续介绍数据结构中的线性表，今天的主角是——栈。
听到栈这个名词，想必大家会想起来之前所讲的操作系统的内存区域划分中的栈，但是要注意今天要讲到的栈和操作系统中的栈是两个概念（毕竟是两个学科的），可不能傻傻分不清哦。
一、栈
数据结构中的栈，是一种特殊的线性表，它只允许在栈的一端进行数据的插入和删除操作，进行插入和删除操作的一端称为栈顶，另一端称为栈底。
因为栈的这个特性，所以栈中的元素遵循后进先出（LIFO）原则。
对栈的操作有以下两种：
压栈：向栈中插入元素（也叫入栈、进栈），在栈顶插入
出栈：删除栈中的元素，在栈顶删除
二、栈应该如何实现
1.顺序表or链表
我们根据之前的知识可以知道要实现栈可以使用数组或者链表，但是究竟哪个更好呢？还是得综合分析一下它们基于栈的特性哪个更有优势。
因为栈的插入和删除都是在栈顶，正好符合顺序表尾删和尾插效率高这一特性，同时也结合顺序表的其他优点，对比可以看出使用顺序表更优。所以我们就用数组结构来实现栈。
2.静态or动态
让我们先看看，静态栈的定义：
#define N 10 typedef int StackNodeType; typedef struct Stack { StackNodeType a[N];//栈存储数据的数组 int top;//栈顶的下标 }Stack;
在实际应用中我们往往无法预料究竟会有多少个数据需要被处理（即，不确定N定义为多少合适，定义多了，会浪费空间；定义少了，又可能放不下数据），所以动态的栈更好，因此我们本次实现的是动态的栈。
三、栈的实现
1.栈的声明
typedef int StackNodeType; typedef struct Stack//栈的定义 { StackNodeType* s;//栈存储数据所用的数组 int top;//栈顶 int capacity;//容量 }Stack;
2.接口（声明）
//初始化栈 void StackInit(Stack* ps); //销毁栈 void StackDestory(Stack* ps); //入栈 void StackPush(Stack* ps, StackNodeType x); //出栈 void StackPop(Stack* ps); //获取栈顶元素 StackNodeType StackTop(Stack* ps); //获取栈中有效元素个数 int StackSize(Stack* ps); //检测栈是否为空（如果为空返回1，如果不为空返回0） bool StackEmpty(Stack* ps);
3.接口的实现
初始化栈
void StackInit(Stack* ps) { ps->s = NULL; ps->top = ps->capacity = 0;//初始化栈顶和容量(按照这个写法，则top是栈顶元素的下一个位置)，如果要改为第二种情况，则应该是ps->top = -1 ；ps->capacity = 0; }
为什么说top是栈顶元素的下一个位置呢？
想必通过上面的分析图大家就能够理解了，至于具体实现时，到底使用哪种情况，大家可以根据个人爱好来选择，（注意：不同的情况会对其他接口的实现有一些影响，之后具体位置我也会说明的）本次实现是选择第一种情况。
销毁栈
void StackDestory(Stack* ps)//使用完栈要将它销毁，否则会产生内存泄漏问题 { assert(ps); free(ps->s); ps->s = NULL; ps->capacity = ps->top = 0;//第二种情况改为ps->capacity = 0 ; ps->top = -1; }
获取栈顶元素
StackNodeType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->s[ps->top-1];//第二种情况改为return ps->s[ps->top]; }
获取栈中有效元素个数
int StackSize(Stack* ps) { assert(ps); return ps->top; }
入栈
void StackPush(Stack* ps, StackNodeType x) { assert(ps); //判断是否需要扩容 if (ps->top == ps->capacity) { int newcapacity = (ps->capacity == 0) ? 4 : (2 * (ps->capacity)); StackNodeType* temp = (StackNodeType*)realloc(ps->s, newcapacity*sizeof(StackNodeType)); if (temp) { ps->s = temp; ps->capacity = newcapacity; } } ps->s[ps->top] = x; ps->top++; }
出栈
void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps));//判断栈是否为空 ps->top--; }
检测栈是否为空
（如果为空返回1，如果不为空返回0）
bool StackEmpty(Stack* ps) { return ps->top == 0;//如果之前选择第二种情况，此处相应改为return ps->top == -1;即可。 }
注意：使用某些库函数时要记得包含它对应的头文件，我也给大家整理了本次所需要的头文件。
#include<stdio.h> //printf #include<stdbool.h> //bool #include<stdlib.h> //realloc #include<assert.h> //assert
4.主函数（测试）
测试栈的相应功能，以下是我使用的主函数，大家也可以根据需要进行修改，测试其他的测试用例。
void test()//测试栈 { Stack ps; StackInit(&ps);//初始化 StackPush(&ps, 1);//入栈 StackPush(&ps, 2); StackPush(&ps, 3); StackPush(&ps, 4); StackPush(&ps, 5); StackPush(&ps, 6); StackPop(&ps);//出栈 StackPop(&ps); StackPop(&ps); //打印栈中元素（实际上遍历一遍栈中的元素就是出栈，将栈顶元素出栈) while (!StackEmpty(&ps)) { printf("%d ", StackTop(&ps)); StackPop(&ps); } printf("\n"); StackDestory(&ps);//销毁栈 } int main() { test(); return 0; }
总结
以上就是今天要讲的内容，本文介绍了数据结构中的栈，对栈的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路（注释）自行实现栈。
本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！
