《数据结构》第十四篇、栈

怒火攻心-高压电.jpg

引言

hello各位小伙伴,我还在,这一周真是累到吐血,每天都二三点才睡,早上7点又得爬起来上班。。。

不过,总算熬过来了,这一周终于有时间可以更新咯,至于java中的HashSet,HashMap等源码还没有进行解析,咱们别急,我抽空更。。。

今天给大家带来的是数据结构之

不过,由于篇幅原因,今天的文章仅仅是上篇,如果估计没错的话,还有中篇、下篇等着呢,哈哈哈,大家有空时候瞅一眼就好了。

1、什么是栈

洗碗时,将洗好的碗一个叠着一个摆放到柜子中;

用碗时,再讲碗逐个取下来

恩,通常来说,摆放碗时是由下而上依次放置,而取碗时,则是从上到下依次取出。这些都是生活中的常理,这样的顺序,如果用我们的术语说的话,就是碗的取出的原则称为“后进先出”,即最后放的碗在取出的时候是先被取出来的。

“后进先出”记住这个术语

在各种数据结构中,栈 (stack)这个数据结构就遵循这个原则。

栈也是一种线性表,但是他是收到限制的线性表,我们在前边学到的顺序表,链表中,我们可以在他们的两端进行插入,删除操作,而栈呢,他只允许在一端进行插入和删除的操作,正如下图所示

栈的结构示意图.png

如图所示,图中,有栈顶和栈底,

栈顶:栈中允许执行插入和删除操作的一端称为栈顶

栈底:栈中不允许执行插入和删除操作的一端称为栈底

入栈、压栈

向一个栈中插入新元素称之为入栈、压栈

入栈之后,该元素被放在栈顶元素的上边,成为新的栈顶元素。

执行入栈操作时,会先将元素插入到栈中,然后按照数据入栈的先后顺序,从下往上依次排列。

每当插入新的元素时,栈顶指针就会向上移动,指向新插入的元素。

当栈已满时,不能继续执行入栈操作。

出栈、弹栈

从一个栈中删除元素又称之为出栈、弹栈

把栈顶元素删除,使其下面的相邻元素成为新的栈顶元素

执行出栈操作时,栈顶元素会先被弹出,接着按照后进先出的原则将栈中的元素依次弹出,。

弹出栈顶元素后,栈顶指针就会向下移动,指向原来栈顶下面的元素,这个元素就成为了新的栈顶元素。

当栈为空时,不能继续执行出栈操作。

注意

如果要从栈中获取元素,只能通过栈顶指针取到栈顶元素,然后依次取出,除此之外没有别的方式。正如上图所示,如果栈顶元素an没有弹出时,an下边的元素是不能取到的。

由于栈遵循后进先出(Last In First Out,LIFO)原则,因此又把栈称为后进先出表

栈的常用操作如下:

进栈、出栈相当于线性表中的插入和删除操作,两者不同的是,栈顶是栈读取、插入的唯一出入口。

2、栈的实现

栈也是线性表,因此线性表的存储结构对栈也适用,栈也分为

顺序栈

链栈

两种存储结构。存储结构的不同使得实现栈的基本算法也有所不同。

2.1.1栈的顺序存储实现

栈的顺序存储也称为顺序栈,他利用一组地址连续的存储单元依次存放自栈底到栈顶的元素,同时设置栈顶标识top来指示栈顶元素在顺序栈中的位置。向顺序栈中插入元素时,其过程如下图所示:

向顺序栈中插入元素.png

如上图所示,向栈中插入元素时,需先使top指针指向栈顶上面的空位,然后再进行赋值

删除栈中元素时,只将top指针向下移动,指向新的栈顶元素,删除过程如下图所示

顺序栈弹栈.png

由上图我们知道,弹栈是将top指针移动,指向新的栈顶位置,原来的栈顶元素依然存在于存储单元中,但是无法通过栈进行访问。

注意,我们介绍栈的时候画的是上下结构的,现在画的是水平结构的,这个只是表示形式,并不是栈真实的结构,真实的结构就是一堆内存地址,更表现形式没关系,知道这点就行了。

学习完栈的入栈,弹栈,原理后,下面通过代码实现了一个顺序栈,这个顺序栈所具备的功能如下:

请看下方代码

seqstack.h(头文件):

seqstack.c(函数实现文件)

下面是测试文件

main.c

2.1.2栈的链式存储实现

栈的链式存储也称为链栈,他和链表的存储原理一样,多可以利用闲散的空间来存储元素,用指针来建立个结点之间的逻辑关系。

链栈也会设置一个栈顶元素的标识符top,称为栈顶指针。

他和链表区别是,只能在一段进行各种操作,如下所示

链栈.png

如图所示,链栈就是一个单端操作的链表,他的插入、删除操作就是在链表的一端进行。

接下来,我们实现一个链栈,其功能如下:

然后,会在main.c中进行测试

代码如下

linkstack.h 头文件

linkstack.c 操作函数实现文件

测试文件 main.c

总结

ok,看完了上面的两个例子,大家应该对顺序栈和链栈有了一个认识了吧,其实这些思想和顺序表和链表很相似,只不过出入口变成了一个,这些东西还得需要大家好好领悟,好好练习下本文中的代码哟。

持续更新,谢谢关注~~~

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180803G0L6X200?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券