Javascript數(shù)據(jù)結(jié)構(gòu)之棧和隊列詳解

第Javascript數(shù)據(jù)結(jié)構(gòu)之棧和隊列詳解

棧（stack）

棧是一種具有「后入先出」(Last-in-First-Out，LIFO)特點的抽象數(shù)據(jù)結(jié)構(gòu)。

了解棧的樣子，最常見的例子如：一摞盤子、一個壓入子彈的彈夾。還有比如我們上網(wǎng)使用的瀏覽器，都有『后退』、『前進』按鈕。后退操作，就是把當前正在瀏覽的頁面（棧頂）地址出棧，倒退回之前的地址。我們使用的編輯類的軟件，比如IDE，Word，PhotoShop，他們的撤銷（undo）操作，也是用棧來實現(xiàn)的，軟件的具體實現(xiàn)代碼可能會有比較大的差異，但原理是一樣的。

由于棧后入先出的特點，每次只能操作棧頂?shù)脑?，任何不在棧頂?shù)脑?，都無法訪問。要訪問下面的元素，先得拿掉上面的元素。所以它是一種高效的數(shù)據(jù)結(jié)構(gòu)。

用Javascript實現(xiàn)一個棧，通常我們用數(shù)組就可以。可以做一個簡單的封裝。

棧實現(xiàn)

棧通常需要實現(xiàn)下面常用功能：

push（插入新元素，并讓新元素成為棧頂元素）pop（棧頂元素出棧，并返回棧頂元素）peek（想知道棧最后添加的是哪個，用這個方法。返回棧頂元素，不出棧。是個輔助方法）clear（清空棧）isEmpty（若棧為空，返回true，否則返回false）size（返回棧元素個數(shù)）

