数据结构 | 栈

01 栈的定义

栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称 LIFO 结构。

从上面这两段话,可以确定:首先栈是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系,只不过它是一种特殊的线性表。定义中说在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。

栈的插入操作,叫做进栈,也叫压栈、入栈。

栈的删除操作,叫做出栈。

02

进栈出栈变化多端

最先进栈的元素,不一定是最后出栈的。

栈对线性表的插入和删除的位置进行了限制,并没有对元素进出的时间进行限制。意思就是说,当并非所有的元素都进栈的情况下,先进去的元素也可以出栈,只要保证栈顶元素出栈就可以了。

比如,现在有 3 个元素 1、2、3,可能的出栈顺序有下面几种:

  • 第一种:1、2、3 依次进栈,再 3、2、1依次出栈,显然出栈顺序为321。
  • 第二种:1 进栈,1 出栈,2 进栈,2 出栈,3 进栈,3 出栈。出栈顺序为 123。
  • 第三种:1 进栈,2 进栈,2 出栈,1 出栈,3 进栈,3 出栈。出栈顺序为 213。
  • 第四种:1 进栈,1 出栈,2 进栈,3 进栈,3 出栈,2 出栈。出栈顺序为 132。
  • 第五种:1 进栈,2 进栈,2 出栈,3 进栈,3 出栈,1 出栈。出栈顺序为 231。

03

栈的抽象数据类型

我们知道,栈是一个特殊的线性表,由于它的特殊性,所以与线性表的操作会略有不同。特别是插入和删除操作,我们分别叫它 push 和 pop。

栈的抽象数据类型

ADT 栈(stack) Data 同线性表,元素具有相同的类型,相邻元素具有前驱和后继关系。 Operation initStack(*S):初始化操作,建立一个空栈 S。 destroyStack(*S):若栈存在,则销毁它。 clearStack(*S):清空栈。 isEmpty(S):若栈为空返回 true,否则返回 false。 getTop(S, *e):若栈存在且非空,用 e 返回 S 的栈顶元素。 push(*S, e):若栈 S 存在,插入新元素 e 到栈 S 中并成为栈顶元素。 pop(*S, *e):删除栈顶元素,并且 e 返回其值。 length(S):返回栈 S 的元素个数。 endADT

由于栈本身就是一个线性表,所以线性表的顺序存储和链式存储对于栈来说,同样适用。

04

栈的顺序存储结构及实现

因为栈是线性表的特例,栈的顺序存储其实是线性表顺序存储的简化,简称为顺序栈。

线性表是用数组实现的,对于栈这种只能一端插入删除的线性表来说,下标为 0 的一端作为栈底比较好,因为首元素都存在栈底,变化最小。

我们定义一个变量 top 来指示栈顶元素在数组中的位置,若栈的长度为 stackSize,则栈顶位置 top 必须小于 stackSize。当栈中存在一个元素时,top 等于 0,因此把空栈的判定条件定为 top = -1。

栈的结构定义

define MAXSIZE = 10 typedef struct { int data[MAXSIZE]; int top; } SqStack;

进栈操作

boolean push(SqStack *s, int e) { if (s->top == MAXSIZE - 1) { return false; } s->top++; s->data[s->top] = e;

return true; }

出栈操作

若栈不为空,则删除栈顶元素,并把其值赋值给 e。

boolean pop(SqStac *s, int *e) { if (s->top == -1) return false; *e = s->data[s->top]; s->top--; return true; }

通过进栈和出栈操作的代码可以看出,时间复杂度都为 O(1)。

05

两栈共享空间

栈的顺序存储有一个很大的缺陷,必须先确定数组存储空间大小,而且万一不够用了,还要扩容。

对于一个栈,我们只能尽量考虑周全,设计出合适大小的数组来处理,但对于两个相同类型的栈,我们可以做到最大限度地利用事先开辟的存储空间来进行操作。

如果我们有两个相同类型的栈,我们为它们各自开辟了数组空间,有可能第一个栈已经满了,而另一个栈还有很多存储空间。我们完全可以用一个数组来存储两个栈。

我们知道,数组有两个端点,两个栈有两个栈底。可以让一个栈的栈底为数组的开始端,即下标为 0 处,另一个栈的栈底为数组的末端,即下标为数组长度 n - 1 处,这样两个栈如果增加元素,就是两端点向中间移动,如图所示。

两栈共享

top1 和 top2 是栈 1 和栈 2 的栈顶指针,只要二者的值不相等,两个栈就可以进行入栈操作。当 top1 等于 -1 时,栈 1 为空;当 top2等于 n 时,栈 2 为空。当 top2 - top1 = 1 时,栈就满了。

两栈共享空间的代码如下:

typedef struct { int data[MAXSIZE]; int top1; int top2; } SqDoubleStack;

对于两栈共享空间的插入方法,除了要插入元素值参数外,还需要有一个判断是栈 1 还是栈 2 的栈号参数。代码如下:

boolean push(SqDoubleStack *s, int e, int stackNumber) { if (s->top2 - s->top1 == 1) { /* 栈满 */ return false; } if (stackNumber == 1) { s->data[++s->top1] = e; } else if (stackNumber == 2) { s->data[--s->top2] = e; } return true; }

出栈方法的代码

