本文深入解析JavaScript中栈、队列及优先队列的实现原理。通过代码示例展示栈的后进先出特性及其在进制转换中的应用，队列的先进先出机制及其在树形结构广度优先搜索（BFS）中的使用。此外，还探讨了基于线性结构和二叉堆（Max/Min Heap）的优先队列实现，并结合React Scheduler源码解析小顶堆在任务调度中的实际落地。
前言
在实际开发中，数组是我们最熟悉的数据结构，通常足以应对大多数场景。然而，面对更复杂的业务逻辑时，数组往往显得力不从心。选择合适的合适数据结构是解决复杂问题的前提，因此深入理解并掌握数据结构对于提升开发效率至关重要。
本文将重点梳理两种在实际开发中高频使用的数据结构，通过简明扼要的说明与示例，希望能对读者有所帮助。
栈（stack）
栈是一种抽象数据结构，其核心特征为“后进先出”（Last-in-First-Out，简称LIFO）。
理解栈的结构，可以联想生活中的场景：一摞盘子或装满子弹的弹夹。在软件应用中，浏览器的“后退”与“前进”功能便是典型例子：点击“后退”时，当前页面（栈顶）被弹出，返回至之前的页面。此外，IDE、Word、PhotoShop等编辑软件的“撤销”（undo）功能，其底层原理也是基于栈实现的，尽管具体代码实现各异，但核心逻辑一致。
得益于LIFO特性，栈仅允许操作栈顶元素，非栈顶元素无法直接访问。若要访问深层元素，必须先移除其上方的所有元素。这种限制使得栈成为一种高效且结构清晰的数据结构。
在JavaScript中实现栈，通常可直接利用数组进行封装。
栈实现
一个标准的栈数据结构需具备以下核心功能：
- push：插入新元素，并将其设为栈顶。
- pop：移除并返回栈顶元素。
- peek：查看栈顶元素但不将其移除，属于辅助方法。
- clear：清空栈内所有元素。
- isEmpty：判断栈是否为空，为空返回true，否则返回false。
- size：返回栈中元素的总数量。
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
clear() {
this.items = [];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
const stack = new Stack();
stack.push('c++');
stack.push('swift');
stack.push('python');
stack.push('javascript');
console.log(stack.isEmpty()); // false
console.log(stack.size()); // 4
console.log(stack.peek()); // javascript
const removedItem = stack.pop();
console.log(removedItem); // javascript
console.log(stack.peek()); // python
stack.clear();
console.log(stack.isEmpty()); // true
console.log(stack.size()); // 0解决实际问题
栈在解决具体算法问题时有着广泛的应用，以下是一个典型示例。
十进制转二进制的转换逻辑如下：
function transitionToBin(decNumber) {
const stack = new Stack();
do {
// 每次循环计算出的低位值，依次入栈
stack.push(decNumber % 2);
decNumber = Math.floor(decNumber / 2);
} while(decNumber > 0);
let result = '';
// 此时，stack 中存放的是转换后二进制值，栈顶是高位，依次向下。
while (stack.size() > 0) {
// 从栈顶的高位依次出栈，拼接到显示结果中
result += stack.pop();
}
return result;
}
const binNumber = transitionToBin(321);
console.log('binNumber: ', binNumber);栈的其他应用场景
栈还广泛应用于内存管理中，用于保存变量及方法调用。函数执行时压栈，返回结果时出栈。递归（recursion）便是栈应用的经典案例。
例如，计算阶乘的递归实现如下：
function factorial(n) {
return n > 1 ? n * factorial(n - 1) : n;
}
console.log(factorial(4));
简单队列（Queue）
除栈外，队列也是开发中常用的数据结构。队列由顺序元素组成的线性结构，与栈的LIFO不同，队列遵循“先进先出”（First-In-First-Out，FIFO）原则。
队列的操作规则为：在队尾添加新元素，在队头移除元素。
现实生活中，最直观的队列例子便是排队等候。
在计算机领域，队列的应用同样广泛，例如CPU的作业调度（Job Scheduling）、外围设备的并发联机（spooling），以及树和图的广度优先搜索（BFS）。
队列实现
构建一个队列数据结构，主要需实现两个核心操作：
- enqueue：将新元素推入队列。
- dequeue：从队列中移除一个已有元素。
我们可以创建一个类来封装队列，利用JavaScript原生数组存储数据，并调用内置函数完成队列操作。
class Queue {
constructor() {
this.items = [];
}
// 推入
enqueue(item) {
this.items.push(item);
}
// 移除
dequeue() {
return this.items.shift();
}
// 队列头元素
peek() {
return this.items[0];
}
// 为空判断
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}队列应用 - 树的广度优先搜索（breadth-first search，BFS）
在遍历树形结构时，既可以使用栈进行深度优先遍历，也可以利用队列进行广度优先遍历。假设存在如下树形数据结构，我们需要获取其所有节点的值。
const treeData = {
node: {
value: 12,
children: [{
value: 30,
children: [{
value: 22,
children: null
}, {
value: 10,
children: [{
value: 5,
children: null
}, {
value: 4,
children: null
}]
}]
}, {
value: 6,
children: [{
value: 8,
children: null
}, {
value: 70,
children: null
}]
}]
}
};使用队列进行广度优先遍历的代码及示意图如下：
function bfs(tree) {
// 准备一个空的队列
const queue = new Queue();
queue.enqueue(tree);
// 一个用于显示结果的数组
const result = [];
do {
// 出队列
let node = queue.dequeue();
result.push(node.value);
if (node.children && node.children.length > 0) {
node.children.forEach(sub => {
queue.enqueue(sub);
});
}
} while (queue.size() > 0);
// 显示遍历结果
console.log('result:', result.join(', '));
}
bfs(treeData.node);
// result: 12, 30, 6, 22, 10, 8, 70, 5, 4
优先队列
在实际场景中，部分队列需要特殊的处理逻辑，出队规则并非简单的“先到先得”。例如：
- 医院分诊系统中，重症患者优先接受治疗。
- 商品销售场景中，可按进货价排序，优先销售进货价较高的商品。
由此产生了“优先队列”。它是普通队列的扩展，区别在于元素具有指定的优先级（或权重）。高优先级元素排在队列前端并优先出队。优先队列保留了普通队列的所有基本操作，但内部增加了排序机制。
优先队列实现
由于设置了优先级规则，我们可以采用顺序存储方式（如数组）而非链式存储来保存队列节点。
基于线性数据结构实现虽满足条件，但时间复杂度较高，并非最优方案。
线性数据结构实现优先队列
实现优先队列主要有两种思路：
- 第一种：插入时直接追加至队尾，移除时遍历队列查找符合优先级条件的元素进行移除。
- 第二种：插入时根据优先级找到合适位置插入，移除时直接从队头取出元素。
以下以第二种方式为例，实现一个优先队列：
class QItem {
constructor(item, priority) {
this.item = item;
this.priority = priority;
}
toString() {
return `${this.item} - ${this.priority}`;
}
}
class PriorityQueue {
constructor() {
this.queues = [];
}
// 推入
enqueue(item, priority) {
const q = new QItem(item, priority);
let contain = false;
// 这个队列本身总是按照优先级，从大到小的
// 所以找到第一个比要插入值小的那个位置
for (let i = 0; i < this.queues.length; i++) {
if (this.queues[i].priority < q.priority) {
this.queues.splice(i, 0, q);
contain = true;
break;
}
}
// 都比它大，放最后
if (!contain) {
this.queues.push(q);
}
}
// 移除
dequeue() {
return this.queues.shift();
}
// 队列头元素
peek() {
return this.queues[0];
}
isEmpty() {
return this.queues.length === 0;
}
size() {
return this.queues.length;
}
}
const queue = new PriorityQueue();
queue.enqueue('K40', 3100);
queue.enqueue('K50', 5000);
queue.enqueue('K10', 6100);
queue.enqueue('K10', 6000);
queue.enqueue('K10', 5600);
queue.enqueue('K50', 4600);
queue.enqueue('K40', 5900);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
/*
QItem { item: 'K10', priority: 6100 }
QItem { item: 'K10', priority: 6000 }
QItem { item: 'K40', priority: 5900 }
QItem { item: 'K10', priority: 5600 }
QItem { item: 'K50', priority: 5000 }
QItem { item: 'K50', priority: 4600 }
QItem { item: 'K40', priority: 3100 }
*/Heap（堆）数据结构实现优先队列
上述线性结构实现了基础优先队列。我们还可以利用“堆”来实现，堆在数据存储上也是线性的，但元素位置遵循特定规则。
堆是一种能够快速从一组数据中找出最大值或最小值的数据结构。
堆是一种具有特殊特征的完全二叉树，也称为二叉堆。
二叉堆具备以下特点：
- 它是完全二叉树（complete binary tree）结构。所谓完全二叉树，指除底层叶子节点外，其他层均被填满，且底层叶子节点从左至右连续无空缺。这种结构使得二叉堆可以使用数组进行线性存储。
- 大顶堆（Max heap）：父节点的值大于或等于子节点，堆顶元素为最大值。
- 小顶堆（Min heap）：父节点的值小于或等于子节点，堆顶元素为最小值。
得益于完全二叉树的特性，我们可以直接使用数组来存储二叉堆。
二叉堆是堆排序和优先队列的基础。其常见应用场景包括处理最大/最小值高效的优先队列，以及堆排序算法本身。
代码实现一个二叉堆
二叉堆的插入和删除操作较为复杂，此处以最大堆（max-heap）为例进行说明。
插入（enqueue）操作
- 新元素首先插入到堆的尾部。
- 随后依次向上调整堆的结构，直至根节点。
此过程称为HeapifyUp。
删除（dequeue）操作
- 取出顶部元素（因其始终为最大值）。
- 将尾部元素移至顶部（暂不考虑其大小关系）。
- 随后依次从根部向下调整堆的结构，直至堆尾。
此过程称为HeapifyDown。
以下是一个max-heap的实现代码。修改comparator函数即可转换为min-heap。
class Heap {
constructor(comparator = (a, b) => a - b) {
this.arr = [];
this.comparator = (iSource, iTarget) => {
const value = comparator(this.arr[iSource], this.arr[iTarget]);
if (Number.isNaN(value)) {
throw new Error(`Comparator should evaluate to a number. Got ${value}！`);
}
return value;
}
}
enqueue(val) {
// 插入到末尾
this.arr.push(val);
// 向上冒泡，找到合适位置
this.siftUp();
}
dequeue() {
if (!this.size) return null;
const val = this.arr.shift();
const rep = this.arr.pop();
this.arr.splice(0, 0, rep);
this.siftDown();
}
get size() {
return this.arr.length;
}
siftUp() {
// 新元素索引
let index = this.size - 1;
// 根据完全二叉树的规则，这里我们可以依据元素索引index的值，获得他对应父节点的索引值
const parent = (i) => Math.floor((i - 1) / 2);
if (parent(index) >= 0 && this.comparator(parent(index), index) < 0) {
// 如果父节点存在，并且对比值比当前值小，则交互位置
this.swap(parent(index), index);
index = parent(index);
}
}
siftDown() {
let curr = 0;
const left = (i) => 2 * i + 1;
const right = (i) => 2 * i + 2;
const getTopChild = (i) => {
// 如果右节点存在，并且右节点值比左节点值大
return (right(i) < this.size && this.comparator(left(i), right(i)) < 0)
? right(i) : left(i);
};
// 左节点存在，并且当前节点的值，小于子节点中大的那个值，交换
while (left(curr) < this.size && this.comparator(curr, getTopChild(curr)) < 0) {
const next = getTopChild(curr);
this.swap(curr, next);
curr = next;
}
}
// 交换位置
swap(iFrom, iTo) {
[this.arr[iFrom], this.arr[iTo]] = [this.arr[iTo], this.arr[iFrom]];
}
}
const heap = new Heap();
heap.enqueue(56);
heap.enqueue(18);
heap.enqueue(20);
heap.enqueue(40);
heap.enqueue(30);
heap.enqueue(22);
console.log('heapify: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 1: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 2: ', heap.arr.join(', '));
heap.dequeue();
console.log('step 3: ', heap.arr.join(', '));
// heapify: 56, 40, 22, 18, 30, 20
// step 1: 40, 30, 22, 18, 20
// step 2: 30, 20, 22, 18
// step 3: 22, 20, 18如代码所示，数据入队时无序，但出队时总能获取最大值，从而实现了优先队列的功能。
小顶堆在React Scheduler事务调度包中的应用
Scheduler包含两个队列：timerQueue（未就绪任务队列）和taskQueue（就绪任务队列）。当新任务注册时，会被push至timerQueue，并根据开始时间重新排列顺序。
push方法基于schedulerMinHeap.js文件中的最小堆（min-heap）实现，源码链接见前文。
export function push(heap: Heap, node: Node): void {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}代码中，push操作后调用了siftUp方法来重新整理顺序。
function siftUp(heap, node, i) {
let index = i;
while (index > 0) {
const parentIndex = (index - 1) >>> 1;
const parent = heap[parentIndex];
if (compare(parent, node) > 0) {
// The parent is larger. Swap positions.
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
// The parent is smaller. Exit.
return;
}
}
}其中计算parentIndex使用了位移方法（等价于除以2取整），简洁高效。
最后
数据结构涵盖内容广泛，本文仅简要介绍了栈和队列，旨在引导读者探索更复杂的数据结构。真正掌握数据结构并将其应用于实际工作，对开发者至关重要。
到此关于JavaScript数据结构之栈和队列的文章介绍完毕，更多相关js栈和队列内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！