技术编程|计算机世界里的“堆栈”你真的懂吗？
如果你学过数据结构 ， 就一定会遇到“堆”,"栈","堆栈",这些对于小白来说有些头大 ， 下面就来科普一下何谓堆栈？
按照WIKI的定义：
堆栈（英语：stack） ， 是计算机科学中一种特殊的串列形式的抽象数据类型 ， 其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针 ， 英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算 。另外堆栈也可以用一维数组或链表的形式来完成 。堆栈的另外一个相对的操作方式称为队列 。需要记住的是 ， 堆：顺序随意 ， 栈：后进先出(Last-In/First-Out) 。
文章图片
文章图片
这里的pop和push到都是什么意思？其实这是堆栈数据结构使用两种基本操作：推入（压栈 ， push）和弹出（弹栈 ， pop）：
推入：将数据放入堆栈的顶端（数组形式或串列形式） ， 堆栈顶端top指针加一 。
弹出：将顶端数据数据输出（回传） ， 堆栈顶端数据减一 。
文章图片
文章图片
如要了解堆栈 ， 应将之拆开分析 。
堆的概念：
堆（英语：Heap）是计算机科学中的一种特别的树状数据结构 。通常是一个可以被看做一棵树的数组对象 。若是满足以下特性 ， 即可称为堆：“给定堆中任意节点 P 和 C ， 若 P 是 C 的父节点 ， 那么 P 的值会小于等于（或大于等于） C 的值” 。若父节点的值恒小于等于子节点的值 ， 此堆称为最小堆（英语：min heap）；反之 ， 若父节点的值恒大于等于子节点的值 ， 此堆称为最大堆（英语：max heap） 。在堆中最顶端的那一个节点 ， 称作根节点（英语：root node） ， 根节点本身没有父节点（英语：parent node） 。
文章图片
文章图片
栈的概念
栈（stack）又名堆栈 ， 它是一种运算受限的线性表 。其限制是仅允许在表的一端进行插入和删除运算 。这一端被称为栈顶 ， 相对地 ， 把另一端称为栈底 。栈就是一个桶 ， 后放进去的先拿出来 ， 它下面本来有的东西要等它出来之后才能出来（先进后出）
栈(Stack)是操作系统在建立某个进程时或者线程（在支持多线程的操作系统中是线程）为这个线程建立的存储区域 ， 该区域具有FIFO的特性 ， 在编译的时候可以指定需要的Stack的大小 。
文章图片
文章图片
堆栈
其实堆栈本身就是栈 ， 只是换了个抽象的名字 。其特性是： 最后一个放入堆栈中的物体总是被最先拿出来 ， 这个特性通常称为后进先出(LIFO)队列 。堆栈中定义了一些操作 。两个最重要就是上述提到的PUSH和POP 。PUSH操作在堆栈的顶部加入一个元素 ， POP操作相反 ， 在堆栈顶部移去一个元素 ， 并将堆栈的大小减一 。
文章图片
文章图片
工作原理
对于工作方式你可能还是一头雾水 ， 以自助餐托盘为例解释一下 ， 你就会更加明了：
作为堆栈如何工作的一个例子 ， 可以把它看成一个弹簧加载托盘分发器 ， 这种类型经常在自助餐厅中发现 。每个托盘上都刻有数字 。托盘依次从顶部装入 ， 每个托盘都放置在已经装入的托盘上 ， 弹簧进行压缩 ， 以便在必要时为更多托盘留出空间 。例如 ， 在图中 ， 托盘编号为42、23、2、9 ， 先装载42个托盘 ， 后装载9个托盘 。
推荐阅读
- 行业互联网|华为 | 车载以太网物理层及TSN发展现状 与技术趋势
- 技术编程|什么是Plesk虚拟主机控制面板？
- 电池技术|法国发明出世界最快的电极：可将锂电池的密度提高3倍
- 技术编程|人工智能在大视频运维中如何实现CDN硬盘故障预测？
- 电池技术|关于惠州赣锋建设高端聚合物锂电池研发及生产基地建设，赣锋锂业要干大事
- |加速冲刺世界级技术领先地位，大族机器人获1.65亿元A轮融资
- 解码器|苹果 ProRes 视频编解码器获 2020 技术工程艾美奖
- 数据|徐叶润：另类数据技术是驱动资管科技的核心
- 中年|《经济学人》封面文章解析蚂蚁集团：数字技术的崛起代表了金融的未来
- 行业互联网|北科院轻工所技术入选中关村论坛技术交易大会“产业创新领先技术百强项目榜单”