目录
前言
这一篇文章我们谈谈栈。
（以下仅代表个人观点，代码和内容有错请指正）
主要内容：动态栈的创建初始化、数据入栈、数据出栈、获取栈顶元素、清空栈内元素、获取栈内元素个数、检测栈是否为空、栈扩容和断言、栈的几个应用。
我认为栈这种数据结构要说的不是很多，主要就是先进后出这种思想。栈也是一种线性表，既然是线性表那么就有线性表的两种表达形式：顺序栈和链式栈（两者的区别在于存储的数据元素在物理结构上是否是相互紧挨着的）。顺序栈存储元素预先申请连续的存储单元；链式栈有需要才申请，数据元素不紧挨着。我们平时浏览网页返回上一个页面就是一个类似的栈结构，程序代码的执行顺序也是利用了这一种结构来执行。话不多说，我们直接步入正题。
扩容和断言
首先对以下代码当中出现的assert()函数和realloc()函数做一个简单的介绍。
断言介绍
字太多了我这里就放图片了，也方便保存图片。不用看完，简单知道用处就行，
本篇文章我只用断言放在函数入口对参数进行合法性的检查。
报错时显示情况：assert(0); 这句代码报错情况如下
会显示错误在第几行和文件路径。
realloc()函数介绍
该函数有两个参数：第一个为原指针的地址，第二个为分配的空间大小。如下面这一句代码举例：
stack->array=(Typement*)realloc(stack->array,sizeof(Typement)*(stack->capacity*2));
realloc()函数可以实现分配内存减小和扩大的功能，我们这里只讨论扩大的情况。
扩容情况分类
（1）如果当前内存段后面有足够的空闲空间供我们使用，则直接扩展这段内存空间，realloc()将返回原指针。
（2）如果当前内存段后面的空闲空间不够，那么就使用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块位置。
（3）如果申请失败，将返回NULL，此时，原来的指针仍然有效。
结构体及宏定义如何定义
写栈的方式有很多种，我这里列举几个比较经典的方式。
以下所有功能均用第一种方式的代码实现。
第一种方式（顺序栈）
结构体当中定义的是一个int类型的指针方便后期扩容，这种方法实质上还是利用了数组实现栈，只不过可以利用指针动态扩容。
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Typement;//宏定义实现简单的多态
typedef struct Stack{
Typement *array;//这里相当于定义了一个int类型的数组
int top;//顶部元素下标
int bottom;//底部元素下标
int capacity;//表示总的栈节点
}SK;
第二种方式（链式栈）
这一种方式将栈内节点和栈的信息分开用两个结构体存放。
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Typement;//宏定义实现简单的多态
typedef struct Node{//栈内节点
Typement Element;
struct Node *next;
}ND;
typedef struct Stack{//栈的结构体
ND top;
ND bottom;
}SK;
第三种方式（顺序栈）
和第一种方式十分相似，只不过创建的是一个静态栈。
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define MAX 100;
typedef int Typement;//宏定义实现简单的多态
typedef struct Stack{
Typement stack[MAX];//静态栈定义的一个数组
int top;//顶部元素下标
int bottom;//底部元素下标
int capacity;//表示总的栈节点
}SK;
栈的初始化
初始化一个栈，即将指向顶部元素的top赋值为0，指向底部元素的bottom也赋值为0，表示栈内总节点的capacity赋值为1。
值得我们注意的是，栈的top实际上指向的是栈顶元素的下一个元素（即即将入栈的元素存放的位置）。初始化的时候栈为空，不包含一个元素（只有一个可供存放的节点）。
void InitStack(SK *stack){//初始化栈
assert(stack);//断言检测地址是否合法
stack->array=(Typement*)malloc(sizeof(Typement)); //给指针分配内存
stack->top=0;//初始化时顶部为下标为0的节点
stack->bottom=0;//底部也为下标为0的节点
stack->capacity=1;//初始化时可以用的栈节点只有1个
}
数据入栈
数据入栈我们要
注意判断栈内是否还有可用的空间，如果没有空间可以使用我们需要对栈进行扩容
，然后将数据放入栈内，top的值加1指向下一个即将存放数据的节点下标。
void PushStack(SK *stack,Typement number){//数据入栈
assert(stack);//断言检测地址是否合法
if( stack->top >= stack->capacity ){/*如果指向顶部游标大于等于了总的栈节点，就表示栈满了，需要扩容 */
stack->array=(Typement*)realloc(stack->array,sizeof(Typement)*(stack->capacity*2)); //对栈进行扩容
/*扩容这点还隐藏了一个细节，如果当前指针后面的空闲内存足够多，就依旧是原来的地址
如果不满足会分配一个新的地址,所以需要再次检验地址是否合法*/
assert(stack->array);
stack->capacity=stack->capacity*2;//扩大总栈节点个数
}
stack->array[stack->top++]=number; //数据入栈
}
数据出栈
数据出栈我们要注意判断栈是否为空。
void PopStack(SK *stack){//数据出栈
assert(stack->array);
if(stack->top<0){//如果栈的顶部元素下标小于0，栈为空，没有节点可以出栈。
return;
}
/*顶部节点指向顶部下方一个节点，最上面的就出栈了，但是其数据还是存在
只不过是指向节点的游标改变了。*/
stack->top--;
}
获取栈顶元素数据
int GetTopStack(SK *stack){//获取栈顶元素
assert(stack->array);
if(stack->top<0){//如果栈的顶部元素下标小于0，栈为空没有元素可以取。
return NULL;
}
return stack->array[stack->top-1];//在这个栈当中，top指向的是栈顶节点的下一个节点，即下一个准备入栈元素的节点位置。
}
清空栈
void EmptyStack(SK *stack){//清空栈里所有元素
assert(stack->array);
free(stack->array);//简单的清空数据只需要把top等于bottom即可,释放内存更好。
InitStack(stack);//清空栈里元素所有元素相当于初始化栈，我们先释放之前栈的内存，再初始化。
}
获取栈内总节点个数和检测栈是否为空
int GetSizeStack(SK *stack){//获取栈内元素个数
assert(stack->array);
return stack->top;
}
int IsEmptyStack(SK *stack){//检测栈是否为空
assert(stack);
return stack->top==0? 1: 0;//三元表达式，为空返回1，不为空返回0
}
测试
int main(){
//测试
SK *TextStack=(SK*)malloc(sizeof(SK));
//初始化
InitStack(TextStack);
printf("初始化后栈是否为空（1代表为空，0代表不为空）：%d\n",IsEmptyStack(TextStack));
//数据入栈
PushStack(TextStack,1);
PushStack(TextStack,2);
PushStack(TextStack,3);
printf("数据入栈之后栈内节点数量：%d\n",GetSizeStack(TextStack));
//数据出栈获取栈顶元素显示并输出栈内总元素个数
printf("数据入栈之后栈是否为空（1代表为空，0代表不为空）：%d\n",IsEmptyStack(TextStack));
printf("当前栈顶元素为：%d ",GetTopStack(TextStack));
PopStack(TextStack);
printf("出栈之后剩余元素个数：%d\n",GetSizeStack(TextStack));
printf("当前栈顶元素为：%d ",GetTopStack(TextStack));
PopStack(TextStack);
printf("出栈之后剩余元素个数：%d\n",GetSizeStack(TextStack));
printf("当前栈顶元素为：%d ",GetTopStack(TextStack));
PopStack(TextStack);
printf("出栈之后剩余元素个数：%d\n",GetSizeStack(TextStack));
//判断栈是否为空
printf("全部出栈之后栈是否为空（1代表为空，0代表不为空）：%d\n",IsEmptyStack(TextStack));
//再次入栈
PushStack(TextStack,98);
PushStack(TextStack,99);
PushStack(TextStack,100);
//测试清空栈
EmptyStack(TextStack);
printf("再次入栈清空栈之后栈是否为空（1代表为空，0代表不为空）：%d\n",IsEmptyStack(TextStack));
return 0;
}
测试结果显示：
栈的应用
（1）用栈实现逆波兰表达式
（2）进制转换
（3）括号匹配
（4）迷宫路径搜寻
还有很多应用就不一一列举了。