初阶数据结构(五) 栈的介绍与实现

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

💓博主csdn个人主页:小小unicorn💓
⏩专栏分类:C++

🚚代码仓库:小小unicorn的学习足迹🚚
🌹🌹🌹关注我带你学习编程知识

栈的介绍

栈的概念

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈 / 压栈 / 入栈。(入数据在栈顶)

出栈:栈的删除操作叫做出栈。(出数据也在栈顶)

理解栈的定义需要注意:
首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表7 尾是指栈顶,而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。

栈的插入操作,叫作进栈,也称压栈、入栈。类似子弹入弹夹,如左下图所示。

栈的删除操作,叫作出栈,有的也叫作弹栈。如同弹夹中的子弹出夹,如右下图所示。

初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深

栈的结构

首先观看下面的动图,对栈概念进一步的加深理解。

初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深

栈的实现

初始化栈

首先,我们需要用结构体创建一个栈,这个结构体需要包括栈的基本内容(栈,栈顶,栈的容量

//栈中存储的元素类型(这里用整型举例)
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;          //栈
	int top;               //栈顶  
	int capacity;          //容量,方便增容
}Stack;


初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深
然后呢,我们需要一个初始化函数,对刚创建的栈进行初始化。

//初始化栈
void StackInit(Stack* pst)
{

	assert(pst);

	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);  //初始化栈可存储4个元素
	pst->top = 0;                                        //初始时栈中无元素,栈顶为0
	pst->capacity = 4;                                   //容量为4
}



}


销毁栈

前面栈的空间是我们自己动态开辟出来的,当我们使用完后必须释放其内存空间,防止内存泄漏。

//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	free(pst->a);              //释放栈
	pst->a = NULL;            //及时置空
	pst->top = 0;             //栈顶置0
	pst->capacity = 0;        //容量置0
}


入栈

进行入栈操作前,我们首先需要检测栈的当前状态,若已满,则需要先对其进行增容,然后才能进行入栈操作。

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)                          //栈已满,需扩容
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity *= 2;                              //栈容量扩大为原来的两倍
	}
	pst->a[pst->top] = x;                                //栈顶位置存放元素x
	pst->top++;                                          //栈顶上移
}

出栈

出栈操作比较简单,即让栈顶的位置向下移动一位即可。但需检测栈是否为空,若为空,则不能进行出栈操作。

//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));                      //检测栈是否为空

	pst->top--;                                   //栈顶下移
}

获取栈顶元素

获取栈顶元素,即获取栈的最上方的元素。若栈为空,则不能获取。

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));                    //检测栈是否为空

	return pst->a[pst->top - 1];                 //返回栈顶元素
}

检测栈是否为空

检测栈是否为空,即判断栈顶的位置是否是0即可。若栈顶是0,则栈为空。

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

获取栈中有效元素个数

因为top记录的是栈顶,使用top的值便代表栈中有效元素的个数。

//获取栈中有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;                   //top的值便是栈中有效元素的个数
}

栈的作用:

有人可能就产生疑问了,用数组或者链表直接实现功能不就行了吗?干嘛还要引入栈这样的数据结构呢?

回答这个问题,就好比:其实这和我们明明可以有两只脚走路,干嘛还要乘坐汽车,火车,飞机性质一样。理论上,陆地上的任何地方,我们都是可以靠双脚走到的,可那需要耗费的时间和精力可想而知。我们更关注的是到达而不是如何去的过程。

栈的引入可以简化程序设计的问题,划分了不同关注层次,使得思考范围缩小,更利于解决问题核心。

栈的应用-------递归:

栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?
当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子对着一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个“化身”。为什么会有这么奇妙的现象呢?原来,A镜子里有B镜子的像,B镜子里也有A镜子的像,这样反反复复,就会产生一连串的“像中像”。这是一种递归现象,如下图所示。
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深

我们先来看一个经典的递归例子:斐波那契数列(Fibonacci)。为了说明这个数列,这位斐老还举了一个很形象的例子。

斐波那契数列的实现:

