javascript的數據結構--實現一個棧

defcon 發布于2019-08-23 13:40 / 2039人閱讀

摘要：棧不管是在哪個語言，，還有咱們的都有這個數據結構，很多從別的行業轉開發的朋友都會經過這個學習過程。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。移除棧頂的元素，同時返回被移除的元素。

棧：不管是在哪個語言，c/c++,java,python，還有咱們的javascript都有這個數據結構，很多從別的行業轉開發的朋友都會經過這個學習過程。

棧：一種遵從后進先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的
同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

在現實生活中也能發現很多棧的例子。例如，下圖里的一摞書或者餐廳里堆放的盤子。
棧也被用在編程語言的編譯器和內存中保存變量、方法調用等。

創建一個棧（直接用ES6的class來寫吧）

先熟悉一下棧的一些方法：

push(element(s)) ：添加一個（或幾個）新元素到棧頂。
pop() ：移除棧頂的元素，同時返回被移除的元素。
peek() ：返回棧頂的元素，不對棧做任何修改（這個方法不會移除棧頂的元素，僅僅返回它）。
isEmpty() ：如果棧里沒有任何元素就返回 true ，否則返回 false 。
clear() ：移除棧里的所有元素。
size() ：返回棧里的元素個數。這個方法和數組的 length 屬性很類似。

class Stack {
    constructor () {
        this.items = []; //{1}
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        this.items.pop();
    ｝
    peek() {
        return items[items.length-1];
    }
    isEmpty() {
        return items.length == 0;
    }
    size() {
        return items.length;
    }
    clear() {
        items = [];
    }
    print() {
        console.log(items);
    }
}

盡管代碼看起來更簡潔、更漂亮，變量 items 卻是公共的。ES6的類是基于原型的。雖然基
于原型的類比基于函數的類更節省內存，也更適合創建多個實例，卻不能夠聲明私有屬性（變量）
或方法。而且，在這種情況下，我們希望 Stack 類的用戶只能訪問暴露給類的方法。否則，就有
可能從棧的中間移除元素（因為我們用數組來存儲其值），這不是我們希望看到的。

1. 用ES6的限定作用域 Symbol 實現類

ES6新增了一種叫作 Symbol 的基本類型，它是不可變的，可以用作對象的屬性。看看怎么用
它來在 Stack 類中聲明 items 屬性：

let _items = Symbol(); //{1}
class Stack {
    constructor () {
        this[_items] = []; //{2}
    }
    //Stack方法
}

在上面的代碼中，我們聲明了 Symbol 類型的變量 _items （行 {1} ），在類的 constructor 函
數中初始化它的值（行 {2} ）。要訪問 _items ，只需把所有的 this.items 都換成 this[_items] 。
這種方法創建了一個假的私有屬性，因為ES6新增的 Object.getOwnPropertySymbols 方
法能夠取到類里面聲明的所有 Symbols 屬性。下面是一個破壞 Stack 類的例子：

let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 輸出 5, 8, 1

從以上代碼可以看到，訪問 stack[objectSymbols[0]] 是可以得到 _items 的。并且，
_items 屬性是一個數組，可以進行任意的數組操作，比如從中間刪除或添加元素。我們操作的
是棧，不應該出現這種行為。

2. 用ES6的 WeakMap 實現類

有一種數據類型可以確保屬性是私有的，這就是 WeakMap 。我們會在第7章深入探討 Map 這
種數據結構，現在只需要知道 WeakMap 可以存儲鍵值對，其中鍵是對象，值可以是任意數據類型。

如果用 WeakMap 來存儲 items 變量， Stack 類就是這樣的：

const items = new WeakMap(); //{1}
class Stack {
    constructor () {
        items.set(this, []); //{2}
    }
    push(element) {
        let s = items.get(this); //{3}
        s.push(element);
    }
    pop() {
        let s = items.get(this);
        let r = s.pop();
        return r;
    }
    //其他方法
}

行 {1} ，聲明一個 WeakMap 類型的變量 items 。
行 {2} ，在 constructor 中，以 this （ Stack 類自己的引用）為鍵，把代表棧的數組存入 items。
行 {3} ，從 WeakMap 中取出值，即以 this 為鍵（行 {2} 設置的）從 items 中取值。
現在我們知道， items 在 Stack 類里是真正的私有屬性了，但還有一件事要做。 items 現在
仍然是在 Stack 類以外聲明的，因此誰都可以改動它。我們要用一個閉包（外層函數）把 Stack
類包起來，這樣就只能在這個函數里訪問 WeakMap ：

let Stack = (function () {
    const items = new WeakMap();
    class Stack {
        constructor () {
            items.set(this, []);
        }
        //其他方法
    }
    return Stack; //{4}
})();

當 Stack 函數里的構造函數被調用時，會返回 Stack 類的一個實例（行 {4} ）。

一個例子（把十進制的數轉換成任意進制的數）

function baseConverter(decNumber, base){
    var remStack = new Stack(),
        rem,
        baseString = "",
        digits = "0123456789ABCDEF"; //{5}
    while (decNumber > 0){
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    while (!remStack.isEmpty()){
        baseString += digits[remStack.pop()]; //{6}
    }
    return baseString;
}

我們只需要改變一個地方。在將十進制轉成二進制時，余數是0或1；在將十進制轉成八進制
時，余數是0到7之間的數；但是將十進制轉成16進制時，余數是0到9之間的數字加上A、B、C、
D、E和F（對應10、11、12、13、14和15）。因此，我們需要對棧中的數字做個轉化才可以（行
{5} 和行 {6} ）。

參考：《Javascript數據結構與算法》

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

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

JavaScript數據結構《棧》

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

nanchen2251 2019-08-21 16:44 評論0 收藏0
Javascript實現基本的數據結構 一棧

摘要：今天實現的是最基本的數據結構之一棧棧在中有著非常重要，基本類型會存儲在棧中，你可以操作實際的值。要定義一個棧，首先需要明白，棧的基本結構有哪些，需要遵循哪些規則。首先創建一個函數對象表示棧。 Javascript工程師，總會面對一個問題，數據結構和算法會成為自己的短板，不僅是對非科班，甚至一些科班出身的工程師來說也是自己的短板，于是就有了這系列文章。基礎決定深度，前端入門易，上升困難，...

seanlook 2019-08-20 16:32 評論0 收藏0
Javascript實現基本的數據結構 一棧

摘要：今天實現的是最基本的數據結構之一棧棧在中有著非常重要，基本類型會存儲在棧中，你可以操作實際的值。要定義一個棧，首先需要明白，棧的基本結構有哪些，需要遵循哪些規則。首先創建一個函數對象表示棧。 Javascript工程師，總會面對一個問題，數據結構和算法會成為自己的短板，不僅是對非科班，甚至一些科班出身的工程師來說也是自己的短板，于是就有了這系列文章。基礎決定深度，前端入門易，上升困難，...

cnio 2019-08-01 16:50 評論0 收藏0
學習javascript數據結構(一)——棧和隊列

摘要：原文地址學習數據結構一棧和隊列博主博客地址的個人博客幾乎所有的編程語言都原生支持數組類型，因為數組是最簡單的內存數據結構。他們就是棧和隊列。我們稱作棧頂，而另一端我們稱作棧底。移除棧頂的元素，同時返回被移除元素。前言只要你不計較得失，人生還有什么不能想法子克服的。原文地址：學習javascript數據結構(一)——棧和隊列博主博客地址：Damonare的個人博客幾乎所有的編程...

doodlewind 2019-08-21 14:42 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0