boolean pop(SqDoubleStack *s, int *e, int stackNumber) { if (stackNumber == 1) { if (s->top1 == -1) return false; *e = s->data[s->top1--]; } else if (stackNumber == 2) { if (s->top2 == MAXSIZE) return false; *e = s->data[s->top2++]; } return true; }

两栈共享通常用于两个栈的空间需求具有相反关系时,也就是一个栈增长时另一个栈在缩短。就像买卖股票一样,一个人买入时,一定有另一个人在做卖出操作。这样使用两栈共享空间存储方法才有比较大的意义。

两栈共享只针对两个具有相同数据类型的栈。

06

栈的链式存储结构

栈的链式存储结构,简称为链栈。

由于单链表有头指针,而栈顶指针也是必须的,所以把栈顶放在链表的头部。另外,由于已经有了栈顶在头部,所以单链表中的头结点就不需要了。

对于链栈来说,基本不存在栈满的情况,因为只要内存有空间,链表就可以一直添加结点。

链栈的结构代码如下:

/** * Node结点 */ typedef struct StackNode { int data; struct StackNode *next; } StackNode, *pStackNode; typedef struct LinkStack { pStackNode top; /* 栈顶指针 */ int count; } LinkStack;

07

栈的链式存储结构—进栈操作

假设新结点 s 的值为 e,top 为栈顶指针,将 s->next 指向当前栈顶结点,栈元素个数加 1。

boolean push(LinkStack *s, int e) { pStackNode pNewNode = (pStackNode)malloc(sizeof(StackNode)); if (NULL == newNode) return false; pNewNode->data = e; /* 把当前栈顶元素赋值给新结点的直接后继 */ pNewNode->next = s->top; /* 新结点作为栈顶 */ s->top = pNewNode; s->count ++; return true; }

08

栈的链式存储—出栈操作

出栈的操作步骤:先用一个变量 p 来存储要删除的栈顶结点,将栈顶指针 改为 p->next,释放 p。

boolean pop(LinkStack *s, int *e) { if (stackEmpty(*s)) { return false; } pStackNode pNode = s->top; *e = pNode->data; s->top = pNode->next; free(pNode);

s->count--; return true; }

上面出栈操作中,用到判断栈是否为空,那么链栈是怎样判断是否为空栈的呢?

boolean stackEmpty(LinkStack *s) { if (s->top->next == NULL) return true; else return false; }

09

总结

从链栈的进栈和出栈操作,可以看出时间复杂度都为 O(1)。

对比顺序栈和链栈,它们的时间复杂度是一样的,对于空间性能,顺序栈需要先确定一个固定的长度,可能会造成空间浪费,但是它在存取时定位很方便,而链栈则要求每个元素都有指针域,无形中增加了内存开销,但是链栈对长度是没有限制的。

所以它们的区别和线性表的顺序存储以及链式存储的区别是一样的:如果栈中的元素个数变化较大,那么使用链栈再合适不过,反之,如果元素个数变化较小,使用顺序栈会更好一些。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

深度详解 Python yield与实现

学Python最简单的方法是什么?推荐阅读:Python开发工程师成长魔法 Python yield与实现 yield的功能类似于return,但是不同之处在于...

43312
来自专栏IT可乐

Java数据结构和算法(四)——栈

  前面我们讲解了数组,数组更多的是用来进行数据的存储,纯粹用来存储数据的数据结构,我们期望的是插入、删除和查找性能都比较好。对于无序数组,插入快,但是删除和查...

1785
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(六)Select 语句概览

Select 语句只会讲解最简单的情况:全表扫描+过滤,暂时不考虑索引等复杂情况,更复杂的情况会在后续章节中介绍。语句为:

4278
来自专栏趣学算法

数据结构 第6讲 链栈

进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

661
来自专栏Golang语言社区

厚土Go学习笔记 | 33. 利用数据流实现密码代换功能

利用 go 语言的 io.Reader 包裹另一个 io.Reader 的模式,修改数据流中的字符串(密码)代换功能。 提供一个字母和数字组合的字符串,对这个字...

36812
来自专栏社区的朋友们

SRF & SPP 源码走读

关于 SPP 的解读已经很多,本文尝试从另外的角度解读SRF&SPP;的源码。本文所涉及SRF代码皆以3.1.8版本,SPP代码皆以3.0.1版本为准。

9580
来自专栏aCloudDeveloper

总结:常用的通用数据处理指令

作者:bakari  时间:2012.4.21 1、 操作数类型 Imm立即操作数 Reg寄存器操作数 Mem内存操作数 2、 操作数寻址方式 立即数寻址 寄存...

1828
来自专栏蓝天

shell字符串操作集

root@x:~# echo $x|awk -F"//" '{print $1}'

542
来自专栏协程

state thread协程小谈

为了打造高性能的服务器,通常思路有两种:1.多cpu利用,并发执行,如多进程和多线程 2、提高每个cpu的使用率,让每个cpu高效起来。

1961
来自专栏前端知识分享

第14天:逻辑运算符、if、for语句

一假即假,同真为真 2、||(或) 一真即真,同假为假 3、!(非) 切记:参与逻辑运算的,都是布尔值。也就是说,只有true、false才能参与 逻辑运算,...

932

扫码关注云+社区