🐸一、栈的概念及结构
🍄1、栈的概念定义
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
- 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈。出数据也在栈顶。
🍄2、动图演示
🌲入栈
🌲出栈
🌲整体过程
🐸二、栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小
🐸三、数组结构栈详解
🍎创建栈的结构
🥰这里先创建三个文件:
1️⃣:Stack.h文件,用于函数的声明
2️⃣:Stack.c文件,用于函数的定义
3️⃣:Test.c文件,用于测试函数
建立三个文件的目的: 将栈作为一个项目来进行编写,方便我们的学习与观察。
⭕接口1:定义结构体(ST)
🥰请看代码与注释👇
//自定义类型
typedef int STDataType;
//创建栈的结构
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
⭕接口2:初始化(STInit)
🥰请看代码与注释👇
//初始化
void STInit(ST* pst)
{
//断言传入指针不为NULL
assert(pst);
pst->a = NULL;
pst->top = -1; //top指向栈顶数据
pst->top = 0; //top 指向栈顶数据的下一个位置
pst->capacity = 0;
}
⭕接口3:销毁(STDestroy)
🥰请看代码与注释👇
//销毁
void STDestroy(ST* pst)
{
//断言传入指针不为NULL
assert(pst);
//释放
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
⭕接口4:入栈(STPush)
🥰请看代码与注释👇
//入栈
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* temp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (temp == NULL)
{
perror("realloc fail");
return;
}
pst->a = temp;
pst->capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
⭕接口5:出栈(STPop)
🥰请看代码与注释👇
//出栈
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
⭕接口6:取栈顶数据(STTop)
🥰请看代码与注释👇
//取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
⭕接口7:判空(STEmpty)
🥰请看代码与注释👇
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
⭕接口8:获取栈的大小(STSize)
🥰请看代码与注释👇
//获取栈的大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
🐸四、完整代码
🥝Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//取栈顶数据
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈的大小
int STSize(ST* pst);
🥝Stack.c
#include"Stack.h"
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = -1; //top指向栈顶数据
pst->top = 0; //top 指向栈顶数据的下一个位置
pst->capacity = 0;
}
//销毁
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* temp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (temp == NULL)
{
perror("realloc fail");
return;
}
pst->a = temp;
pst->capacity = newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
//出栈
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
//取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
//获取栈的大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
🥝Test.c
#include"Stack.h"
//入栈测试
void TestStack1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));
STPop(&st);
}
STDestroy(&st);
}
//测试
void TestStack2()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
printf("%d ", STTop(&st));
STPop(&st);
STPush(&st, 3);
STPush(&st, 4);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));
STPop(&st);
}
STDestroy(&st);
}
int main()
{
//TestStack1();
//TestStack2();
return 0;
}
🥰这期内容相对比较简单,希望烙铁们可以理解消化哦!文章来源:https://www.toymoban.com/news/detail-691211.html
总结🥰
以上就是 【数据结构】栈—C语言版 的全部内容啦🥳🥳🥳🥳
本文章所在【数据结构与算法】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰
文章来源地址https://www.toymoban.com/news/detail-691211.html
到了这里,关于【数据结构】栈---C语言版(详解!!!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!