目录

• 栈的概念
• 栈的结构声明
• 初始化
• 数据入栈
• 出栈
• 判断栈是否为空
• 取栈顶的值
• 销毁栈

栈的概念

栈是一种线性表，插入数据的一端叫栈顶，另一端叫栈底。
入栈：数据从栈顶进入栈中
出栈：数据从栈顶删除
所以，栈的特点就是先进后出，也可以说后进先出。

入栈图

出栈图

根据栈先进后出的性质，我们来实现一个简单的栈。

栈的结构声明

typedef int STDataType;struct Stack
{//存放数据的空间STDataType* data;//栈顶位置size_t top;//栈的容量size_t Cacpcity;
}ST;

初始化

初始化很简单，我们让data指向的空间为NULL,顶部位置从0开始，每插入一个数据就+1。

//初始化
void StackInto(ST* ST)
{ST->data = NULL;ST->top = 0;ST->Cacpcity = 0;
}

我们可以看到初始化成功了。

数据入栈

栈初始化好后，我们就要把数据插入栈中，因为是先进后出，所以我们直接在数组尾部插入即可。

//容量更新
void CheckCacpcity(ST* ST)
{//容量等于top时，说明数组没有空间了if (ST->Cacpcity == ST->top){//如果空间为0，初始空间4，如果不为0，空间*2int NewCacpcity = ST->Cacpcity == 0 ? 4 : ST->Cacpcity * 2;//扩容STDataType* newdata = (STDataType*)realloc(ST->data,sizeof(STDataType) * NewCacpcity);//扩容是否成功if (newdata == NULL){printf("reallo fail\n");exit(-1);}ST->data = newdata;//更新容量ST->Cacpcity = NewCacpcity;}
}//数据入栈
void StackPush(ST* ST, STDataType x)
{//断言，传进来的指针不能为空assert(ST);//容量不够自动增容CheckCacpcity(ST);//尾部数据入栈*(ST->data+ST->top) = x;ST->top++;
}

然后我们发现数据入栈。并且容量更新了。

出栈

因为栈是后进来的先出去，所以直接删除最后一个元素即可。

//数据出栈
void StackPop(ST* ST)
{assert(ST);//如果top等于0，说明没有元素了assert(ST->top > 0);//出栈操作，就是这么简单ST->top--;}

判断栈是否为空

直接判断top的值是否为0即可，返回真即为空。

//栈是否为空
bool StackEmpty(ST* ST)
{assert(ST);return ST->top == 0;
}

取栈顶的值

同样很简单，top-1的值就是栈顶的值，但是要注意栈必须不为空。

//取栈顶的值
STDataType StackTop(ST* ST)
{assert(ST);assert(!StackEmpty(ST));return ST->data[ST->top - 1];
}

入栈的顺序是1 2 3 4 5 ，出栈的顺序是 5 4 3 2 1

销毁栈

这个也简单，top和capacity置为0，释放掉data，指针置为空即可。

//销毁
void StackDestroy(ST* ST)
{assert(ST);ST->top = ST->Cacpcity = 0;free(ST->data);ST->data = NULL;
}

销毁成功。
代码已上传至git