javascript的數(shù)據(jù)結構--實現(xiàn)一個棧

defcon 發(fā)布于2019-08-23 13:40 / 2084人閱讀

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

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

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

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

創(chuàng)建一個棧（直接用ES6的class來寫吧）

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

push(element(s)) ：添加一個（或幾個）新元素到棧頂。
pop() ：移除棧頂?shù)脑?，同時返回被移除的元素。
peek() ：返回棧頂?shù)脑兀粚Ｗ鋈魏涡薷模ㄟ@個方法不會移除棧頂?shù)脑?，僅僅返回它）。
isEmpty() ：如果棧里沒有任何元素就返回 true ，否則返回 false 。
clear() ：移除棧里的所有元素。
size() ：返回棧里的元素個數(shù)。這個方法和數(shù)組的 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的類是基于原型的。雖然基
于原型的類比基于函數(shù)的類更節(jié)省內(nèi)存，也更適合創(chuàng)建多個實例，卻不能夠聲明私有屬性（變量）
或方法。而且，在這種情況下，我們希望 Stack 類的用戶只能訪問暴露給類的方法。否則，就有
可能從棧的中間移除元素（因為我們用數(shù)組來存儲其值），這不是我們希望看到的。

1. 用ES6的限定作用域 Symbol 實現(xiàn)類

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

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

在上面的代碼中，我們聲明了 Symbol 類型的變量 _items （行 {1} ），在類的 constructor 函
數(shù)中初始化它的值（行 {2} ）。要訪問 _items ，只需把所有的 this.items 都換成 this[_items] 。
這種方法創(chuàng)建了一個假的私有屬性，因為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 屬性是一個數(shù)組，可以進行任意的數(shù)組操作，比如從中間刪除或添加元素。我們操作的
是棧，不應該出現(xiàn)這種行為。

2. 用ES6的 WeakMap 實現(xiàn)類

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

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

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

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

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

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;
}

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

參考：《Javascript數(shù)據(jù)結構與算法》

GPU云服務器云服務器 java 手寫一個棧 python實現(xiàn)棧 javascript全棧視頻 javascript全棧教程

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

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/99367.html

JavaScript數(shù)據(jù)結構《棧》

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

nanchen2251 2019-08-21 16:44 評論0 收藏0
Javascript實現(xiàn)基本的數(shù)據(jù)結構一棧

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

seanlook 2019-08-20 16:32 評論0 收藏0
Javascript實現(xiàn)基本的數(shù)據(jù)結構一棧

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

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

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

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

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

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