您好,登錄后才能下訂單哦!
這篇文章主要介紹JavaScript中棧和隊列算法的案例分析,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
一、認識數(shù)據(jù)結(jié)構(gòu)
什么是數(shù)據(jù)結(jié)構(gòu)?下面是維基百科的解釋
數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式
數(shù)據(jù)結(jié)構(gòu)意味著接口或封裝:一個數(shù)據(jù)結(jié)構(gòu)可被視為兩個函數(shù)之間的接口,或者是由數(shù)據(jù)類型聯(lián)合組成的存儲內(nèi)容的訪問方法封裝
我們每天的編碼中都會用到數(shù)據(jù)結(jié)構(gòu),因為數(shù)組是最簡單的內(nèi)存數(shù)據(jù)結(jié)構(gòu),下面是常見的數(shù)據(jù)結(jié)構(gòu)
數(shù)組(Array)
棧(Stack)
隊列(Queue)
鏈表(Linked List)
樹(Tree)
圖(Graph)
堆(Heap)
散列表(Hash)
下面來學(xué)習(xí)學(xué)習(xí)棧和隊列..
二、棧
2.1 棧數(shù)據(jù)結(jié)構(gòu)
棧是一種遵循后進先出(LIFO)原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端,稱作棧頂,另一端就叫棧底。在棧里,新元素都接近棧頂,舊元素都接近棧底。
類比生活中的物件:一摞書或者推放在一起的盤子
普通的棧常用的有以下幾個方法:
push 添加一個(或幾個)新元素到棧頂
pop 溢出棧頂元素,同時返回被移除的元素
peek 返回棧頂元素,不對棧做修改
isEmpty 棧內(nèi)無元素返回true,否則返回false
size 返回棧內(nèi)元素個數(shù)
clear 清空棧
class Stack { constructor() { this._items = []; // 儲存數(shù)據(jù) } // 向棧內(nèi)壓入一個元素 push(item) { this._items.push(item); } // 把棧頂元素彈出 pop() { return this._items.pop(); } // 返回棧頂元素 peek() { return this._items[this._items.length - 1]; } // 判斷棧是否為空 isEmpty() { return !this._items.length; } // 棧元素個數(shù) size() { return this._items.length; } // 清空棧 clear() { this._items = []; } }
現(xiàn)在再回頭想想數(shù)據(jù)結(jié)構(gòu)里面的棧是什么。
突然發(fā)現(xiàn)并沒有那么神奇,僅僅只是對原有數(shù)據(jù)進行了一次封裝而已。而封裝的結(jié)果是:并不去關(guān)心其內(nèi)部的元素是什么,只是去操作棧頂元素,這樣的話,在編碼中會更可控一些。
(1)十進制轉(zhuǎn)任意進制
要求: 給定一個函數(shù),輸入目標數(shù)值和進制基數(shù),輸出對應(yīng)的進制數(shù)(最大為16進制)
baseConverter(10, 2) ==> 1010 baseConverter(30, 16) ==> 1E
分析: 進制轉(zhuǎn)換的本質(zhì):將目標值一次一次除以進制基數(shù),得到的取整值為新目標值,記錄下余數(shù),直到目標值小于0,最后將余數(shù)逆序組合即可。利用棧,記錄余數(shù)入棧,組合時出棧
// 進制轉(zhuǎn)換 function baseConverter(delNumber, base) { const stack = new Stack(); let rem = null; let ret = []; // 十六進制中需要依次對應(yīng)A~F const digits = '0123456789ABCDEF'; while (delNumber > 0) { rem = Math.floor(delNumber % base); stack.push(rem); delNumber = Math.floor(delNumber / base); } while (!stack.isEmpty()) { ret.push(digits[stack.pop()]); } return ret.join(''); } console.log(baseConverter(100345, 2)); //輸出11000011111111001 console.log(baseConverter(100345, 8)); //輸出303771 console.log(baseConverter(100345, 16)); //輸出187F9
(2)逆波蘭表達式計算
要求: 逆波蘭表達式,也叫后綴表達式,它將復(fù)雜表達式轉(zhuǎn)換為可以依靠簡單的操作得到計算結(jié)果的表達式,例如(a+b)*(c+d)
轉(zhuǎn)換為a b + c d + *
["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6 ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] ==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
分析: 以符號為觸發(fā)節(jié)點,一旦遇到符號,就將符號前兩個元素按照該符號運算,并將新的結(jié)果入棧,直到棧內(nèi)僅一個元素
function isOperator(str) { return ['+', '-', '*', '/'].includes(str); } // 逆波蘭表達式計算 function clacExp(exp) { const stack = new Stack(); for (let i = 0; i < exp.length; i++) { const one = exp[i]; if (isOperator(one)) { const operatNum1 = stack.pop(); const operatNum2 = stack.pop(); const expStr = `${operatNum2}${one}${operatNum1}`; const res = eval(expStr); stack.push(res); } else { stack.push(one); } } return stack.peek(); } console.log(clacExp(["4", "13", "5", "/", "+"])); // 6.6
(3)利用普通棧實現(xiàn)一個有min
方法的棧
思路: 使用兩個棧來存儲數(shù)據(jù),其中一個命名為dataStack
,專門用來存儲數(shù)據(jù),另一個命名為minStack
,專門用來存儲棧里最小的數(shù)據(jù)。始終保持兩個棧中的元素個數(shù)相同,壓棧時判別壓入的元素與minStack
棧頂元素比較大小,如果比棧頂元素小,則直接入棧,否則復(fù)制棧頂元素入棧;彈出棧頂時,兩者均彈出即可。這樣minStack
的棧頂元素始終為最小值。
class MinStack { constructor() { this._dataStack = new Stack(); this._minStack = new Stack(); } push(item) { this._dataStack.push(item); // 為空或入棧元素小于棧頂元素,直接壓入該元素 if (this._minStack.isEmpty() || this._minStack.peek() > item) { this._minStack.push(item); } else { this._minStack.push(this._minStack.peek()); } } pop() { this._dataStack.pop(); return this._minStack.pop(); } min() { return this._minStack.peek(); } } const minstack = new MinStack(); minstack.push(3); minstack.push(4); minstack.push(8); console.log(minstack.min()); // 3 minstack.push(2); console.log(minstack.min()); // 2
三、隊列
3.1 隊列數(shù)據(jù)結(jié)構(gòu)
隊列是遵循先進先出(FIFO,也稱為先來先服務(wù))原則的一組有序的項。隊列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊列的末尾
類比:日常生活中的購物排隊
普通的隊列常用的有以下幾個方法:
enqueue
向隊列尾部添加一個(或多個)新的項
dequeue
移除隊列的第一(即排在隊列最前面的)項,并返回被移除的元素
head
返回隊列第一個元素,隊列不做任何變動
tail
返回隊列最后一個元素,隊列不做任何變動
isEmpty
隊列內(nèi)無元素返回true
,否則返回false
size
返回隊列內(nèi)元素個數(shù)
clear
清空隊列
class Queue { constructor() { this._items = []; } enqueue(item) { this._items.push(item); } dequeue() { return this._items.shift(); } head() { return this._items[0]; } tail() { return this._items[this._items.length - 1]; } isEmpty() { return !this._items.length; } size() { return this._items.length; } clear() { this._items = []; } }
與棧類比,棧僅能操作其頭部,隊列則首尾均能操作,但僅能在頭部出尾部進。當(dāng)然,也印證了上面的話:棧和隊列并不關(guān)心其內(nèi)部元素細節(jié),也無法直接操作非首尾元素。
(1)約瑟夫環(huán)(普通模式)
要求: 有一個數(shù)組a[100]
存放0~99;要求每隔兩個數(shù)刪掉一個數(shù),到末尾時循環(huán)至開頭繼續(xù)進行,求最后一個被刪掉的數(shù)。
分析: 按數(shù)組創(chuàng)建隊列,依次判斷元素是否滿足為指定位置的數(shù),如果不是則enqueue
到尾部,否則忽略,當(dāng)僅有一個元素時便輸出
// 創(chuàng)建一個長度為100的數(shù)組 const arr_100 = Array.from({ length: 100 }, (_, i) => i*i); function delRing(list) { const queue = new Queue(); list.forEach(e => { queue.enqueue(e); }); let index = 0; while (queue.size() !== 1) { const item = queue.dequeue(); index += 1; if (index % 3 !== 0) { queue.enqueue(item); } } return queue.tail(); } console.log(delRing(arr_100)); // 8100 此時index=297
(2)菲波那切數(shù)列(普通模式)
要求: 使用隊列計算斐波那契數(shù)列的第n項
分析: 斐波那契數(shù)列的前兩項固定為1,后面的項為前兩項之和,依次向后,這便是斐波那契數(shù)列。
function fibonacci(n) { const queue = new Queue(); queue.enqueue(1); queue.enqueue(1); let index = 0; while(index < n - 2) { index += 1; // 出隊列一個元素 const delItem = queue.dequeue(); // 獲取頭部值 const headItem = queue.head(); const nextItem = delItem + headItem; queue.enqueue(nextItem); } return queue.tail(); } console.log(fibonacci(9)); // 34
(3)用隊列實現(xiàn)一個棧
要求: 用兩個隊列實現(xiàn)一個棧
分析: 使用隊列實現(xiàn)棧最主要的是在隊列中找到棧頂元素并對其操作。具體的思路如下:
兩個隊列,一個備份隊列emptyQueue
,一個是數(shù)據(jù)隊列dataQueue
;
在確認棧頂時,依次dequeue
至備份隊列,置換備份隊列和數(shù)據(jù)隊列的引用即可
class QueueStack { constructor() { this.queue_1 = new Queue(); this.queue_2 = new Queue(); this._dataQueue = null; // 放數(shù)據(jù)的隊列 this._emptyQueue = null; // 空隊列,備份使用 } // 確認哪個隊列放數(shù)據(jù),哪個隊列做備份空隊列 _initQueue() { if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } else if (this.queue_1.isEmpty()) { this._dataQueue = this.queue_2; this._emptyQueue = this.queue_1; } else { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } }; push(item) { this.init_queue(); this._dataQueue.enqueue(item); }; peek() { this.init_queue(); return this._dataQueue.tail(); } pop() { this.init_queue(); while (this._dataQueue.size() > 1) { this._emptyQueue.enqueue(this._dataQueue.dequeue()); } return this._dataQueue.dequeue(); }; };
學(xué)習(xí)了棧和隊列這類簡單的數(shù)據(jù)結(jié)構(gòu),我們會發(fā)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)并沒有之前想象中那么神秘,它們只是規(guī)定了這類數(shù)據(jù)結(jié)構(gòu)的操作方式:棧只能對棧頂進行操作,隊列只能在尾部添加在頭部彈出;且它們不關(guān)心內(nèi)部的元素狀態(tài)。
以上是“JavaScript中棧和隊列算法的案例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。