【数据结构与算法】(2)：堆(heap)、栈(stack)、队列(queue)

说起数据结构，自然绕不开 堆(heap)、栈(stack)、队列(queue) 这三种常用的数据结构。

一、前言

堆栈模型在 JS 中的应用：

• 值类型变量，存储在 栈 (变量对象)
• 引用类型变量，存储在 堆 (堆内存空间)

// 值类型
var a1 = 0;                 // 变量对象
var a2 = 'this is string';  // 变量对象
var a3 = null;              // 变量对象
// 引用类型
var b = { m: 20 };          // 变量b存在于变量对象中，{m: 20} 作为对象存在于堆内存中
var c = [1, 2, 3];          // 变量c存在于变量对象中，[1, 2, 3] 作为对象存在于堆内存中

上边代码用图来表示，则是这样：

二、堆 (Heap)

堆是一种特殊的树状数据结构，它的存取数据的方式，则与书架与书非常相似。好比在JSON格式的数据中，我们存储的 key-value 是可以无序的，因为顺序的不同并不影响我们的使用，我们只需要关心书的名字。
它具有以下特点：

• 堆是一个完全二叉树，即除了最后一层外，其他层的节点都是满的，并且最后一层的节点都尽量靠左排列。
• 堆中的每个节点都满足堆的性质，即父节点的值大于或等于（或小于或等于）其子节点的值。
• 堆可以分为两种类型：最大堆和最小堆。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

堆 的应用非常广泛，其中最常见的应用之一是堆排序。堆排序是一种高效的排序算法，它利用堆的性质进行排序操作。此外，堆还可以用于优先队列、图算法等领域。

三、栈 (Stack)

栈是一种具有 后进先出 （LIFO）特性的数据结构，它的操作只能在栈的一端进行。栈有两个基本操作：

• 入栈（Push）：将元素添加到栈的顶部。
• 出栈（Pop）：从栈的顶部移除元素。

栈可以用数组或链表来实现。在实际应用中，栈常常用于函数调用、表达式求值、括号匹配等场景。

四、队列 (Queue)

队列是一种具有 先进先出 （FIFO）特性的数据结构，它的操作在队列的两端进行。队列有两个基本操作：

• 入队（Enqueue）：将元素添加到队列的尾部。
• 出队（Dequeue）：从队列的头部移除元素。

队列也可以用 数组或链表 来实现。在实际应用中，队列常常用于任务调度、消息传递、缓冲区管理等场景。

---

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-10
最后更新： 2023-07-20
本文标题： 【数据结构与算法】(2)：堆(heap)、栈(stack)、队列(queue)
本文链接： https://www.tiven.cn/p/c55e8f27/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！