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

说起数据结构，自然绕不开 堆(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] 作为对象存在于堆内存中

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

JS堆栈应用

二、堆 (Heap)

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

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

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

三、栈 (Stack)

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

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

栈 Stack

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

四、队列 (Queue)

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

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

队列 Queue

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

《数据结构与算法》系列

欢迎访问：天问博客