数据结构学习笔记——栈

定义

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

我们允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。

栈又称作后进先出(Last In First Out)的线性表。这里应该注意,栈是一种特殊的线性表。栈的特殊之处在于限制了线性表的插入和删除的位置。

栈是线性表,那么就具有线性关系,即前驱后继关系。

栈底是固定的,最先进栈的只能在栈底。

栈的插入操纵,叫做进栈,也叫压栈、入栈。栈的删除操作,也叫出栈,有的也叫弹栈。如图:

特殊注意,并不是最先进栈的就一定是最后出栈,如1进、1出、2进、2出、3进、3出,1先进,1也先出。

线性表的顺序存储和链式存储,对于栈来说同样适用。

栈的顺序存储结构

栈是通过数组来实现的。如图:

top表示栈顶元素的位置,top为-1表示为空栈,top=StackSize-1表示栈满。

进栈、出栈

由图可知,两者都没有涉及到任何循环操作,因此时间复杂度都是O(1) 。

两栈共享控件

栈有一个很大的缺陷,就是必须事先确定数组存储空间的大小,万一不够用了,就需要用编程手段进行扩展数组容量。

对于两个相同类型的栈,我们可以尽最大限度地利用事先开辟好的存储空间来进行操作。

方法就是:两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈底为数组的末端,即下标为数组长度n-1处。这样,如果两个栈增加元素,就是两个端点向中间延伸。

top1和top2是栈1和栈2的两个栈顶指针,只要它们不见面,两个栈就可以一直用。

一般是当两个栈的空间需求有相反关系时,也就是一个栈增长,另一个栈缩短的情况。

栈的链式存储结构

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

由于单链表有头指针,而栈顶指针也是必须的,所以最好的办法就是把栈顶放在单链表的头部。如图:

对于链栈来说,基本不存在满栈的情况,除非内存已经没有可以使用的空间。

链栈的进栈和出栈

直接看图:

进栈

新结点S指针域指向原栈顶,将S赋值给栈顶指针。

出栈

栈顶结点指针指向下一位,释放结点P。

综上,如果栈的使用过程中,元素变化不可预料,有时很小,有时非常大,那么最好用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈更好。

栈的应用——递归

递归函数:我们把一个直接调用自己或者通过一系列的调用语言间接地调用自己的函数,叫做递归函数。

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

那么递归和栈有什么关系呢?

递归过程退回的顺序是它前进顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。

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

简而言之,递归过程的退回顺序就是前进顺序的逆序,所以使用栈是最好的数据结构。

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-03-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

Java每日一练(2017/7/18)

新通知 ●回复"每日一练"获取以前的题目! ●【新】Ajax知识点视频更新了!(回复【学习视频】获取下载链接) ●【新】HTML5知识点视频更新了!(回复【前端...

35610
来自专栏Java3y

栈和队列就是这么简单

一、前言 上一篇已经讲过了链表【Java实现单向链表】了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:栈和队列 如果写错的地方希望大家能够多多体谅并...

37610
来自专栏写代码的海盗

准备冲锋 golang入坑系列

史前摘要: 本来想写读前必读,但连续几篇博文都写读前必读,感觉就没有了新意。 所以换成史前摘要,反正是一个意思。 此摘要的目的仍然是提醒点击而来的同学,本系列最...

3645
来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

992
来自专栏浪淘沙

Java学习day16---人际关系

1325
来自专栏C语言及其他语言

【每日一题】问题 1183: 人见人爱A+B

北大的acm上面已经有10来道A+B的题目了,相信这些题目曾经是大家的最爱,希望今天的这个A+B能给大家带来好运,也希望这个题目能唤起大家对ACM曾经的热爱。...

1372
来自专栏zhisheng

#每日一题#2

由于昨天文章原创原因,所以没发出来,大部分同学没看这篇啊。于是在一次发出来,希望大家可以认真的思考,这些题目都是互联网大公司笔试的题目,很有参考性!大家不要浪费...

3669
来自专栏小勇DW3

HashMap 与 ConcrrentHashMap 使用以及源码原理分析

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为...

6403
来自专栏数据魔术师

基础算法 | 数据结构之线性表&顺序表&链表(上)

各位,起床了起床了 小编又来送干货了 今天讲的是数据结构 全文字数:1185字 阅读时间:10分钟 数据结构?啥玩意? * 内容提要: *预备知识 *顺序表(S...

4216
来自专栏pydata

understand WSGI

生成器与迭代器区别: 容器是一种把多个元素组织在一起的数据结构, 容器中的元素可以逐个地迭代获取,可以用in,not in 关键字判断元素是否包含在容器中。 通...

862

扫码关注云+社区

领取腾讯云代金券