目录
🛰️博客主页：✈️銮同学的干货分享基地
🛰️欢迎关注：👍点赞🙌收藏✍️留言
🛰️系列专栏：🎈 数据结构
🎈 C语言学习
🛰️代码仓库：🎉数据结构仓库
家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注，欢迎你们的私信提问，感谢你们的转发！
关注我，关注我，关注我，你们将会看到更多的优质内容！！
🏡🏡 本文重点 🏡🏡：
🚅 栈的概念与结构 🚃 栈各接口功能实现 🚏🚏
🍊前言🍊：
前面我们学习了顺序表与链表的相关知识，也实现了它们各自的所有常用功能接口，理清了二者的使用差异和适用条件，而今天我们就将进入下一部分关于 栈（stack） 的研究之中。
🥝一.栈的概述🥝：
1.栈的概念：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
- 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈：栈的插入操作叫做进栈、入栈或压栈，入数据在栈顶。
- 出栈：栈的删除操作叫做出栈或退栈。出数据也在栈顶。
2.栈的结构：
🍉 二、栈的各接口功能实现🍉：
在这里銮崽以数组栈的实现为例为各位小伙伴们进行讲解。
1.栈的初始化：
- 初始化前需进行非空判断，防止对空指针进行操作。
- 确认非空后将所有元素置为初始值即可。
- Top 的值可以为 0 也可以为 -1 ，区别在于：为 0 表示 Top 指向栈顶数据的下一个数据；而 -1 表示 Top 指向栈顶数据。
2.压栈：
- 执行操作前进行非空判断，防止对空指针进行操作。
- 还要对栈空间进行判断，若栈内 top = capacity ，则说明此时已经存满，于是需要进行扩容操作。
- 扩容操作注意考虑首次扩容，即栈内容为空时的特殊情况，这里使用了三目操作符，首次扩容时使内存扩容为一个数据的大小，即 SDataType 类型，为 4 字节，而其它数据在扩容时则扩容为原大小的二倍。
- 扩容完毕后判断是否扩容成功，扩容失败需要提示扩容错误并退出，防止出现不可预料的错误。扩容成功则将新申请来的空间赋给栈。
- 最后若达到压栈要求，则将数据存至栈顶，并使栈顶向后指一步。
3.出栈：
- 执行操作前需进行非空判断，防止对空指针进行操作。
- 删除栈顶数据，即数据出栈的操作则十分简单，只需将指向栈顶的指针前移一步即可，不过在进行前移时，要注意判断栈内是否还有数据元素，若没有数据则停止前移。
4.取栈顶数据：
- 执行操作前需要进行非空判断，防止对空指针进行操作。
- 同时需要判断栈内是否存在数据。
- 若判断结果非空，即栈内存在数据（可以获取到栈顶数据），则返回栈顶数据，否则打印提示“ 栈顶数据获取失败 ”。
5.计算栈内有效数据：
- 执行操作前需进行非空判断，防止对空指针进行操作。
- 判断栈数据有效后，直返回栈顶即可，即为栈内有效数据。
6.判断栈是否为空：
- 执行操作前需要进行非空判断，防止对空指针进行操作。
- 直接对栈顶数据进行判断即可，若栈顶数据为初始值 0 ，则说明栈内没有数据，为空，返回特征值 1，否则返回 0。
- 该接口甚至可以简化为：
7.栈的销毁：
- 执行操作前需进行非空判断，防止对空指针进行操作。
- 判断结果非空，即需要释放后，直接释放指针 p->a 并置空后，将栈顶数据 top 与有效数据数量 capacity 置为初始值 0 即可。
🍇三、所有接口完整代码🍇：
1.Stack.h：
-
#pragma once
-
-
#include<stdio.h>
-
#include<stdlib.h>
-
#include<assert.h>
-
-
typedef
int SDataType;
-
-
typedef
struct
Stack
-
{
-
SDataType* a;
-
int top;
//栈顶位置
-
int capacity;
//容量空间的大小
-
}ST;
-
-
void SInit(ST* p);
//栈的初始化
-
void SPush(ST* p, SDataType x);
//压栈
-
void SPop(ST* p);
//出栈
-
SDataType STop(ST* p);
//取栈顶数据
-
int SSize(ST* p);
//计算栈内有效数据数量
-
int SEmpty(ST* p);
//判断栈是否为空
-
void SDestroy(ST* p);
//栈的销毁
2.Stack.c：
-
#define _CRT_SECURE_NO_WARNINGS 1
-
-
#include"Stack.h"
-
-
//栈的初始化：
-
void SInit(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
return;
-
}
-
p->a =
NULL;
-
p->top =
0;
//也可以是-1
-
p->capacity =
0;
-
}
-
-
//压栈：
-
void SPush(ST* p, SDataType x)
-
{
-
if (p ==
NULL)
-
{
-
return;
-
}
-
//判断是否存满:
-
if (p->top == p->capacity)
-
{
-
//动态开辟：
-
int NewCapacity = (p->capacity ==
0) ?
4 : (p->capacity *
2);
-
SDataType* tmp =
realloc(p->a,
sizeof(SDataType) * NewCapacity);
-
//判断是否开辟成功：
-
if (tmp ==
NULL)
-
{
-
printf(
"Realloc fail\n");
-
exit;
-
}
-
else
-
{
-
p->a = tmp;
-
p->capacity = NewCapacity;
-
}
-
}
-
//达到压栈要求，执行压栈操作：
-
p->a[p->top] = x;
-
p->top++;
-
}
-
-
//出栈：
-
void SPop(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
return;
-
}
-
if (p->top >
0)
-
{
-
p->top--;
-
}
-
}
-
-
//取栈顶数据：
-
SDataType STop(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
printf(
"StsckTop get fail\n");
-
exit;
-
}
-
if (p->top >
0)
-
{
-
return p->a[p->top -
1];
-
}
-
}
-
-
//计算栈内有效数据数量：
-
int SSize(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
printf(
"StsckSize get fail\n");
-
exit;
-
}
-
return p->top;
-
}
-
-
//判断栈是否为空：
-
int SEmpty(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
printf(
"StsckEmpty get fail\n");
-
exit;
-
}
-
if (p->top ==
0)
-
{
-
return
1;
-
}
-
else
-
{
-
return
0;
-
}
-
}
-
-
//判断非空可以简化为：
-
int SEmpty(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
printf(
"StsckEmpty get fail\n");
-
exit;
-
}
-
return p->top ==
0;
-
}
-
-
//栈的销毁：
-
void SDestroy(ST* p)
-
{
-
if (p ==
NULL)
-
{
-
return;
-
}
-
free(p->a);
-
p->a =
NULL;
-
p->capacity = p->top =
0;
-
}
3.test.c：
-
#define _CRT_SECURE_NO_WARNINGS 1
-
-
#include"Stack.h"
-
-
void StackTest()
-
{
-
ST st;
-
//初始化栈：
-
SInit(&st);
-
//压栈：
-
SPush(&st,
1);
-
SPush(&st,
2);
-
SPush(&st,
3);
-
SPush(&st,
4);
-
//出栈：
-
SPop(&st);
-
SPop(&st);
-
//获取栈顶数据：
-
printf(
"Top Data = %d\n",
STop(&st));
-
//获取有效数据个数：
-
printf(
"Here are %d data in the stack\n",
SSize(&st));
-
//判断栈内是否为空：
-
int ret =
SEmpty(&st);
-
if (ret)
-
{
-
printf(
"NULL\n");
-
}
-
else
-
{
-
printf(
"NOT NULL\n");
-
}
-
//销毁栈：
-
SDestroy(&st);
-
}
-
-
int main()
-
{
-
StackTest();
-
-
return
0;
-
}
🍒总结🍒：
今天銮崽就以数组栈为例，较全面的向各位小伙伴们展示并讲解了栈的概念、结构与各接口的实现过程与作用原理，各位小伙伴们下去以后最好能够再抽出一些时间，自己动动手，尝试一下栈各个接口的实现，帮助自己更好的理解和使用栈的相关操作。
🔥🔥眼里有不朽的光芒，心里有永恒的希望🔥🔥
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
转载：https://blog.csdn.net/weixin_59392935/article/details/128742808
查看评论