目录
一、栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
后进先出示意图
后进先出步骤分解
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。
2.1 头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.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);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);我们在创建栈时，一般是创建支持动态增长的栈，定长的静态栈不实用。这里的top就相当于是存储栈顶元素，capacity在入栈时为是否要增容提供判断条件。
2.2 各个功能的实现
初始化栈
void StackInit(Stack* ps)
{
ps->a = NULL;
ps->top = ps->capacity = 0;
}数组置空，栈顶数字和容量归0。
入栈
void StackPush(Stack* ps, STDataType data)
{
if (ps->top == ps->capacity)
{
int newcapacity =ps->capacity== 0 ? 4 : ps->capacity*2;
STDataType* tem = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
if (tem == NULL)
{
perror("realloc fail");
return;
}
ps->capacity = newcapacity;
ps->a = tem;
}
ps->a[ps->top++] = data;
}先判断容量是否有足够的空间让数据入栈，在第一次入栈是先给定4个空间，后面每次不够时就将空间数乘以2， 还有一个判断是否开辟成功（这个可以不写，一般都会开辟成功）。
出栈
void StackPop(Stack* ps)
{
assert(ps);
ps->top--;
}出栈非常的简单，只要将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;
}两个都是比较简单的代码，只要用top就可以知道栈顶元素和栈中的元素个数。
判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}栈中个数为0那么就是空栈，也是直接用到了top，。
栈的销毁
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}和初始化类似，数组置空，top和capacity归0。
2.3 测试
写完代码后还是需要测试的
int main()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
StackPush(&s, 5);
while (!StackEmpty(&s))
{
printf("%d\n", StackTop(&s));
StackPop(&s);
}
StackDestroy(&s);
}我这里就是先入栈五个元素，然后在一个循环中打印，每打印一个就将栈顶元素出栈，直到栈变为空栈结束打印。
完整源码
zhan.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.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);zhan.c
#include"zhan.h"
void StackInit(Stack* ps)
{
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{
if (ps->top == ps->capacity)
{
int newcapacity =ps->capacity== 0 ? 4 : ps->capacity*2;
STDataType* tem = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
if (tem == NULL)
{
perror("realloc fail");
return;
}
ps->capacity = newcapacity;
ps->a = tem;
}
ps->a[ps->top++] = data;
}
void StackPop(Stack* ps)
{
assert(ps);
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->capacity = 0;
ps->top = 0;
}最好是要自己写一遍，这样才能加深印象，也更能理解栈相关的知识。
本篇关于栈的内容就到这里了，希望对各位有帮助，如果有错误欢迎指出，感谢支持。
