Java基础、中级、高级、架构面试资料

吃多了拉就是队列,吃多了吐就是栈

JAVA herman 2469浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

吃多了拉就是队列,吃多了吐就是栈!听起来比较搞笑,但实际上比喻的还是挺形象的。今天我们先来简单的说说队列和栈!

队列和堆栈是一个更高层次的概念,其底层可以是用链表也可以是用数组来实现。

堆栈

堆栈实现了一种后进先出的语义 (LIFO) 。可以使用数组或者是链表来实现它:

栈

对于堆栈中的数据的所有操作都是在栈的顶部完成的,只可以查看栈顶部的数据,只能够向栈的顶部压入数据,也只能从栈的顶部弹出数据。

队列

队列实现了先入先出的语义 (FIFO) 。队列也可以使用数组和链表来实现:

队列

队列只允许在队尾添加数据,在队头删除数据。但是可以查看队头和队尾的数据。还有一种是双端队列,在两端都可以插入和删除:

双端队列

栈与队列的相同点

  1. 都是线性结构。
  2. 插入操作都是限定在表尾进行。
  3. 都可以通过顺序结构和链式结构实现。、
  4. 插入与删除的时间复杂度都是O(1),在空间复杂度上两者也一样。
  5. 多链栈和多链队列的管理模式可以相同。

栈与队列的不同点

  1. 删除数据元素的位置不同,栈的删除操作在表尾进行,队列的删除操作在表头进行。
  2. 应用场景不同;常见栈的应用场景包括括号问题的求解,表达式的转换和求值,函数调用和递归实现,深度优先搜索遍历等;常见的队列的应用场景包括计算机系统中各种资源的管理,消息缓冲器的管理和广度优先搜索遍历等。
  3. 顺序栈能够实现多栈空间共享,而顺序队列不能。

栈的使用场景可以参考方法调用链,A 调用 B,B 调用 C,那么 C 方法就在栈顶,它需要先结束。队列的使用场景就比较多了,各种队列实现类以及我们前面讲的公平锁、锁池、等待池等。

关于栈和队列,我后面再结合具体的 Java 类来说!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 吃多了拉就是队列,吃多了吐就是栈