栈--C语言实现数据结构

这篇具有很好参考价值的文章主要介绍了栈--C语言实现数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

本期带大家一起用C语言实现栈🌈🌈🌈

一、栈的概念🌎

栈是一种常见的数据结构,它遵循后进先出(Last In, First Out)的原则。可以将其类比为现实生活中的一摞书或者一叠盘子。

栈由一个连续的内存区域组成,可以存储一系列的元素。在栈的一端称为栈顶,另一端称为栈底。

栈的主要操作包括入栈(Push)和出栈(Pop):

入栈操作将元素放置在栈顶,新增加的元素成为新的栈顶。
出栈操作将栈顶的元素移除,并将其下面的元素成为新的栈顶。
由于栈的特性,只能访问、插入和删除栈顶元素,不支持在任意位置进行操作。

栈具有局部性原理,即后进入栈的元素会先被访问到,而先进入栈的元素则需要等待后面的元素出栈才能被访问到。

栈常用于函数调用、递归算法、表达式求值、括号匹配等场景。

二、栈的操作流程

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

三、栈的结构

栈的话,我们可以使用顺序栈链表栈来实现

1.对于顺序栈而言:
方便的便是尾删和尾插了,因为有记录了下标,那么便可以很快的访问到最后一个元素 ,不需要经过遍历
栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习
2.对于链表栈而言:
对于链表而言,尤其是 单链表,尾部的插入删除是很麻烦的。但是 单链表 的头插和头删就很方便,所以可以把 单链表的头部 作为栈顶,单链表的尾部 作为 栈底。 插入数据的时候我们需要选择头插数据
栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

如果对于双向链表而言,那么就是随便选了,毕竟双向链表无论哪头插入删除数据都很方便

那么对于 顺序栈链式栈 ,那个更加好呢?那必定是 顺序栈,因为使用顺序栈的 尾插尾删非常方便, 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单,所以我们接下来就实现 顺序栈

四、栈的实现

4.1 结构设计

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;     //栈顶元素的下一个  或者 栈顶的下标
	int capacity;
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时,top可以表示 栈顶的下一个位置的下标 或 栈顶下标

1.当 top = 0,top 表示栈顶的下一个位置的下标:
栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

top一开始等于0的时候,先压栈,top再++

2、当top=-1的时候,top 表示栈顶元素的下标:

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

top=-1的时候,++top,再压栈

4.2 初始化栈

因为我们实现的是顺序栈,因此和顺序表的初始化是一样的
我们创建一个ST s,然后传s的地址即可

void STInit(ST* ps)
{

	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}

这里我们将top置为0,表示下一个数据的下标

4.3压栈

压栈的话,我们需要判断一下我们的我们的容量capacity是否和我们的ttop相等
如果相等的话,那么就扩容操作

void STPush(ST* ps,STDataType x)
{

	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));

		if (tmp == NULL)
		{
			perror("realloc :fail");
			return;
		}

		ps->a = tmp;

		ps->capacity = newcapacity;

	}
	ps->a[ps->top++] = x;

}

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

4.4 出栈

出栈的话是很简单的,只需要将我们的top--就可以了
不过需要注意的是,如果我们的栈为空的话,那我们就不进行出栈操作

void STPop(ST* ps)
{

	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

4.5 获取栈顶元素

获取栈顶元素的话,我们同样需要判断栈是否为空
如果为空的话,那我们就不去获取栈顶元素的操作
如果不为空,那我们返回下标为top-1那个元素

STDataType STTop(ST* ps)
{

	assert(ps);

	return ps->a[ps->top - 1];

}

4.6 栈中数据的个数

栈中数据个数的话比较简单,只需要返回我们的top即可

int STSize(ST* ps)
{
	assert(ps);

	return  ps->top;

}

4.7 判断栈是否为空

判断栈是否为空的话,我们只需要返回top==0的真假就行

bool STEmpty(ST* ps)
{

	return ps->top == 0;
}

4.8 栈的销毁

对于栈的销毁,那么我们就只需要释放动态开辟的空间,将指针置空。并将 capacity 和 top 两个变量置 0即可

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;

	ps->top = 0;
}

5、有效的括号

链接:有效的括号
栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习
看完题目之后,我们可以有以下的思路
我们可以让左括号压栈
当我们遇到右括号的时候,如果我们的栈不为空的话,我们就拿栈顶的元素去和右括号比较,如果括号不匹配的话,我们先销毁一下我们的栈,然后再去返回false
如果我们的栈为空的话,那我们就先销毁一下我们的栈,然后直接返回false
当然当我们的括号匹配的时候,我们就让s➕➕和删去栈顶元素,然后再去进行下一轮的判断
当我们的括号全部匹配完了之后,如果我们的栈不为空的话,我们就返回false,不然就反回true,并且销毁栈

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习
易错点:
遍历结束,栈不为空
栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习

6. 感谢与交流✅

🌹🌹🌹如果大家通过本篇博客收获了,对顺序表有了新的了解的话
那么希望支持一下哦如果还有不明白的,疑惑的话,或者什么比较好的建议的话,可以发到评论区,
我们一起解决,共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯

栈--C语言实现数据结构,数据结构,c语言,数据结构,算法,学习文章来源地址https://www.toymoban.com/news/detail-562697.html

到了这里,关于栈--C语言实现数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包