classStack{

constructor(){

this.items=[];

push(item){

this.items.push(item);

pop(){

returnthis.items.pop();

peek(){

returnthis.items[this.items.length-1];

clear(){

this.items=[];

isEmpty(){

returnthis.items.length===0;

size(){

returnthis.items.length;

conststack=newStack();

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

constremovedItem=stack.pop();

console.log(removedItem);//javascript

console.log(stack.peek());//python

stack.clear();

console.log(stack.isEmpty());//true

console.log(stack.size());//0

解決實際問題

那么棧如何應用解決實際問題，下面是一個例子。

一個十進制轉(zhuǎn)換為二進制的例子：

functiontransitionToBin(decNumber){

conststack=newStack();

do{

//每次循環(huán)計算出的低位值，依次入棧

stack.push(decNumber%2);

decNumber=Math.floor(decNumber/2);

}while(decNumber

letresult='';

//此時，stack中存放的是轉(zhuǎn)換后二進制值，棧頂是高位，依次向下。

while(stack.size()0){

//從棧頂?shù)母呶灰来纬鰲?，拼接到顯示結(jié)果中

result+=stack.pop();

returnresult;

constbinNumber=transitionToBin(321);

console.log('binNumber:',binNumber);

棧的另外應用

棧也被用于內(nèi)存保存變量和方法調(diào)用。函數(shù)調(diào)用的時候壓棧，return結(jié)果的時候，出棧。比如我們經(jīng)常用的遞歸（recursion），就是棧應用的例子。

比如下面一個計算階乘的例子：

functionfactorial(n){

returnn1n*factorial(n-1):n;

console.log(factorial(4));

簡單隊列（Queue）

除了棧，隊列也是一種常用的數(shù)據(jù)結(jié)構(gòu)。隊列是由順序元素組成的線性數(shù)據(jù)結(jié)構(gòu)，又不同于棧（Last-in-First-Out，LIFO），他遵循的是先進先出（First-In-First-Out，F(xiàn)IFO）。

隊列在隊尾添加新元素，在頂部移除元素。

現(xiàn)實中，最常見的隊列例子就是排隊。

計算機中，隊列應用也相當廣泛。例如計算機CPU作業(yè)調(diào)度（JobScheduling）、外圍設備聯(lián)機并發(fā)（spooling）、樹和圖的廣度優(yōu)先搜索（BFS）

隊列實現(xiàn)

一個隊列數(shù)據(jù)結(jié)構(gòu)，主要是要實現(xiàn)兩個操作：

enqueue把一個新元素推入隊列dequeue從隊列中移除一個已有元素

我們創(chuàng)建一個類來封裝一個隊列。我們可以使用javascript原生的數(shù)組來存儲里面的數(shù)據(jù)內(nèi)容，和javascript自帶的函數(shù)來實現(xiàn)隊列的操作。

classQueue{

constructor(){

this.items=[];

//推入

enqueue(item){

this.items.push(item);

//移除

dequeue(){

returnthis.items.shift();

//隊列頭元素

peek(){

returnthis.items[0];

//為空判斷

isEmpty(){

returnthis.items.length===0;

size(){

returnthis.items.length;

}

隊列應用-樹的廣度優(yōu)先搜索（breadth-firstsearch，BFS）

我們在遍歷一顆樹的時候，可以使用棧思路進行深度優(yōu)先遍歷，也可以采用隊列的思路，廣度優(yōu)先遍歷。假設我們有下面這樣一個樹形的數(shù)據(jù)結(jié)構(gòu)，我們查找它所有的節(jié)點值。

consttreeData={

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

};

我們用隊列進行廣度優(yōu)先的思路來遍歷。代碼和示意圖如下：

functionbfs(tree){

//準備一個空的隊列

constqueue=newQueue();

queue.enqueue(tree);

//一個用于顯示結(jié)果的數(shù)組

constresult=[];

do{

//出隊列

letnode=queue.dequeue();

result.push(node.value);

if(node.childrennode.children.length0){

node.children.forEach(sub={

queue.enqueue(sub);

}while(queue.size()

//顯示遍歷結(jié)果

console.log('result:',result.join(','));

bfs(treeData.node);

//result:12,30,6,22,10,8,70,5,4

優(yōu)先隊列

在實際情況中，有的隊列需要一些特殊的處理方式，出隊列規(guī)則的不一定是簡單粗暴的最早進入隊列最先出。比如：

醫(yī)院對病人的分診，重癥的優(yōu)先給予治療我們銷售某件商品時，可以按照該商品入庫的進貨價作為條件，進貨價高的優(yōu)先拿出銷售。

于是，就有了優(yōu)先隊列。優(yōu)先隊列是普通隊列的一種擴展，它和普通隊列不同的在于，隊列中的元素具有指定的優(yōu)先級別（或者叫權(quán)重）。讓優(yōu)先級高的排在隊列前面，優(yōu)先出隊。優(yōu)先隊列具有隊列的所有特性，包括基本操作，只是在這基礎上添加了內(nèi)部的一個排序。

優(yōu)先隊列實現(xiàn)

因為設置了一些規(guī)則，我們可以用順序存儲的方式來存儲隊列，而不是鏈式存儲。換句話說，所有的節(jié)點都可以存儲到數(shù)組中。

滿足上面條件，我們可以利用線性數(shù)據(jù)結(jié)構(gòu)的方式實現(xiàn)，但時間復雜度較高，并不是最理想方式

線性數(shù)據(jù)結(jié)構(gòu)實現(xiàn)優(yōu)先隊列

我們要實現(xiàn)優(yōu)先隊列，就會有兩種方法。

第一種，就是插入的時候，不考慮其他，就在隊列末尾插入。而移除的時候，則要根據(jù)優(yōu)先級找出隊列中合適的元素移除。第二種是，插入元素的時候，根據(jù)優(yōu)先級找到合適的放置位置，而移除的時候，直接從隊列前面移除。

下面以第二種情況為例，實現(xiàn)一個優(yōu)先隊列：

classQItem{

constructor(item,priority){

this.item=item;

this.priority=priority;

toString(){

return`${this.item}-${this.priority}`;

classPriorityQueue{

constructor(){

this.queues=[];

//推入

enqueue(item,priority){

constq=newQItem(item,priority);

letcontain=false;

//這個隊列本身總是按照優(yōu)先級，從大到小的

//所以找到第一個比要插入值小的那個位置

for(leti=0;ithis.queues.length;i++){

if(this.queues[i].priorityq.priority){

this.queues.splice(i,0,q);

contain=true;

break;

//都比它大，放最后

if(!contain){

this.queues.push(q);

//移除

dequeue(){

returnthis.queues.shift();

//隊列頭元素

peek(){

returnthis.queues[0];

isEmpty(){

returnthis.queues.length===0;

size(){

returnthis.queues.length;

constqueue=newPriorityQueue();

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)實現(xiàn)優(yōu)先隊列

上面是簡單的使用一個線性數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了一個優(yōu)先隊列。我們也可以用實現(xiàn)。這種堆數(shù)據(jù)存儲的時候也是一個線性的，只是這些數(shù)據(jù)的存放位置有一定規(guī)則。

堆可以理解為可以迅速找到一堆數(shù)中的最大或者最小值的數(shù)據(jù)結(jié)構(gòu)

堆是具有特殊特征的完全二叉樹（也叫二叉堆）。

二叉堆特點：

它是一個完全二叉樹（completebinarytree）的數(shù)據(jù)結(jié)構(gòu)。所謂完全二叉樹（completebinarytree）,就是整個二叉樹，除了底層的葉子節(jié)點，其他的層都是填滿的，而且底層的葉子節(jié)點，從左到右不能有空的。（這樣一個完全二叉樹就能使用Array這種線性結(jié)構(gòu)來存儲）大頂堆（Maxheap）：父節(jié)點的值大于或者等于子節(jié)點的值，堆頂是這個堆的最大元素小頂堆（Minheap）：父節(jié)點的值小于或者等于子節(jié)點的值，堆頂是這個堆的最小元素

因為完全二叉樹的特性，我們可以用一個數(shù)組來存儲二叉堆

二叉堆是實現(xiàn)堆排序和優(yōu)先隊列的基礎。二叉堆常用的應用場景就是優(yōu)先隊列，它處理最大、最小值效率很高。同時堆排序算法也用到了二叉堆。

代碼實現(xiàn)一個二叉堆

二叉堆的插入和刪除操作比較復雜，我們用max-heap舉例說明。

插入（enqueue）操作

新元素一律先插入到堆的尾部依次向上調(diào)整整個堆的結(jié)構(gòu)（一直到根即可）

HeapifyUp

刪除（dequeue）操作

取出頂部元素（因為它永遠是最大那個）將尾元素替換到頂部（先不用管它的大小）依次從根部向下調(diào)整整個堆的結(jié)構(gòu)（一直到堆尾即可）

HeapifyDown

下面是一個max-heap的實現(xiàn)。comparator函數(shù)里面修改一下，就可以變成一個min-heap

classHeap{

constructor(comparator=(a,b)=a-b){

this.arr=[];

parator=(iSource,iTarget)={

constvalue=comparator(this.arr[iSource],this.arr[iTarget]);

if(Number.isNaN(value)){

thrownewError(`Comparatorshouldevaluatetoanumber.Got${value}！`);

returnvalue;

enqueue(val){

//插入到末尾

this.arr.push(val);

//向上冒泡，找到合適位置

this.siftUp();

dequeue(){

if(!this.size)returnnull;

constval=this.arr.shift();

constrep=this.arr.pop();

this.arr.splice(0,0,rep);

this.siftDown();

getsize(){

returnthis.arr.length;

siftUp(){

//新元素索引

letindex=this.size-1;

//根據(jù)完全二叉樹的規(guī)則，這里我們可以依據(jù)元素索引index的值，獲得他對應父節(jié)點的索引值

constparent=(i)=Math.floor((i-1)/2);

if(parent(index)=0parator(parent(index),index)0){

//如果父節(jié)點存在，并且對比值比當前值小，則交互位置

this.swap(parent(index),index);

index=parent(index);

siftDown(){

letcurr=0;

constleft=(i)=2*i+1;

constright=(i)=2*i+2;

constgetTopChild=(i)={

//如果右節(jié)點存在，并且右節(jié)點值比左節(jié)點值大

return(right(i)this.sizeparator(left(i),right(i))0)

right(i):left(i);

//左節(jié)點存在，并且當前節(jié)點的值，小于子節(jié)點中大的那個值，交換

while(left(curr)this.sizeparator(curr,getTopChild(curr))0){

constnext=getTopChild(curr);

this.swap(curr,next);

curr=next;

//交換位置

swap(iFrom,iTo){

[this.arr[iFrom],this.arr[iTo]]=[this.arr[iTo],this.arr[iFrom]];

constheap=newHeap();

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('step1:',heap.arr.join(','));

heap.dequeue();

console.log('step2:',heap.arr.join(','));

heap.dequeue();

console.log('step3:',heap.arr.join(','));

//heapify:56,40,22,18,30,20

//step1:40,30,22,18,20

//step2:30,20,22,18

//step3:22,20,18

如上面代碼所示，數(shù)據(jù)