Javascript數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
前言
我們實(shí)際開發(fā)中，比較熟悉的數(shù)據(jù)結(jié)構(gòu)是數(shù)組。一般情況下夠用了。但如果遇到復(fù)雜的問題，數(shù)組就捉襟見肘了。在解決一個(gè)復(fù)雜的實(shí)際問題的時(shí)候，選擇一個(gè)更為合適的數(shù)據(jù)結(jié)構(gòu)，是順利完成這些任務(wù)的前提基礎(chǔ)。所以好好了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，對我們高效的解決問題非常重要。
下面我總結(jié)了兩種我們在實(shí)際開發(fā)過程中比較常用到的數(shù)據(jù)結(jié)構(gòu)，簡單整理說明一下，希望對大家有幫助。
棧（stack）
棧是一種具有 「后入先出」(Last-in-First-Out，LIFO) 特點(diǎn)的抽象數(shù)據(jù)結(jié)構(gòu)。
了解棧的樣子，最常見的例子如：一摞盤子、一個(gè)壓入子彈的彈夾。還有比如我們上網(wǎng)使用的瀏覽器，都有『后退』、『前進(jìn)』按鈕。后退操作，就是把當(dāng)前正在瀏覽的頁面（棧頂）地址出棧，倒退回之前的地址。我們使用的編輯類的軟件，比如 IDE，Word，PhotoShop，他們的撤銷（undo）操作，也是用棧來實(shí)現(xiàn)的，軟件的具體實(shí)現(xiàn)代碼可能會(huì)有比較大的差異，但原理是一樣的。
由于棧后入先出的特點(diǎn)，每次只能操作棧頂?shù)脑?，任何不在棧頂?shù)脑兀紵o法訪問。要訪問下面的元素，先得拿掉上面的元素。所以它是一種高效的數(shù)據(jù)結(jié)構(gòu)。
用 Javascript 實(shí)現(xiàn)一個(gè)棧，通常我們用數(shù)組就可以?？梢宰鲆粋€(gè)簡單的封裝。
棧實(shí)現(xiàn)
棧通常需要實(shí)現(xiàn)下面常用功能：
- push（插入新元素，并讓新元素成為棧頂元素）
- pop（棧頂元素出棧，并返回棧頂元素）
- peek（想知道棧最后添加的是哪個(gè)，用這個(gè)方法。返回棧頂元素，不出棧。是個(gè)輔助方法）
- clear（清空棧）
- isEmpty（若棧為空，返回 true，否則返回 false）
- size（返回棧元素個(gè)數(shù)）
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解決實(shí)際問題
那么棧如何應(yīng)用解決實(shí)際問題，下面是一個(gè)例子。
一個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的例子：
function transitionToBin(decNumber) {
const stack = new Stack();
do {
// 每次循環(huán)計(jì)算出的低位值，依次入棧
stack.push(decNumber % 2);
decNumber = Math.floor(decNumber / 2);
} while(decNumber > 0);
let result = '';
// 此時(shí)，stack 中存放的是轉(zhuǎn)換后二進(jìn)制值，棧頂是高位，依次向下。
while (stack.size() > 0) {
// 從棧頂?shù)母呶灰来纬鰲?，拼接到顯示結(jié)果中
result += stack.pop();
}
return result;
}
const binNumber = transitionToBin(321);
console.log('binNumber: ', binNumber);棧的另外應(yīng)用
棧也被用于內(nèi)存保存變量和方法調(diào)用。函數(shù)調(diào)用的時(shí)候壓棧，return 結(jié)果的時(shí)候，出棧。比如我們經(jīng)常用的遞歸 （recursion） ，就是棧應(yīng)用的例子。
比如下面一個(gè)計(jì)算階乘的例子：
function factorial(n) {
return n > 1 ? n * factorial(n - 1) : n;
}
console.log(factorial(4));
簡單隊(duì)列（Queue）
除了棧，隊(duì)列也是一種常用的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列是由順序元素組成的線性數(shù)據(jù)結(jié)構(gòu)，又不同于棧 （Last-in-First-Out，LIFO） ，他遵循的是先進(jìn)先出（First-In-First-Out，F(xiàn)IFO） 。
隊(duì)列在隊(duì)尾添加新元素，在頂部移除元素。
現(xiàn)實(shí)中，最常見的隊(duì)列例子就是排隊(duì)。
計(jì)算機(jī)中，隊(duì)列應(yīng)用也相當(dāng)廣泛。例如計(jì)算機(jī) CPU 作業(yè)調(diào)度（Job Scheduling）、外圍設(shè)備聯(lián)機(jī)并發(fā)（spooling）、樹和圖的廣度優(yōu)先搜索（BFS）
隊(duì)列實(shí)現(xiàn)
一個(gè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，主要是要實(shí)現(xiàn)兩個(gè)操作：
- enqueue 把一個(gè)新元素推入隊(duì)列
- dequeue 從隊(duì)列中移除一個(gè)已有元素
我們創(chuàng)建一個(gè)類來封裝一個(gè)隊(duì)列。我們可以使用 javascript 原生的數(shù)組來存儲(chǔ)里面的數(shù)據(jù)內(nèi)容，和 javascript 自帶的函數(shù)來實(shí)現(xiàn)隊(duì)列的操作。
class Queue {
constructor() {
this.items = [];
}
// 推入
enqueue(item) {
this.items.push(item);
}
// 移除
dequeue() {
return this.items.shift();
}
// 隊(duì)列頭元素
peek() {
return this.items[0];
}
// 為空判斷
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}隊(duì)列應(yīng)用 - 樹的廣度優(yōu)先搜索（breadth-first search，BFS）
我們在遍歷一顆樹的時(shí)候，可以使用棧思路進(jìn)行深度優(yōu)先遍歷，也可以采用隊(duì)列的思路，廣度優(yōu)先遍歷。假設(shè)我們有下面這樣一個(gè)樹形的數(shù)據(jù)結(jié)構(gòu)，我們查找它所有的節(jié)點(diǎn)值。
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
}]
}]
}
};我們用隊(duì)列進(jìn)行廣度優(yōu)先的思路來遍歷。代碼和示意圖如下：
function bfs(tree) {
// 準(zhǔn)備一個(gè)空的隊(duì)列
const queue = new Queue();
queue.enqueue(tree);
// 一個(gè)用于顯示結(jié)果的數(shù)組
const result = [];
do {
// 出隊(duì)列
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);
// 顯示遍歷結(jié)果
console.log('result:', result.join(', '));
}
bfs(treeData.node);
// result: 12, 30, 6, 22, 10, 8, 70, 5, 4
優(yōu)先隊(duì)列
在實(shí)際情況中，有的隊(duì)列需要一些特殊的處理方式，出隊(duì)列規(guī)則的不一定是簡單粗暴的最早進(jìn)入隊(duì)列最先出。 比如：
- 醫(yī)院對病人的分診，重癥的優(yōu)先給予治療
- 我們銷售某件商品時(shí)，可以按照該商品入庫的進(jìn)貨價(jià)作為條件，進(jìn)貨價(jià)高的優(yōu)先拿出銷售。
于是，就有了優(yōu)先隊(duì)列。優(yōu)先隊(duì)列是普通隊(duì)列的一種擴(kuò)展，它和普通隊(duì)列不同的在于，隊(duì)列中的元素具有指定的優(yōu)先級(jí)別（或者叫權(quán)重）。 讓優(yōu)先級(jí)高的排在隊(duì)列前面，優(yōu)先出隊(duì)。優(yōu)先隊(duì)列具有隊(duì)列的所有特性，包括基本操作，只是在這基礎(chǔ)上添加了內(nèi)部的一個(gè)排序。
優(yōu)先隊(duì)列實(shí)現(xiàn)
因?yàn)樵O(shè)置了一些規(guī)則，我們可以用順序存儲(chǔ)的方式來存儲(chǔ)隊(duì)列，而不是鏈?zhǔn)酱鎯?chǔ)。換句話說，所有的節(jié)點(diǎn)都可以存儲(chǔ)到數(shù)組中。
滿足上面條件，我們可以利用線性數(shù)據(jù)結(jié)構(gòu)的方式實(shí)現(xiàn)，但時(shí)間復(fù)雜度較高，并不是最理想方式
線性數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列
我們要實(shí)現(xiàn)優(yōu)先隊(duì)列，就會(huì)有兩種方法。
- 第一種，就是插入的時(shí)候，不考慮其他，就在隊(duì)列末尾插入。而移除的時(shí)候，則要根據(jù)優(yōu)先級(jí)找出隊(duì)列中合適的元素移除。
- 第二種是，插入元素的時(shí)候，根據(jù)優(yōu)先級(jí)找到合適的放置位置，而移除的時(shí)候，直接從隊(duì)列前面移除。
下面以第二種情況為例，實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列：
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;
// 這個(gè)隊(duì)列本身總是按照優(yōu)先級(jí)，從大到小的
// 所以找到第一個(gè)比要插入值小的那個(gè)位置
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();
}
// 隊(duì)列頭元素
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（堆）數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列
上面是簡單的使用一個(gè)線性數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了一個(gè)優(yōu)先隊(duì)列。我們也可以用實(shí)現(xiàn)。這種堆數(shù)據(jù)存儲(chǔ)的時(shí)候也是一個(gè)線性的，只是這些數(shù)據(jù)的存放位置有一定規(guī)則。
堆可以理解為可以迅速找到一堆數(shù)中的最大或者最小值的數(shù)據(jù)結(jié)構(gòu)
堆是具有特殊特征的完全二叉樹（也叫二叉堆）。
二叉堆特點(diǎn)：
- 它是一個(gè)完全二叉樹（complete binary tree） 的數(shù)據(jù)結(jié)構(gòu)。所謂完全二叉樹（complete binary tree）,就是整個(gè)二叉樹，除了底層的葉子節(jié)點(diǎn)，其他的層都是填滿的，而且底層的葉子節(jié)點(diǎn)，從左到右不能有空的。（這樣一個(gè)完全二叉樹就能使用 Array 這種線性結(jié)構(gòu)來存儲(chǔ)）
- 大頂堆（Max heap） ：父節(jié)點(diǎn)的值大于或者等于子節(jié)點(diǎn)的值，堆頂是這個(gè)堆的最大元素
- 小頂堆（Min heap） ：父節(jié)點(diǎn)的值小于或者等于子節(jié)點(diǎn)的值，堆頂是這個(gè)堆的最小元素
因?yàn)橥耆鏄涞奶匦裕覀兛梢杂靡粋€(gè)數(shù)組來存儲(chǔ)二叉堆
二叉堆是實(shí)現(xiàn)堆排序和優(yōu)先隊(duì)列的基礎(chǔ)。二叉堆常用的應(yīng)用場景就是優(yōu)先隊(duì)列，它處理最大、最小值效率很高。同時(shí)堆排序算法也用到了二叉堆。
代碼實(shí)現(xiàn)一個(gè)二叉堆
二叉堆的插入和刪除操作比較復(fù)雜，我們用 max-heap 舉例說明。
插入（enqueue）操作
- 新元素一律先插入到堆的尾部
- 依次向上調(diào)整整個(gè)堆的結(jié)構(gòu)（一直到根即可）
HeapifyUp
刪除（dequeue）操作
- 取出頂部元素（因?yàn)樗肋h(yuǎn)是最大那個(gè)）
- 將尾元素替換到頂部（先不用管它的大小）
- 依次從根部向下調(diào)整整個(gè)堆的結(jié)構(gòu)（一直到堆尾即可）
HeapifyDown
下面是一個(gè) max-heap 的實(shí)現(xiàn)。comparator 函數(shù)里面修改一下，就可以變成一個(gè) 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;
// 根據(jù)完全二叉樹的規(guī)則，這里我們可以依據(jù)元素索引index的值，獲得他對應(yīng)父節(jié)點(diǎn)的索引值
const parent = (i) => Math.floor((i - 1) / 2);
if (parent(index) >= 0 && this.comparator(parent(index), index) < 0) {
// 如果父節(jié)點(diǎn)存在，并且對比值比當(dāng)前值小，則交互位置
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) => {
// 如果右節(jié)點(diǎn)存在，并且右節(jié)點(diǎn)值比左節(jié)點(diǎn)值大
return (right(i) < this.size && this.comparator(left(i), right(i)) < 0)
? right(i) : left(i);
};
// 左節(jié)點(diǎn)存在，并且當(dāng)前節(jié)點(diǎn)的值，小于子節(jié)點(diǎn)中大的那個(gè)值，交換
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如上面代碼所示，數(shù)據(jù)進(jìn)入隊(duì)列是無序的，但在出隊(duì)列的時(shí)候，總是能找到最大那個(gè)。這樣也實(shí)現(xiàn)了一個(gè)優(yōu)先隊(duì)列。
小頂堆在 React Scheduler 事務(wù)調(diào)度的包應(yīng)用
Scheduler 存在兩個(gè)隊(duì)列，timerQueue（未就緒任務(wù)隊(duì)列） 和 taskQueue（就緒任務(wù)隊(duì)列）。當(dāng)有新的未就緒任務(wù)被注冊，就會(huì) push 到 timerQueue 中，并根據(jù)開始時(shí)間重新排列任務(wù)順序。
push 方法是在一個(gè)叫 schedulerMinHeap.js 的文件中基于最小堆（min-heap）來實(shí)現(xiàn)的。schedulerMinHeap 源碼
export function push(heap: Heap, node: Node): void {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}看到代碼中，在 push 之后，調(diào)用了 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;
}
}
}這里計(jì)算 parentIndex 是用了位移的方法（等價(jià)于除以 2 再去尾），帥！
最后
數(shù)據(jù)結(jié)構(gòu)還有很多內(nèi)容，這里只是簡單的說了兩種，為了能引導(dǎo)大家去學(xué)習(xí)其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)知識(shí)。真正的掌握數(shù)據(jù)結(jié)構(gòu)，并把它應(yīng)用于實(shí)際工作中，對我們非常重要。
到此這篇關(guān)于Javascript數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的文章就介紹到這了,更多相關(guān)js棧和隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
解決layui 三級(jí)聯(lián)動(dòng)下拉框更新時(shí)回顯的問題
今天小編就為大家分享一篇解決layui 三級(jí)聯(lián)動(dòng)下拉框更新時(shí)回顯的問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09
js去除空格的方法有很多，本文整理了12種比較實(shí)用方法在此與大家分享下2013-11-11
JavaScript實(shí)現(xiàn)網(wǎng)頁下拉菜單效果
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)網(wǎng)頁下拉菜單效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
D3.js 從P元素的創(chuàng)建開始(顯示可加載數(shù)據(jù))
D3是一個(gè)基于數(shù)據(jù)操作的可視化js庫，認(rèn)識(shí)d3，就從最基礎(chǔ)的顯示可加載數(shù)據(jù)談起,需要的朋友可以參考下2014-10-10
javascript創(chuàng)建含數(shù)字字母的隨機(jī)字符串方法總結(jié)
如果想創(chuàng)建一個(gè)含有數(shù)字、字母（大小寫）或者符號(hào)的字符串，比如從[a-zA-Z0-9]集合中中創(chuàng)建一個(gè)隨機(jī)的字符串，長度為5.有沒有什么比較好的代碼呢？本文提供了幾種方法，包括自動(dòng)改變字符集合。一起來學(xué)習(xí)下。2016-08-08
怎么限制input的text里輸入的值只能是數(shù)字(正則、js)
這篇文章主要通過正則表達(dá)式和JS代碼限制input的text里輸入的值只能是數(shù)字的相關(guān)資料,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了JavaScript內(nèi)存優(yōu)化,主要是javascript的應(yīng)用越來越復(fù)雜,內(nèi)存問題所導(dǎo)致的卡頓、內(nèi)存溢出等現(xiàn)象也變得不再陌生,所以說也談內(nèi)存優(yōu)化,需要的朋友可以參考下2014-06-06
event對象獲取方法總結(jié)在google瀏覽器下測試
Event 對象代表事件的狀態(tài)，比如事件在其中發(fā)生的元素、鍵盤按鍵的狀態(tài)、鼠標(biāo)的位置、鼠標(biāo)按鈕的狀態(tài)，Event對象的獲取方法如下，感興趣的朋友可以參考下2013-11-11
基于Html+CSS+JS實(shí)現(xiàn)手動(dòng)放煙花效果
這篇文章主要介紹了利用Html+CSS+JavaScript實(shí)現(xiàn)的放煙花效果，文中一共實(shí)現(xiàn)了兩種方式：手動(dòng)和自動(dòng)，文中的示例代碼講解詳細(xì)，感興趣的可以試一試2022-01-01
阻止mousemove鼠標(biāo)移動(dòng)或touchmove觸摸移動(dòng)觸發(fā)click點(diǎn)擊事件
這篇文章主要為大家介紹了阻止mousemove或touchmove與click事件同時(shí)觸發(fā)技巧，一個(gè)按鈕綁定了多個(gè)事件，所以就要想辦法阻止 mouse 鼠標(biāo)事件或 touch 觸摸事件 與 click 事件同時(shí)觸發(fā)，不然每次拖拽按鈕后都會(huì)觸發(fā) click 事件，這顯然是不友好的2023-06-06