前端學數據結構之棧

来源:https://www.cnblogs.com/xiaohuochai/archive/2018/01/02/8174742.html
-Advertisement-
Play Games

[1]數據結構 [2]創建棧 [3]使用stack類 [4]ES6 [5]應用 ...


前面的話

　　學習數據結構和演算法十分重要。首要原因是數據結構和演算法可以很高效地解決常見問題，這對今後的代碼質量至關重要（也包括性能，要是用了不恰當的數據結構或演算法，很可能會產生性能問題）。其次，對於電腦科學，演算法是最基礎的概念。數組是電腦科學中最常用的數據結構，我們知道，可以在數組的任意位置上刪除或添加元素。然而，有時候還需要一種在添加或刪除元素時有更多控制的數據結構。有兩種數據結構類似於數組，但在添加和刪除元素時更為可控。它們就是棧和隊列。本文將詳細介紹棧

 

數據結構

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

　　在現實生活中也能發現很多棧的例子。例如，下圖裡的一摞書或者餐廳里堆放的盤子

stack

　　棧也被用在編程語言的編譯器和記憶體中保存變數、方法調用等

 

創建棧

　　下麵將創建一個類來表示棧，先聲明這個類：

function Stack() {
//各種屬性和方法的聲明
}

　　使用一種數據結構來保存棧里的元素。可以選擇數組：

let items = [];

　　接下來，為棧聲明一些方法

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

【push】

　　push方法負責往棧里添加新元素，有一點很重要：該方法只添加元素到棧頂，也就是棧的末尾

　　因為使用了數組來保存棧里的元素，所以可以數組的push方法來實現

this.push = function(element){ 
  items.push(element);
};

【pop】

　　接著來實現pop方法。這個方法主要用來移除棧里的元素。棧遵從LIFO原則，因此移出的是最後添加進去的元素。因此，可以用數組的pop方法

this.pop = function(){ 
  return items.pop();
};

　　只能用push和pop方法添加和刪除棧中元素，這樣一來，棧自然就遵從了LIFO原則

【peek】

　　現在，為類實現一些額外的輔助方法。如果想知道棧里最後添加的元素是什麼，可以用peek方法。這個方法將返回棧頂的元素：

this.peek = function(){
  return items[items.length-1];
};

　　因為類內部是用數組保存元素的，所以訪問數組的最後一個元素可以用 length - 1

stack2

　　在上圖中，有一個包含三個元素的棧，因此內部數組的長度就是3。數組中最後一項的位置是2，length - 1（3 -1）正好是2

【isEmpty】

　　下麵要實現的方法是 isEmpty，如果棧為空的話將返回true，否則就返回false：

this.isEmpty = function(){ 
  return items.length == 0;
};

　　使用isEmpty方法，能簡單地判斷內部數組的長度是否為0

【size】

　　類似於數組的length屬性，也能實現棧的length。對於集合，最好用size代替length。因為棧的內部使用數組保存元素，所以能簡單地返回棧的長度：

this.size = function(){ 
  return items.length;
};

【clear】

　　最後來實現clear方法。clear方法用來移除棧里所有的元素，把棧清空。實現這個方法最簡單的方式是：

this.clear = function(){ 
  items = [];
};

　　另外也可以多次調用pop方法，把數組中的元素全部移除，這樣也能實現clear方法

　　棧已經實現。通過一個例子來應用它，為了檢查棧里的內容，我們來實現一個輔助方法，叫print。它會把棧里的元素都輸出到控制台：

this.print = function(){ 
  console.log(items.toString());
};

　　這樣，我們就完整創建了棧！

　　棧的完整代碼如下

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

    this.toString = function(){
        return items.toString();
    };
}

 

使用stack類

　　下麵來學習如何使用Stack類。 首先，需要初始化Stack類。然後，驗證一下棧是否為空（輸出是true，因為還沒有往棧里添加元素）

var stack = new Stack(); 
console.log(stack.isEmpty()); //輸出為true

　　接下來，往棧里添加一些元素（可以添加任意類型的元素）

stack.push(5); 
stack.push(8);

　　如果調用peek方法，將會輸出8，因為它是往棧里添加的最後一個元素：

console.log(stack.peek());//輸出8

　　再添加一個元素：

stack.push(11); 
console.log(stack.size()); //輸出3 
console.log(stack.isEmpty()); //輸出false

　　我們往棧里添加了11。如果調用size方法，輸出為3，因為棧里有三個元素（5、8和11）。 如果調用isEmpty方法，會看到輸出了false（因為棧里有三個元素，不是空棧）。最後， 我們再添加一個元素：

stack.push(15);

　　下圖描繪了目前為止我們對棧的操作，以及棧的當前狀態：

stack3

　　然後，調用兩次pop方法從棧里移除2個元素：

stack.pop();
stack.pop(); 
console.log(stack.size()); //輸出2 
stack.print(); //輸出[5, 8]

　　在兩次調用pop方法前，我們的棧里有四個元素。調用兩次後，現在棧里僅剩下5和8了。下圖描繪這個過程的執行：

