🎬 鸽芷咕:个人主页 🔥个人专栏:《Linux深造日志》《C++干货基地》
⛺️生活的理想,就是为了理想的生活!
🌈hello! 各位铁铁们大家好啊,今天来给大家更新一下栈这个数据结构,栈实际上是实现一种后进先出效果。 ⛳️一般我们在C语言学习期间函数开辟的空间就是在栈区,那么我们今天就来领略一下栈的风采吧! 📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐! ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!
栈:其实是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元素遵守后进先出 LIFO(Last In First Out)
的原则。
具体我们可以看一下图片来了解了解,其实栈有点类似堆砖块。想拿到最下面的砖块必须要把上面的都拿走才可以拿到。
既然栈实现的是后进先出的方法,那么我们选用顺序表,还是链表来实现呢? 答案肯定是数组啦。
-1
,就好了效率不知道比链表快了多少倍既然选择好了使用什么类型来实现栈那么接下来就是先定义栈的结构:
指针
来开空间capacity
来记录容量📚 代码演示:
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
入栈要注意的是考虑好边界情况:
📚 代码演示:
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
// 11:40
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
出栈就很简单这个也是,顺序表实现栈表的好处:
top--
就好了不需要去真正的删除数据📚 代码演示:
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
//
assert(ps->top > 0);
--ps->top;
}
获取栈顶元素也非常简单,前面我们定义了一个 top 这时候就可以派上用场了:
ps->a[top]
,就可以一键获取了📚 代码演示:
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
//
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
这个也是一样,贼简单直接 ps->top
就是栈区数据的个数:
📚 代码演示:
// 获取栈中有效元素个数
int StackSize(Stack* ps);
{
assert(ps);
return ps->top;
}
栈的判空这个如何实现呢?是不是只要 ps->top == 0
就是空了呢?
📚 代码演示:
// 检测栈是否为空,如果为空返回真,如果不为空返回假
bool StackEmpty(Stack* ps);
{
assert(ps);
return ps->top == 0;
}
销毁现在对于我们已经是轻车熟路了,free( )
掉动态开辟的空间,在 free( )
掉栈就好了;
📚 代码演示:
// 销毁栈
void StackDestroy(Stack* ps)
{
free(ps->a);
free(ps);
}
☁️ 好了以上就是栈的实现了,总的来说还是很简单的一会就写完了。大家不要忘记练习哦!
看到这里了还不给博主扣个:
⛳️ 点赞
☀️收藏
⭐️ 关注
!
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。