栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底,栈中的数据元素遵守 后进先出LIFO（Last In First Out） 的原则
由于栈后进先出的特点，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比小。实现类似于顺序表，结构包括一个数组指针，指向存储数据的数组，再就是一个指向栈顶的指针，因为压栈时如果栈满了需要动态开辟空间，所以这里还需要定义一个容量
重庆分公司
重庆分公司
//数据类型
typedef int STDataType;
//栈信息结构
typedef struct Stack
{STDataType* a;//数组
int top;// 初始为0，表示栈顶位置下一个位置的下标
int capacity;// 容量
}ST;图示：
将数组指针a置空，同时开辟出起始空间容量，并将栈顶初始化为0，这里栈顶也可以初始化为-1，如果初始化为0，取栈顶就是取下标为top-1位置处的元素，如果初始化为-1，取栈顶就是取的下标为top位置处的元素
//初始化栈
void StackInit(ST* ps)
{assert(ps);
//开辟起始空间
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)//判断开辟成功
{perror("malloc fail");
exit(-1);
}
ps->top = 0;
ps->capacity = 4;//初始容量
}根据前面的初始化，如果top指针在下标为0的位置栈就为空，返回其布尔值即可
//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);
//返回top指针是否在下标为0的位置
return ps->top == 0;
}首先要考虑扩容问题，避免空间不够还要压栈，这里断言ps是为了防止人为不小心传空，然后将数据放入下标为top的位置，再将top++后移一个位置即可，此时栈顶的下标top代表的就是栈中数据的个数
//压栈（入栈）
void StackPush(ST* ps, STDatatype x)
{assert(ps);
// 判断扩容
if (ps->top == ps->capacity)
{STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
if (tmp == NULL)//判断开辟成功
{ perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
//先将top位置放入数据，再将top++后移
ps->a[ps->top] = x;
ps->top++;
}首先断言栈为空的情况，栈空不能出栈，然后出栈操作只需要将top指针减一改变栈顶位置为原栈顶的下一个元素即可，这里不需要将原栈顶置零，后面再进行压栈操作时自然会将其覆盖掉
//出栈
void StackPop(ST* ps)
{assert(ps);
//断言栈为空
assert(!StackEmpty(ps));
//栈顶下标后移一位
ps->top--;
}首先断言栈为空的情况，栈为空无栈顶元素，然后将下标为top-1的栈顶元素返回即可
//查看栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);
//断言栈为空
assert(!StackEmpty(ps));
//返回栈顶元素
return ps->a[ps->top - 1];
}栈顶的下标top代表的就是栈中数据的个数,将其返回即可
//统计栈内元素个数
int StackSize(ST* ps)
{assert(ps);
//返回栈顶下标
return ps->top;
}销毁栈我们直接释放掉存储栈的数组，再将数组指针置空（避免野指针），最后将栈顶指针和容量置零即可
//销毁栈
void StackDestroy(ST* ps)
{assert(ps);
//释放数组
free(ps->a);
ps->a = NULL;//置空
ps->top = ps->capacity = 0;//置零
}栈的实现到这里就介绍结束了，期待大佬们的三连！你们的支持是我大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
