JS資料結構學習:棧
棧的定義
什麼是棧?棧是一種遵循後進先出原則的有序集合,新新增的或者待刪除的元素都儲存在棧的同一端,稱為棧頂,另一端稱為棧底,在棧裡,新元素靠近棧頂,舊元素靠近棧底,用個圖來看大概這樣式的:
用一個更形象的例子來說明:上網的時候,每點選一個超連結,瀏覽器都會開啟一個新的頁面,並且壓入到一個訪問歷史棧中,你可以不斷的點選開啟新的頁面,但總是可以通過回退重新訪問以前的頁面,從瀏覽器的訪問歷史棧中彈出歷史網頁地址,從棧頂彈出,總是最新的最先彈出
棧的建立
首先建立一個類用來表示棧,接著宣告一個數組用來儲存棧裡的元素:
function Stack() { let items = [] // 方法宣告 }
建立好棧之後,需要為棧宣告一些方法,棧一般會包含以下幾個方法:
- push(): 新增新元素到棧頂
- pop(): 移除棧頂的元素,同時返回被移除的元素
- peek(): 返回棧頂的元素,不對棧做任何修改
- isEmpty(): 如果棧裡沒有任何元素就返回true,否則返回false
- clear(): 移除棧裡的所有元素
- size(): 返回棧裡的元素個數
具體實現:
function Stack() { let items = [] // 新增元素到棧頂,也就是棧的末尾 this.push = function (element) { items.push(element) } // 棧的後進先出原則,從棧頂出棧 this.pop = function () { return items.pop() } // 檢視棧頂的元素,訪問陣列最後一個元素 this.peek = function () { return items[items.length - 1] } // 檢查棧是否為空 this.isEmpty = function () { return items.length == 0 } // 返回棧的長度,棧的長度就是陣列的長度 this.size = function () { return items.length } // 清空棧 this.clear = function () { items = [] } // 列印棧元素 this.print = function () { console.log(items.toString()) } }
棧的使用
現在我們來看如何使用棧:
let stack = new Stack() stack.push(1) stack.push(2) stack.push(3) console.log(stack.peek()) // 3 console.log(stack.isEmpty()) // false console.log(stack.size()) // 3
先向棧中加入三個元素1,2,3,接下來用一張圖來看一下入棧的過程:
入棧過程都是在棧頂依次入棧,接著呼叫peek方法返回棧頂元素3,isEmpty返回false,size返回棧的長度3,然後在繼續呼叫pop來看看出棧的過程:
stack.pop() stack.print() // 1,2
出棧也是和入棧相同,都是從棧頂開始出棧,保證棧的後入先出原則
es6宣告Stack類
上面建立了一個Stack函式來充當類,並且在裡面聲明瞭一個私有變數,但是在es6裡面是有類的語法的,可以直接用es6新語法來宣告,程式碼大概是這樣事的:
class Stack { constructor () { this.items = [] } push (element) { this.items.push(element) } pop () { return this.items.pop() } peek () { return this.items[items.length - 1] } isEmpty () { return this.items.length == 0 } size () { return this.items.length } clear () { this.items = [] } print () { console.log(this.items.toString()) } } let stack = new Stack() stack.push(1) console.log(stack.isEmpty()) stack.print()
看起來似乎不錯,比之前要簡單,關鍵是看起來更加合理,使用的是類的語法,呼叫也沒有什麼問題,但是如果這麼執行呢?
console.log(stack.items)
會發現一個問題,在stack類外面可以直接訪問類裡面的屬性,按照設計items應該是Stack類的私有屬性才對,就像之前Stack函式裡面的私有變數,是不能在外部訪問的,如何才能將items變成私有屬性呢?應該會有和我一樣想法的人,使用閉包,在閉包裡面裡面定義私有屬性,然後再將stack類返回回來,程式碼實現大概是這樣的:
let Stack = (function () { let items = new WeakMap() class Stack { constructor () { items.set(this, []) } push (element) { let s = items.get(this) s.push(element) } pop () { let s = items.get(this) return s.pop() } peek () { let s = items.get(this) return s[s.length - 1] } isEmpty () { let s = items.get(this) return s.length == 0 } size () { let s = items.get(this) return s.length } clear () { let s = items.get(this) s = [] } print () { let s = items.get(this) console.log(s.toString()) } } return Stack })()
可能有人會問為什麼這裡要把items定義成一個WeakMap物件,先簡單介紹一下WeakMap物件的用法,WeakMap物件是一對鍵/值對的集合,其鍵必須是物件,值可以是任意的,定義成WeakMap就是為了將items屬性變成私有屬性,在外部呼叫Stack物件的時候無法訪問到items屬性。
棧的應用
前面介紹了那麼多棧相關的知識,最後也是介紹棧的應用場景的時候了,棧的實際應用非常廣泛,例如用來儲存訪問過的任務或路徑、撤銷的操作。為了有一個更直觀的應用瞭解,下面會介紹如何用來解決計算機中的進位制轉換問題,將10進位制轉換為其他進位制數,可能不少人已經忘了如何進行進位制轉換了,下面先來看一個簡單的10進位制轉2進位制的過程:
上面的圖中展示將一個10進位制8轉化為2進位制數的過程,接下來看看用棧是如何實現的:
function conver(num, radix) { let stack = new Stack() let binaryString = '' let digits = '0123456789ABCDEF' while (num > 0) { stack.push(num % radix) num = parseInt(num / radix) } while (!stack.isEmpty()) { binaryString += digits[stack.pop()] } console.log(binaryString) } conver(8, 2) // 1000
總結
這篇文章主要對棧做了簡單介紹,動手實踐了棧的實現,以及用棧實現了一個簡單進位制轉換的功能。如果有錯誤或不嚴謹的地方,歡迎批評指正,如果喜歡,歡迎點贊。