👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生
前言：在之前几篇博客中，我们学习了顺序表和链表，接下来我们将学习栈的相关知识，希望大家继续坚持下去🌹🌹🌹
目录
一、栈的概念与结构
栈：⼀种特殊的线性表，其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据也在栈顶
栈战：栈的删除操作叫做出栈。出数据也在栈顶
例子：我们可以将栈想象为水杯，水杯的地步就是栈底，开口的地方就是栈顶，在水杯里面放石头，直到放满为止，先放进杯子的石头是最后才能拿出来的。
注意：栈的实现一般可以用数组或者链表来实现，但是相对而言数组的结构实现更优一些，将数组的尾部作为栈顶，数组的头部作为栈顶，插入删除数据的时间复杂度都为O(1)，但是链表使用头部也可以进行插入删除，时间复杂度也为O(1)，但是每次插入都会申请一个节点大小的空间，在空间上相对而言，数组的结构更加优秀
栈的结构：
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;//指向栈顶的位置--刚好就是栈中有效数据个数
int capacity;//栈的空间大小
}ST;二、栈的初始化和销毁
初始化：
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->capacity = ps->top = 0;
}销毁：
//销毁
void STDesTroy(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}注意事项：
这里的结构和顺序表几乎是一样的，但是为了区分size，这里我们使用top作为栈顶
三、、入栈
//入栈--栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->capacity == ps->top)
{
//增容
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;
}相信大家看到这些代码的时候并不陌生，这里的逻辑和顺序表几乎一模一样，当在栈中插入数据时，由于栈顶插入，所以要先判断栈的空间是否足够，若不够先增容，足够的话就将x赋给ps->arr[ps->top++]就可以了
四、出栈
在出栈之前首先要判断栈是否为空，若不为空才可以进行出栈操作，所以这里封装一个判空的接口
//栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//栈顶为0，栈就为空
}出栈：
//出栈--栈顶
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}栈不为空，直接让ps->top--就可以了，非常简单
五、取栈顶元素
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return ps->arr[ps->top-1];//易错top是空的，top-1才是栈顶元素
}注意事项：
这里要注意的是，top是栈顶，而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();
}测试结果：
六、获取栈中元素个数
//获取栈中有效数据个数
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 STDesTroy(ST* ps);
//入栈--栈顶
void STPush(ST* ps, STDataType x);
//栈是否为空
bool STEmpty(ST* ps);
//出栈--栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);Stack.c：
#include"stack.h"
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//销毁
void STDesTroy(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//入栈--栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->capacity == ps->top)
{
//增容
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];//易错top是空的，top-1才是栈顶元素
}
//获取栈中有效数据个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}test.c：
#include"stack.h"
void test01()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
printf("size:%d\n", STSize(&st));
while (!STEmpty(&st))
{
//取栈顶
STDataType top = STTop(&st);
printf("%d ", top);
//出栈
STPop(&st);
}
printf("\n");
STDesTroy(&st);
}
int main()
{
test01();
return 0;
}往期回顾：
总结：这篇博客带着给大家实现了栈的全部接口了，其实可以看出来栈的结构很简单，但是大家不能眼高手低，下去一定要自己画图操作，那么下篇博客将带着大家实现队列，大家敬请期待！如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持🌹🌹🌹