1、栈的定义
栈( stack )是限定仅在表尾进行插入和删除操作的线性表。也称为先进后出的线性表。
如果还不明白，我们可以将其想象成手枪的弹夹，弹夹即为一个顺序存储结构的栈，子弹即为我们操作的数据，第一颗放进弹夹的里子弹在射击时却是最后一颗被发射出去的子弹，该子弹射出弹夹的顺序，就和我们栈中存储的数据是一样的，先存进去的数据，要最后才能出来。
2、栈顶和栈底
允许插入和删除数据的一端称为栈顶（top），另一端则称为栈底（bottom）
3、栈的操作
栈的操作一般来说由如下几种：
/**************************************************************
* ADT 栈 (stack)
* operation
* InitStack(*S):初始化操作，建立一个空栈
* DestroyStack(*S):若栈存在，则销毁它
* ClearStack(*S):将栈清空
* StackEmpty(S):判断栈是否为空，若为空，返回ture,否返回false
* GetTop(S,*e):若栈存在且为非空，则用 e 返回栈顶元素
* Push(*S,e):若栈S存在，插入新元素e到栈S，并成为栈顶元素
* Pop(*S,*e):若栈S存在，将栈顶元素删除，并用e返回删除的元素
* StackLength(S):返回栈S的元素个数
* endADT
***************************************************************/
4、栈的类型
4.1、栈的顺序存储结构及实现
栈是线性表的特例，因此和线性表一样，顺序存储结构的栈也称为线性栈，也由一个数组来实现，数组下标为0的一端用来做栈底，定义一个变量top来指示栈顶元素在数组中的位置，规定栈为空时，top为-1。
4.2 、栈的结构定义
#define MAXSIZE 20 //栈的长度
typedef int SElemType; //栈中存储的数据类型，根据需要定
typedef struct
{
/* data */
SElemType data[MAXSIZE];
int top;
}SqStack;
4.3、栈的初始化
初始化主要是初始化数组元素，以及栈顶变量top，代码如下：
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:InitStack
* 参数：S : SqStack类型的结构体的地址
* 功能：top初始化为-1
* 修改记录：无
********************************************************************/
#define MAXSIZE 5 //栈的长度,根据需求随时更改
void InitStack(SqStack *S)
{
S->top = -1; //将栈顶标号初始化为-1，空栈
printf("初始化完成\n");
printf("S->top = %d\n",S->top);
}
4.3、栈的销毁
顺序存储结构的栈的销毁感觉就是清除数组元素的意思吧，这里再看大话数据结构时没理解这个销毁的意思，所以这里贴的代码并没有实质性的功能，只是为了文章的完整性贴在这里。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:DestroyStack
* 参数：S : SqStack类型的结构体的地址
* 功能：无
* 修改记录：无
********************************************************************/
void DestroyStack(SqStack *S)
{
}
4.4、清空栈里的元素
将数组里的元素全部清零。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:ClearStack
* 参数：S : SqStack类型的结构体的地址
* 功能：将栈的元素值清0，并将栈顶值恢复为-1
* 修改记录：无
********************************************************************/
void ClearStack(SqStack *S)
{
if(S->top == -1)
{
printf("栈已经为空，不用清除\n");
return;
}
for(int i = S->top; i >= 0; i--) //注意栈清空时，栈顶的值必须为-1
{
S->data[i] = 0; //将栈元素清0
}
S->top = -1; //栈顶值恢复为-1
printf("栈已清空\n");
}
4.5、判断栈是否为空
前面以及提到，当栈为空栈的时候，top为-1，因此只需判断top的值是否为-1即可。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:StackEmpty
* 参数：S : SqStack类型的结构体
* 功能：判断栈是否为空，为空返回ture,否则返回false
* 修改记录：无
********************************************************************/
bool StackEmpty(SqStack S)
{
if(S.top == -1)
{
printf("栈为空\n");
return true;
}
else
{
printf("栈不为空\n");
return false;
}
}
4.6、获取栈顶元素
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:GetTop
* 参数：S : SqStack类型的结构体，*e栈顶元素的地址
* 功能：若栈存在且为非空，则用 e 返回栈顶元素
* 修改记录：无
********************************************************************/
void GetTop(SqStack S,SElemType *e)
{
if(S.top == -1) //栈为空
{
printf("栈为空\n");
return;
}
*e = S.data[S.top];
}
4.7、元素入栈
元素入栈只需记住一点，元素只能从栈顶一端入栈。如下图：
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:Push
* 参数：*S :SqStack类型的结构体的地址 e:需要插入的元素
* 功能：将元素e压入栈S中，并成为栈顶元素，压入成功返回OK，否则返回ERROR
* 修改记录：无
********************************************************************/
bool Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE - 1) //栈已满
{
printf("栈已满\n");
return ERROR;
}
S->data[++S->top] = e; //将元素e插入到栈S内，并成为栈顶元素(上面已经判断过栈是否满了，这里不用再担心栈顶top溢出的问题)
return OK;
}
4.8、元素出栈
同样，元素出栈也只能从栈顶一段出。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:Pop
* 参数：*S :SqStack类型的结构体的地址 e:需要删除的元素的地址
* 功能：将栈顶元素删除，删除成功返回OK，否则返回ERROR
* 修改记录：无
********************************************************************/
bool Pop(SqStack *S,SElemType *e)
{
if(S->top == -1)
{
printf("栈为空\n");
return ERROR;
}
*e = S->data[S->top--]; //将栈顶元素赋值给e后，栈顶向前移动
return OK;
}
4.9、获取栈里的元素个数
栈的元素个数和数组里的元素个数一样，最后一个下标加1即为元素个数，即 top+1 。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:Pop
* 参数：S :SqStack类型的结构体
* 功能：返回栈S的元素个数
* 修改记录：无
********************************************************************/
int StackLength(SqStack S)
{
return (S.top + 1);
}
至此，顺序存储结构的栈的知识就讲完啦，不知道你现在对栈是否有了更深的认识呢，接下来讲解链式存储结构的栈。
5、栈的链式存储结构及实现
栈的链式存储结构和链表的链式存储结构时一样的，只是栈的链式存储结构没有了头指针而是换成了栈顶指针top，栈的链式存储结构没有头结点，因为栈顶就在头部。链式存储结构的内存不在向顺序存储结构那样是连续的，而是在入栈时由系统随机分配的，各个结点由next指针链接起来，就像串珠子一样，如下图：
5.1、栈的结构定义代码
typedef int SElemType; //链栈数据类型，根据需要更改
//在操作StackNode结构体时，一定要确定栈LinkStack不为空，否则在访问该结构体时由于top是野指针而使程序崩溃
typedef struct
{
/* data */
SElemType data; //链栈里的数据
struct StackNode *next; //指向栈顶的后一结点的指针
}StackNode,*LinkStackPtr; //注意这里的StackNode是结构体，而LinkStackPtr是指向结构体指针
typedef struct LinkStack
{
LinkStackPtr top; //栈顶，和next一样都是StackNode类型的指针（区别是top是指向当前节点的指针，而next是指向栈顶后一节点的指针）
int count; //结点个数
}LinkStack;
5.2、栈的初始化
定义一个栈之后，一定要记得初始化它，否则很有可能由于栈顶指针top是一个野指针而错误更改其他内容而导致程序崩溃。
由于链式存储结构的栈是通过指针来实现访问里面的内容的，所以我们访问栈里数据时，必须先确定栈是否为空，否则在操作S.top.data和S.top.next的时候就会出错，这是由于栈为空的时候top并没有指向任何结点，所以这样操作会出错，严重的使程序崩溃。
/*******************************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：InitStack
* 参数：*S ：LinkStack结构体指针
* 功能：初始化LinkStack栈顶top指针,并将链栈长度初始化为0
* 备注：在操作链栈之前必须先将栈顶top指针初始化为NULL
* 防止它们成为野指针，使程序崩溃,并且此时不能直接S.top.next和S.top.data来操作这两个数据
* 因为此时的S.top还没有初始化，是一个野指针，他并不知道自己指向哪里，并且现在还没栈结点，
* S.top.next和S.top.data也不存在。
********************************************************************************/
void InitStack(LinkStack *S)
{
S->top = NULL;
S->count = 0;
#if DEBUG
printf("初始化成功\n");
#endif
}
5.3、栈的销毁
栈的销毁我也没有理解其意思，但是在清除栈时也会将其内存释放掉，所以感觉两者是一样的，因此这里贴的代码并没有实质性意义，只是为了文章的完整性。
/*****************************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名:DestroyStack
* 参数：S : SqStack类型的结构体的地址
* 功能：无
* 修改记录：无
********************************************************************/
void DestroyStack(SqStack *S)
{
}
5.4、清空栈里的元素
在清空链式存储结构的链表时，必须在从栈顶开始释放结点的内存，在释放之前应该先定义一个LinkStackPtr 类型的临时结构体指针变量 p 用来保存即将要清除的栈结点，否则清除下一个节点时，由于内存以及被释放，next指针里的内容也就跟着被清除了，就无法访问后面的结点了。代码如下：
/************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：ClearStack
* 参数：*S ：LinkStack结构体指针
* 功能：将栈清空并释放内存
* 备注：无
***************************************************/
void ClearStack(LinkStack *S)
{
LinkStackPtr p;
if(NULL == S->top)
{
#if DEBUG
printf("栈已空\n");
#endif
return;
}
while(S->top)
{
p = S->top; //使p指向栈顶
S->top = S->top->next; //栈顶向后移
free(p); //释放栈顶
S->count--; //栈结点个数减一
}
#if DEBUG
printf("栈销毁成功\n");
#endif
}
5.5、判断栈是否为空
判断链式存储结构的栈是否为空，只需判断栈顶指针top是否等于NULL即可。这里需要注意的是，以栈顶指针top是否等于NULL前提是，我们在定义一个链式存储结构变量时，一定要紧接着初始化它，否则第一个结点的栈顶top并不一定是NULL,可能是任何值，这是系统随机分配的地址，因此我们栈顶指针再移动到最初的位置时，top并不等于空，这时候就会出现栈实际上以及空了，但是判断结果却不为空，后面再操作栈里的数据就会使程序崩溃。
/************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：StackEmpty
* 参数：S ：LinkStack结构体
* 功能：检测栈是否为空，为空返回false，不为空返回true
* 备注：无
***************************************************/
bool StackEmpty (LinkStack S)
{
if(NULL == S.top)
{
#if DEBUG
printf("栈已空\n");
#endif
return false;
}
else
{
#if DEBUG
printf("栈不为空\n");
#endif
return true;
}
}
5.6、获取栈顶元素
获取栈顶元素比较简单，但首先我们需要判断一下栈是否为空，否则访问栈里的数据也会使程序崩溃。
/************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：GetTop
* 参数：S ：LinkStack结构体，*e : 栈顶元素值
* 功能：获取栈顶元素值
* 备注：无
***************************************************/
void GetTop (LinkStack S, SElemType *e)
{
if(NULL == S.top)
{
#if DEBUG
printf("栈已空\n");
#endif
return ERROR;
}
*e = S.top->data;
}
5.7、元素入栈
链式存储结构的栈一般不会出现栈满的情况，但是为了以防万一，我们还是做一个判断，这里判断malloc是否成功，一般情况下malloc不成功就是计算机系统内存满了。也就是栈满了。
/************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：Push
* 参数：*S ：LinkStack结构体指针，e : 插入的元素
* 功能：将元素e插入链栈，成功返回OK，否则返回ERROR
* 备注：无
***************************************************/
bool Push(LinkStack *S, SElemType e)
{
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
if(NULL == s)
{
#if DEBUG
printf("入栈失败\n");
#endif
return ERROR;
}
s->data = e;
s->next = S->top; //将新元素的next指向之前的栈顶
S->top = s; //将新元素结点赋值给栈顶指针
S->count++;
#if DEBUG
printf("入栈成功\n");
#endif
return OK;
}
5.8、元素出栈
元素出栈就是，先判断栈是否为空，然后从栈顶元素开始出栈，元素出栈之后也要将其内存释放掉。
/************************************************
* 作者：xx
* 时间：2022.10.28
* 函数名：Pop
* 参数：*S ：LinkStack结构体指针，*e : 删除的元素的指针
* 功能：将栈顶元素删除，成功返回OK，否则返回ERROR
* 备注：无
***************************************************/
bool Pop(LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if(NULL == S->top)
{
#if DEBUG
printf("栈已空\n");
#endif
return ERROR;
}
*e = S->top->data; //将即将删除的元素赋值给e，并返回
p = S->top;
S->top = S->top->next; //是栈顶指向后一结点
free(p); //释放结点p
S->count--; //链栈结点个数减1
#if DEBUG
printf("出栈成功\n");
#endif
return OK;
}
5.9、获取栈的元素个数
获取栈的元素个数直接返回count的值即可。
/************************************************
* 作者：xx
* 时间：2022.20.28
* 函数名：StackLength
* 参数：S ：LinkStack结构体
* 功能：获取栈结点个数
* 备注：无
***************************************************/
int StackLength (LinkStack S)
{
return S.count;
}
好啦，至此，栈的顺序存储结构和链式存储结构都讲完啦，众所周知指针是C语言里最难搞的一部分，因此链式存储结构由于涉及到指针所以是比较容易出错了，所以在设计程序时一定要注意，确保函数没有问题，在操作栈里的数据时，一定要确保栈不为空，还有就是一定要初始化、初始化、初始化。顺序存储结构其实就是操作数组，因此只要注意数组不越界就好了