斐老说如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。假设所有兔子都不死,那么一年以后可以繁殖多少对兔子呢?

我们拿新出生的一对小兔子分析一下:第一个月小兔子没有繁殖能力,所以还是一对;两个月后,生下一对小兔子共有两对;三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对……以此类推可以列出下表。
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深
表中数字1,1,2,3,5,8,13,…构成了一个序列。这个是咧有个十分明显的特点,那就是:前面向量两项之和,构成了后一项。如下图所示:
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深
会发现,编号1的一对兔子经过6个月就变成8对兔子了,如果用数学函数公式来定义的话,那就是:
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深
思考一下,如果我们要实现这样的数列用常规迭代方法如何操作。以前40位的斐波那契数列为例。

//前40位
int main()
{
	int i;
	int a[40] = { 0 };
	a[0] = 0;
	a[1] = 1;
	printf("0:%d\n", a[0]);
	printf("1:%d\n", a[1]);
	for (i = 2; i < 40; i++)
	{
		a[i] = a[i - 1] + a[i - 2];
		printf("%d:%d\n", i,a[i]);

	}
	return 0;
}

看看结果:
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深
用递归实现的话:

//斐波那契递归实现:
int Fbi(int i)
{
	if (i < 2)
	{
		return i == 0 ? 0 : 1;
	}
	return Fbi(i - 1) + Fbi(i - 2);
}

int main()
{

	int i;
	printf("递归显示斐波那契数列:\n");
	for (i = 0; i < 40; i++)
	{
		printf("%d:%d\n",i, Fbi(i));
	}

	return 0;
}

看下结果:
初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深

通过比较发现,明显递归版的代码干净很多。这就是递归,估计有人难以理解,函数怎么可以自己调用自己?我们可以换种思路,它调用函数时调用的函数跟它本身一样。

我们可以模拟一下Fbi(5)具体是怎么实现的。

初阶数据结构(五) 栈的介绍与实现,c++,c语言,数据结构,c语言,算法,迭代加深

递归的定义:

在高级语言中,调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。

当然,写递归程序最怕的就是陷入永不结束的无穷递归中,所以,每个递归定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而是返回值退出。

比如刚才的例子,总有一次递归会使得i<2的,这样就可以执行return i的语句而不用继续递归了。

对比了两种实现斐波那契的代码。迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

那么我们讲了这么多递归的内容,和栈有什么关系呢?这得从计算机系统的内部说起

前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符合栈这样的数据结构,因此,编译器使用栈实现递归就没什么惊奇的了。

简单地说,就是在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

当然,对于现在的高级语言,这样的递归问题是不需要用户来管理这个栈的,一切都由系统代劳了。

文章到这里就要告一段落了,有更好的思路或问题的,欢迎留言评论区。
下棋预告:初阶数据结构(六) 队列的介绍与实现文章来源地址https://www.toymoban.com/news/detail-675754.html

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

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

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

相关文章

  • 数据结构-栈的实现(C语言版)

    前言         栈是一种特殊的线性表,只允许在固定的一端进行插入和删除的操作, 进行数据插入和删除的一端叫做栈顶,另一端叫做栈底。  栈中的数据元素遵循后进先出的的原则。 目录 1.压栈和出栈 2. 栈的实现 3.测试代码         压栈:栈的插入操作叫 压栈,入数

    2024年02月13日
    浏览(49)
  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(60)
  • 初阶数据结构(六)队列的介绍与实现

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFO(First In First Out)的原则。 入队列:队列的

    2024年02月11日
    浏览(40)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(80)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(39)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(44)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(43)
  • Leetcode刷题---C语言实现初阶数据结构---单链表

    删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [ ], val = 1 输出:[ ] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月15日
    浏览(51)
  • 数据结构初阶之基础二叉树(C语言实现)

    📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月,独傲天下百坚强。 男儿应有龙腾志,盖世一意转洪荒。 莫使此生无痕度,终归人间一捧黄。🍎🍎🍎 ❤️ 什么

    2024年03月19日
    浏览(43)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包