🔥个人主页：@草莓熊Lotso
🎬作者简介：C++研发方向学习者
📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》
⭐️人生格言：生活是默默的坚持，毅力是永久的享受。
前言： 前面我们学习完了顺序表和链表，那么接下来我们会继续学习栈和队列的知识，还是和之前一样会完全实现一遍，有了前面的基础其实栈和队列的实现会轻松很多的
目录
一.栈的概念和结构
--栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
我们可以把栈的结构想成水杯，杯底是封闭的，接水和倒水都在杯顶
--我们栈的实现一般可以使用数据或者链表实现，相对而言数组的结构实现更优一些。我们将数组的尾部作为栈顶，数组首部作为栈底，数组的尾部操作时间复杂度都是O(1)。其实链表使用头部操作也可以，但是综合空间来说使用数组更优一点
--我们先来看下栈的结构的定义
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;
int capacity;
}ST;二.栈的初始化和销毁
初始化：
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}销毁：
//销毁
void STDestory(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}重点提示：
栈的创建和销毁都是跟顺序表差不多的，没有很大的区别，为了区分我们把size这里定义的是top
三.栈的入栈和出栈
--栈的入栈和出栈操作我们实现起来也都很简单，我们直接来看看吧
入栈：
void STPush(ST* ps, STDataType x)
{
assert(ps);
//检查空间
//空间不够就增容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}看到这些代码，大家应该都不会很陌生，跟顺序表一样，空间足够直接尾部插入一个数据，top++，空间不够就扩容，扩容操作和顺序表是一模一样，不是很了解的可以看下博主前面顺序表实现的博客
--在实现出栈之前，我们先要实现一个判空操作的接口
//判空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}如果top为0，就证明了栈为空
出栈：
//出栈
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}栈不为空，就直接ps->top--就ok了，不需要其它的操作，实现起来很方便
四.取栈顶元素和获取栈中有效元素个数
--取栈顶元素实现了之后，我们就可以在test.c中实现取栈顶元素，打印再出栈的操作了，可以观察一下我们栈的先进后出特性
取栈顶元素：
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];;
}注意这里取出来的一定是下标为ps->top-1的元素
test.c：
#include"stack.h"
void test1()
{
ST ps;
STInit(&ps);
//入栈
STPush(&ps, 1);
STPush(&ps, 2);
STPush(&ps, 3);
STPush(&ps, 4);
while (!STEmpty(&ps))
{
//取栈顶元素，打印
STDataType top = STTop(&ps);
printf("%d ", top);
//出栈
STPop(&ps);
}
printf("\n");
//销毁
STDestory(&ps);
}
int main()
{
test1();
}--测试完成，打印没有问题，先进的后出，退出码为0
获取栈中元素个数：
//求栈中有效数据个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}这个实现起来也是非常简单了，直接返回ps->top刚好就是有效元素个数
五.代码展现
Stack.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestory(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//判空
bool STEmpty(ST* ps);
//求栈中有效数据个数
int STSize(ST* ps);
Stack.c：
#include"stack.h"
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void STDestory(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{
assert(ps);
//检查空间
//空间不够就增容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}
//判空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];;
}
//求栈中有效数据个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
test.c：
#include"stack.h"
void test1()
{
ST ps;
STInit(&ps);
//入栈
STPush(&ps, 1);
STPush(&ps, 2);
STPush(&ps, 3);
STPush(&ps, 4);
while (!STEmpty(&ps))
{
//取栈顶元素，打印
STDataType top = STTop(&ps);
printf("%d ", top);
//出栈
STPop(&ps);
}
printf("\n");
//销毁
STDestory(&ps);
}
int main()
{
test1();
}往期回顾：
结语：这篇博客我们完成了栈这个数据结构的实现，大家可以发现，有了前面的基础我们再来实现起来简直就是如鱼得水，很顺畅。那么我们在下篇博客中会继续队列这个数据结构的实现，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持