😘个人主页：@Cx330❀
👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生
📖个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》
前言：在之前几篇博客中，我们学习了顺序表和链表，接下来我们将学习栈的相关知识，希望大家继续坚持下去🌹🌹🌹
目录
一、栈的概念与结构
二、栈的初始化和销毁
注意事项：
三、、入栈
四、出栈
五、取栈顶元素
注意事项：
测试结果：
六、获取栈中元素个数
七、全部代码实现
Stack.h：
Stack.c：
test.c：
一、栈的概念与结构
栈：⼀种特殊的线性表，其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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;
}往期回顾：
【数据结构初阶】--双向链表（一）
【数据结构初阶】--双向链表（二）
总结：这篇博客带着给大家实现了栈的全部接口了，其实可以看出来栈的结构很简单，但是大家不能眼高手低，下去一定要自己画图操作，那么下篇博客将带着大家实现队列，大家敬请期待！如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持🌹🌹🌹