stack4

 

ES6

　　下麵來花點時間分析一下代碼，看看是否能用ES6的新功能來改進

　　我們創建了一個可以當作類來使用的Stack函數。JS函數都有構造函數，可以用來模擬類的行為。我們聲明瞭一個私有的items變數，它只能被Stack函數/類訪問。然而，這個方法為每個類的實例都創建一個items變數的副本。因此，如果要創建多個Stack實例，它就不太適合了

　　下麵用ES6新語法來聲明Stack類

class Stack {

    constructor () {
        this.items = [];
    }

    push(element){
        this.items.push(element);
    }
    //其他方法
}

　　我們只是用ES6的簡化語法把Stack函數轉換成Stack類。這種方法不能像其他語言(Java、C++、C#)一樣直接在類裡面聲明變數，只能在類的構造函數constructor里聲明，在類的其他函數里用this.items就可以引用這個變數

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

　　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屬性是一個數組，可以進行任意的數組操作，比如從中間刪除或添加元素。我們操作的是棧，不應該出現這種行為

【WeakMap】

　　有一種數據類型可以確保屬性是私有的，這就是WeakMap。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; //{5}
})();

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

　　現在，Stack類有一個名為items的私有屬性。雖然它很醜陋，但畢竟實現了私有屬性。然而，用這種方法的話，擴展類無法繼承私有屬性。魚與熊掌不可兼得

　　棧的完整代碼如下

let Stack3 = (function () {

    const items = new WeakMap();

    class Stack3 {

        constructor () {
            items.set(this, []);
        }

        push(element){
            let s = items.get(this);
            s.push(element);
        }

        pop(){
            let s = items.get(this);
            let r = s.pop();
            return r;
        }

        peek(){
            let s = items.get(this);
            return s[s.length-1];
        }

        isEmpty(){
            return items.get(this).length == 0;
        }

        size(){
            let s = items.get(this);
            return s.length;
        }

        clear(){
            items.set(this, []);
        }

        print(){
            console.log(this.toString());
        }

        toString(){
            return items.get(this).toString();
        }
    }

    return Stack3;
})();

　　把上面的代碼跟最初實現的Stack類做個比較，我們會發現有一些相似之處：

function Stack() {
 let items = [];
 //其他方法
}

　　事實上，儘管ES6引入了類的語法，仍然不能像在其他編程語言中一樣聲明私有屬性或方法。有很多種方法都可以達到相同的效果，但無論是語法還是性能，這些方法都有各自的優點和缺點

　　哪種方法更好？這取決於在實際項目中如何使用演算法，要處理的數據量，要創建的實例個數，以及其他約束條件

 

應用

　　棧的實際應用非常廣泛。在回溯問題中，它可以存儲訪問過的任務或路徑、撤銷的操作。Java和C#用棧來存儲變數和方法調用，特別是處理遞歸演算法時，有可能拋出一個棧溢出異常

　　下麵將學習使用棧的三個最著名的演算法示例。首先是十進位轉二進位問題，以及任意進位轉換的演算法；然後是平衡圓括弧問題；最後，學習如何用棧解決漢諾塔問題

【十進位轉二進位】

　　現實生活中，我們主要使用十進位。但在計算科學中，二進位非常重要，因為電腦里的所有內容都是用二進位數字表示的（0和1）。沒有十進位和二進位相互轉化的能力，與電腦交流就很困難

　　要把十進位轉化成二進位，我們可以將該十進位數字和2整除（二進位是滿二進一），直到結果是0為止。舉個例子，把十進位的數字10轉化成二進位的數字，過程大概是這樣

stack5

　　下麵是對應的演算法描述：

function divideBy2(decNumber){
 var remStack = new Stack(),
 rem,
 binaryString = '';
 while (decNumber > 0){ //{1}
  rem = Math.floor(decNumber % 2); //{2}
  remStack.push(rem); //{3}
  decNumber = Math.floor(decNumber / 2); //{4}
 }
 while (!remStack.isEmpty()){ //{5}
  binaryString += remStack.pop().toString();
 }
 return binaryString;
}

　　在這段代碼里，當結果滿足和2做整除的條件時（行{1}），我們會獲得當前結果和2的餘數，放到棧里（行{2}、{3}）。然後讓結果和2做整除（行{4}）。另外請註意：JavaScript有數字類型，但是它不會區分究竟是整數還是浮點數。因此，要使用Math.floor函數讓除法的操作僅返回整數部分。最後，用pop方法把棧中的元素都移除，把出棧的元素變成連接成字元串（行{5}）。

　　用剛纔寫的演算法做一些測試，使用以下代碼把結果輸出到控制台里：

console.log(divideBy2(233)); //輸出11101001 
console.log(divideBy2(10)); //輸出1010 
console.log(divideBy2(1000)); //輸出1111101000

【進位轉換演算法】

　　我們很容易修改之前的演算法，使之能把十進位轉換成任何進位。除了讓十進位數字和2整除 轉成二進位數，還可以傳入其他任意進位的基數為參數，就像下麵演算法這樣：

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

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

