专栏首页别明天就今天吧面试题-数组、链表实现栈

面试题-数组、链表实现栈

先来看看什么是栈,摘自百科:

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

其实栈就是一种特殊的数据结构,就像一叠盘子,一个落着一个,洗干净的盘子放到最上面,想取盘子的时候也是从最上面(top)去取。包含入栈(push)和出栈(pop)两个操作,特点是后进先出,先进后出。

数组实现栈(顺序栈):

链表实现栈(链式栈):

通过以上两种方式的实现,数组方式实现栈存在一个问题,容量是定义好了,如果超限需要考虑扩容问题,实现的方式一般是申请更大的空间,然后将老数组中的元素拷贝到新数组中,链式栈则不存在这个问题。

栈的实际应用:

1.浏览器的前进、后退功能,通过定义两个栈,把浏览的页面依次压入栈,当回退时,元素出栈放入到另一个栈中,当前进时,再从这个栈中取出放入到第一个栈。

2.方法的递归调用,最开始调用的方法最后执行,同样的道理。

本文分享自微信公众号 - 别明天就今天吧(gh_916f9a413d1e),作者:别明天就今天吧

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-28

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试题-JAVA之HashMap-get、resize方法源码分析

    HashMap的get方法是通过key获取对应Value的方法,resize方法则是初始化或扩容数组的方法,来看看是如何实现的;

    别明天就今天吧
  • 面试题-Map之LinkedHashMap

    说起LinkedHashMap其实都会带着一个词LRU(Least Recently Used)也就是最近最少使用,用LinkedHashMap实现LRU再适合...

    别明天就今天吧
  • HttpClient一站式web开发的首选工具

    多次请求会产生多个历史记录(默认记录最近50次请求),在历史记录前出现比较符号,可以很方便的比较多次访问的结果。

    别明天就今天吧
  • 编程小白 | 每日一练(33)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通
  • js 数组方法大集合,各方法是否改变原有的数组详解

    不会改变原来数组的有: concat()---连接两个或更多的数组,并返回结果。

    IT人一直在路上
  • 你所不知道的linux匿名管道知识

    相信很多在linux平台工作的童鞋, 都很熟悉管道符 '|', 通过它, 我们能够很灵活的将几种不同的命令协同起来完成一件任务。就好像下面的命令:

    马哥linux运维
  • 你所不知道的linux匿名管道知识

    豌豆贴心提醒,本文阅读时间5分钟 相信很多在linux平台工作的童鞋, 都很熟悉管道符 '|', 通过它, 我们能够很灵活的将几种不同的命令协同起来完成一件任...

    小小科
  • Spark-RDD常用Transformationg与Action操作

    RDD创建后就可以在RDD上进行数据处理。RDD支持两种操作:转换(transformation),即从现有的数据集创建一个新的数据集;动作(action),即...

    用户1205080
  • ES6学习之函数传参

    本文作者:IMWeb Terrance 原文出处:IMWeb社区 未经同意,禁止转载 ECMAScript 6 (or ECMAScript 201...

    IMWeb前端团队
  • ES6学习之函数传参

    PS:这篇文章主体是根据Faraz Kelhini的文章(见引用1)翻译而来,加入了自己的一些理解。

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券