資料結構-棧
前言
陣列是 JS 中最常用的資料結構,它可以在任意位置新增或刪除資料。棧是另外一種資料結構,類似於陣列,但是在新增或刪除資料時更加靈活。
棧資料結構
棧是一種後進先出(LIFO) 的資料結構。新新增或待刪除的元素都儲存在棧的一端,叫棧頂 ,另一端就叫做棧底 。在棧中,新元素都靠近棧頂,就元素都靠近棧底。
建立棧
可以用陣列來模擬一個棧結構:
function Stack() { let items = [] // 棧的屬性和方法 }
需要實現的方法:
- push(element): 新增一個元素到棧頂
- pop(): 移除棧頂的元素,並返回該元素
- peek(): 僅僅返回棧頂的元素
- clear(): 清空棧
- size(): 返回棧中的元素的個數
- isEmpty(): 判斷棧是否為空
// 向棧中新增元素 this.push = function (element) { items.push(element) } // 從棧中移除元素 this.pop = function () { return items.pop() } // 檢視棧頂元素 this.peek = function () { return items[item.length - 1] } // 檢查棧是否為空 this.isEmpty = function () { return !!item.length } // 清空棧中的元素 this.clear = function () { items = [] } // 返回棧的大小 this.size = function () { return items.length } // 列印棧 this.print = function () { console.log(items.toString()) }
ES6 與 棧
ES6 的寫法:
class Stack { constructor() { this.items = [] } push (element) { this.items.push(element) } // ... 其他方法 }
ES6 的類是基於原型的,雖然基於原型的類比基於函式的類更節省記憶體,但是卻不能宣告私有變數,所以變數 items 是公共的。這種情況下,可以直接通過修改 items 來修改棧中的資料,這是無法避免的。
用 ES6 的限定作用域 Symbol 實現類
ES6 新增了 Symbol 基礎型別,它是不可變的,也可以作用物件的屬性。
let _items = Symbol() class Stack { constructor() { this[_items] = [] } // ... 其他方法 }
上面這個例子建立了一個假的私有屬性,不能完全規避上面提到的問題,因為 ES6 新增的Object.getOwnPropertySymbols
方法能夠取到類裡面宣告的所有 Symbols 屬性,比如:
let stack = new Stack() stack.push(66) stack.push(88) let objectSymbols = Object.getOwnPropertySymbols(stack) console.log(objectSymbols.length) // 1 console.log(objectSymbols[0]) // Symbol() stack[objectSymbols[0]].push(1) stack.print() // 66 88 1
通過訪問 stack[objectSymbols[0]] 是可以訪問 _items 的,並且可以對 _items 進行任意操作。
用 ES6 的WeakMap 實現類
有一種資料型別可以確保屬性是私有的,這就是WeakMap 。WeakMap 可以儲存鍵值對,其中鍵是物件,值可以是任意資料型別。
const 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() } // ... 其他方法 }
現在,Stack 中的 items 是私有的了,但是 items 是在 Stack 類以外宣告的,還是可以被改動,所以需要藉助閉包來實現一層封裝:
let Stack = (function () { const items = new WeakMap() class Stack { constructor() { items.set(this, []) } // ... 其他方法 return Stack } })()
### 用棧解決實際問題
棧在 JS 中應用還是十分廣泛的,比如呼叫棧 。進位制轉換也是很常見的例子,可以用 棧 來處理,比如要把十進位制轉化成二進位制,可以將該十進位制數字和2整除,直到結果是 0 為止。
function divideBy2 (decNumber) { var remStack = new Stack(), rem, binaryString = '' while (decNumber > 0) { rem = Math.floor(decNumber % 2) remStack.push(rem) decNumber = Math.floor(decNumber / 2) } while (!remStack.isEmpty()) { binaryString += remStack.pop().toString() } return binaryString }
這個例子中,當結果滿足和2做整除的條件是,會取得當前結果和2的餘數,放到棧裡,然後讓結果繼續和2做整除。
#### 改進演算法
把上面的例子改成十進位制轉成任意進位制的:
function baseConverter(decNumber, base) { var remStack = new Stack(), rem, binaryString = '', digits = '0123456789ABCDEF' while (decNumber > 0) { rem = Math.floor(decNumber % base) remStack.push(rem) decNumber = Math.floor(decNumber / base) } while (!remStack.isEmpty()) { binaryString += digits[remStack.pop()] } return binaryString }