　　可以使用之前的演算法，輸出結果如下：

console.log(baseConverter(100345, 2)); //輸出11000011111111001
console.log(baseConverter(100345, 8)); //輸出303771
console.log(baseConverter(100345, 16)); //輸出187F9

【平衡圓括弧】

function parenthesesChecker(symbols){

    let stack = new Stack(),
        balanced = true,
        index = 0,
        symbol, top,
        opens = "([{",
        closers = ")]}";

    while (index < symbols.length && balanced){
        symbol = symbols.charAt(index);
        if (opens.indexOf(symbol) >= 0){
            stack.push(symbol);
            console.log(`open symbol - stacking ${symbol}`);
        } else {
            console.log(`close symbol ${symbol}`);
            if (stack.isEmpty()){
                balanced = false;
                console.log('Stack is empty, no more symbols to pop and compare');
            } else {
                top = stack.pop();
                //if (!matches(top, symbol)){
                if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
                    balanced = false;
                    console.log(`poping symbol ${top} - is not a match compared to ${symbol}`);
                } else {
                    console.log(`poping symbol ${top} - is is a match compared to ${symbol}`);
                }
            }
        }
        index++;
    }
    if (balanced && stack.isEmpty()){
        return true;
    }
    return false;
}

console.log(parenthesesChecker('{([])}')); //true
console.log(parenthesesChecker('{{([][])}()}')); //true
console.log(parenthesesChecker('[{()]')); //false

【漢諾塔】

function towerOfHanoi(n, from, to, helper){

    if (n > 0){
        towerOfHanoi(n-1, from, helper, to);
        to.push(from.pop());
        console.log('-----');
        console.log('Source: ' + from.toString());
        console.log('Dest: ' + to.toString());
        console.log('Helper: ' + helper.toString());
        towerOfHanoi(n-1, helper, to, from);
    }
}

var source = new Stack();
source.push(3);
source.push(2);
source.push(1);

var dest = new Stack();
var helper = new Stack();

towerOfHanoi(source.size(), source, dest, helper);

source.print();
helper.print();
dest.print();

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Mysql中函數和存儲過程的區別
    Mysql中函數和存儲過程的區別 存儲過程： 1、 可以寫sql語句 2、 inout，out構造返回值 3、 調用：call：存儲過程名稱 4、 可以返回結果集 函數： 1、 不可以寫sql語句 2、 使用return 返回值 3、 調用時，使用函數名（）即可 4、 不能獲取結果集 ...
  • SQL Server(第一章) 創建表 刪除表 創建主鍵約束、唯一約束、外鍵約束、CHECK約束、預設約束
    2.Orders訂單表 ...
  • mysql自連接求累計金額
    ...
  • 資料庫設計範式
    資料庫設計範式是一個很重要的概念，但是這個重要程度只是適合於參考。使用資料庫設計範式，可以讓數據表更好的進行數據的保存，因為在合理的設計，如果數據量一大也肯定會存在性能上的問題，所以在開發中，唯一可以稱為設計的寶典——設計的時候儘量避免日後的程式出現多表關聯查詢。 第一範式 所謂的第一範式指的是數據... ...
  • APP開發選擇什麼框架好? 請看這裡!
    背景 App的開發一般都需要滿足Android和iOS兩個系統環境，也就意味著一個App需要定製兩套實現方案，造成開發成本和維護成本都很高。為瞭解決這個問題，最好的辦法就是實現一套代碼跨端運行，所以Hybrid App混合應用模式應運而生。在Hybrid App整個開發框架上，有各種各樣的框架，各種 ...
  • ArcGIS Runtime SDK是什麼？
    如上圖，Runtime SDK是什麼東西？居然還有安卓、蘋果手機、Mac、QT的版本？ 是不是意味著ArcGIS的編輯數據和空間分析可以通過編程的方法在每個平臺上滿地跑了？ 答案是：是，也不是。 1. 與AO/AE的區別 AO是ArcGIS Desktop和ArcGIS Server的底層技術，有C ...
  • Android破解學習之路（五）——Android游戲 割繩子：魔法 + 在游戲加入Toast彈窗提示
    前言：這一期的破解教程，有新的知識內容出現啦！ 這一期破解的游戲是找不到之前的關鍵字，怎麼破解呢？ 破解成功之後，添加一個Toast彈窗提示由XX破解，這操作該如何實現呢？請往下看~ 鏈接: https://pan.baidu.com/s/1dF8jKdF 密碼: 6666 破解步驟： 1.試玩，找 ...
  • lodash源碼分析之Hash緩存
    在那小小的夢的暖閣，我為你收藏起整個季節的煙雨。 ——洛夫《靈河》 本文為讀 lodash 源碼的第四篇，後續文章會更新到這個倉庫中，歡迎 star： "pocket lodash" gitbook也會同步倉庫的更新，gitbook地址： "pocket lodash" 作用與用法 顧名思義，就是要 ...
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類