數據結構-棧

zhoutk 發布于2019-08-23 14:59 / 2034人閱讀

摘要：棧是另外一種數據結構，類似于數組，但是在添加或刪除數據時更加靈活。棧數據結構棧是一種后進先出的數據結構。這種情況下，可以直接通過修改來修改棧中的數據，這是無法避免的。

前言

數組是 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
}

GPU云服務器云服務器棧結構棧數據結構棧順序結構優化遞歸數據棧

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101448.html

js數據結構和算法（二）棧和隊列

摘要：對于棧來說，這個表尾稱為棧的棧頂，相應的表頭稱為棧底。棧和隊列的區別棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。出棧操作出棧操作就是在棧頂取出數據，棧頂指針隨之下移的操作。基本概念棧和隊列都是動態的集合，在棧中，可以去掉的元素是最近插入的哪一個。棧實現了后進先出。在隊列中，可以去掉的元素總是在集合中存在的時間最長的那一個。隊列實現了先進先出的策略。棧的官...

jsummer 2019-08-21 12:30 評論0 收藏0
Java版-數據結構-棧

摘要：介紹棧是一種后進先出的線性表數據結構，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。介紹棧是一種后進先出的線性表數據結構，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。棧，只有兩種操作，分為入棧（壓棧）和出棧（退棧）；向棧中添加元素的操作叫做入棧，相反從棧中刪除元素叫做出棧。特點只能從棧頂添加元素或者...

voidking 2019-08-16 16:10 評論0 收藏0
JavaScript數據結構《棧》

摘要：我們都知道數組是里面比較常用的一種數據結構，棧和數組類似，定義如下棧是一種遵從后進先出原則的有序集合。新增加和待刪除的元素都保存在棧的尾部，也稱棧頂，相反的另一端就叫棧底，在棧的這種數據結構里面，我們新增的元素都在棧頂，舊的元素都在棧底。由于不是計算機專業出身，對數據結構這些了解的比較少，最近看了一些相關的書籍，這里做一些總結。本篇要說的是棧。我們都知道數組是JavaScript里面...

nanchen2251 2019-08-21 16:44 評論0 收藏0
finally與return之間的關系

摘要：則會在轉移指令前執行?？偨Y與之間的關系如果在中含有語句，那么語句的還有作用嗎先看一段代碼如果你對內存布局不是很清楚，請看這篇文章虛擬機類加載機制和字節碼執行引擎重點關注運行時棧幀結構局部變量表槽，操作數棧。定論問：finally語句一定會執行嗎？答：如果沒有執行相應的try語句則不會執行。在try語句中如果調用System.exit(0)方法則不會執行。問：finally...

Yuanf 2019-08-14 12:25 評論0 收藏0
JS數據結構學習：棧

摘要：棧的應用前面介紹了那么多棧相關的知識，最后也是介紹棧的應用場景的時候了，棧的實際應用非常廣泛，例如用來存儲訪問過的任務或路徑撤銷的操作。棧的定義什么是棧？棧是一種遵循后進先出原則的有序集合，新添加的或者待刪除的元素都保存在棧的同一端，稱為棧頂，另一端稱為棧底，在棧里，新元素靠近棧頂，舊元素靠近棧底，用個圖來看大概這樣式的：showImg(https://segmentfault.c...

Alfred 2019-08-26 13:28 評論0 收藏0
js 調用棧機制與ES6尾調用優化介紹

摘要：調用棧的運行機制機制程序運行到一個函數，它就會將其添加到調用棧中，當從這個函數返回的時候，就會將這個函數從調用棧中刪掉。在調用棧中每個調用偵都對應一個函數，最上方的調用幀稱為當前幀，調用棧是由所有的調用偵形成的。 showImg(https://segmentfault.com/img/remote/1460000019244497?w=900&h=600); 調用棧的英文名叫做Cal...

AaronYuan 2019-08-26 13:52 評論0 收藏0