前言：為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1. 編程語言是相通的
   人們常說，編程語言是相通的，學(xué)會了一門析孽，其他語言也可以很輕松的掌握，我認為這是一個似是而非的說法只怎。
   每一門編程語言都離不開變量，條件判斷怜俐，循環(huán)這些概念身堡，但是每門編程語言又有自己的使用范圍，都有自己所擅長的領(lǐng)域拍鲤。即便nodejs已經(jīng)可以一統(tǒng)前后端贴谎，也總有他不能勝任的工作
   多年的工作經(jīng)驗告訴我汞扎，相通的不是語言，而是數(shù)據(jù)結(jié)構(gòu)與算法
2. 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目標

• 提高算法能力
• 提高程序框架設(shè)計能力
• 供你面試裝逼(這點真的沒毛病擅这，尤其是前端面試)

3. 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)需要的知識儲備
   我覺得你需要非常熟練的使用數(shù)組這個數(shù)據(jù)類型澈魄，再一個去知道如何在js中定義一個類。這里推薦下阮一峰老師的一篇文章Javascript定義類的三種方法仲翎。接下來我將以我粗淺的認識與大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)之 -- 棧

1. 棧的定義

棧是一種特殊的線性表痹扇，僅能夠在棧頂進行操作，有先進后出（后進先出）的特點

棧.png

羽毛球.jpeg

2. 棧的實現(xiàn)

2.1 數(shù)據(jù)存儲

從數(shù)據(jù)存儲的角度看玫坛，要實現(xiàn)棧有兩種方式结笨，一種是以數(shù)組做基礎(chǔ)，一種是以鏈表為基礎(chǔ)湿镀。數(shù)組是最簡單的實現(xiàn)方式炕吸，鏈表在后面會作為單獨的一種數(shù)據(jù)結(jié)構(gòu)來講解
我們先來定一個一個簡單的Stack類

function Stack() {
  var items = []; // 使用數(shù)組存儲數(shù)據(jù)
}

2.2 棧的方法

棧有以下幾個方法

• push 添加一個元素到棧頂(向桶里放入一個羽毛球)
• pop 彈出棧頂元素(從桶里拿出一個羽毛球)
• top 返回棧頂還俗，注意勉痴，不是彈出(看一眼不拿)
• isEmpty 判斷棧是否為空
• size 返回棧內(nèi)元素的個數(shù)
• clear 清空棧
  接下來赫模，我們逐一實現(xiàn)這些方法

2.2.1 push方法

// push方法向棧里壓入一個元素
this.push = function(item) {
  items.push(item)
}

2.2.2 pop方法

// pop方法把棧頂元素彈出
this.pop = function() {
  return items.pop()
}

2.2.3 top方法

// top方法返回棧頂元素
this.top = function() {
  return items[items.length - 1]
}

2.2.4 isEmpty方法

// isEmpty方法判斷棧是否為空
this.isEmpty = function() {
  return items.length == 0;
}

2.2.5 size方法

// size方法返回棧內(nèi)元素的個數(shù)
this.size = function() {
  return items.length
}

2.2.6 clear方法

// clear方法清空棧
this.clear = function() {
  items = []
}

最終完整版如下

function Stack() {
    var items = [];  // 使用數(shù)組存儲數(shù)據(jù)

    // push方法向棧里壓入一個元素
    this.push = function(item){
        items.push(item);
    };

    // pop方法把棧頂?shù)脑貜棾?    this.pop = function(){
        return items.pop();
    };

    // top 方法返回棧頂元素
    this.top = function(){
        return items[items.length - 1];
    };

    // isEmpty返回棧是否為空
    this.isEmpty = function(){
        return items.length == 0;
    };

    // size方法返回棧的大小
    this.size = function(){
        return items.length;
    };

    // clear 清空棧
    this.clear = function(){
        items = []
    }
}

2.3 被欺騙的感覺

看完上面的實現(xiàn)，很多同學(xué)會說蚀腿，佑弟你騙我嘴瓤，說的那么神乎其神的數(shù)據(jù)結(jié)構(gòu)，這里的棧竟然就是對數(shù)組進行了一層封裝而已袄蚋啤廓脆！WTF
真的是只做了一層封裝嗎？請大家思考以下問題

1. 給你一個數(shù)組磁玉，你可以通過索引操作任意元素停忿，但是給你一個棧，你能操作棧內(nèi)任意元素嗎蚊伞，棧提供的方法只允許我們操作棧頂元素席赂，也就是數(shù)組的最后一個元素，這種限制其實提供給我們一種思考問題的方式时迫，這個方式也就是棧的特性颅停，后進先出。
2. 既然實現(xiàn)棧用的是數(shù)組掠拳，那棧能做的事情癞揉，數(shù)組也一樣可以做，為什么要多此一舉弄個棧出來？封裝是為了隱藏實現(xiàn)細節(jié)喊熟，有時候站在棧的角度思考問題比站在數(shù)組的角度思考問題更加方便柏肪，后面的練習(xí)你就會有所體會

3. 棧的應(yīng)用練習(xí)

在這里我們通過一個練習(xí)題，你就能明白我剛才所說的站在棧的肩膀上思考問題有時候比站在數(shù)組的肩膀上思考問題更加方便

3.1 括號的合法

3.1.1 題目要求

下面的字符串中包含小括號芥牌，請便攜一個函數(shù)判斷字符串中的括號是否合法烦味，所謂的合法就是括號是成對出現(xiàn)

((ab(cd)g(aa))(cc))   合法
(ab(cd))(bbdsf)(1    不合法

3.1.2 思路分析

括號存在嵌套關(guān)系，也存在并列關(guān)系壁拉，如果使用數(shù)組存儲這些括號谬俄，再想辦法一一匹配左右括號似乎是一個可行的辦法，可是如何判斷一個左括號對應(yīng)的是哪個右括號呢扇商？
現(xiàn)在凤瘦，我們站在棧的肩膀上去思考這個問題，解題的過程就非常簡單了案铺，我們可以遍歷這個字符串蔬芥，對每個字符做以下操作

• 遇到左括號，就把左括號壓入棧頂
• 遇到右括號控汉，判斷棧是否為空笔诵，為空則說明沒有與之對應(yīng)的左括號，不合法姑子，如果不為空乎婿，則將棧頂元素彈出，這對括號就抵消了
  當for循環(huán)結(jié)束后街佑，如果棧為空谢翎，則說明左右括號全部抵消，則合法沐旨，反之不合法

3.1.3 示例代碼

function isLegitimate(string){
    var stack = new Stack();
    for(var i=0; i<string.length; i++ ){
        var item = string[i];
        if(item == "("){
            // 將左括號壓入棧
            stack.push(item);
        }else if (item==")"){
            // 如果為空,就說明沒有左括號與之抵消
            if(stack.isEmpty()){
                return false;
            }else{
                // 將棧頂?shù)脑貜棾?                stack.pop();
            }
        }

    }
    return stack.size() == 0;
};
console.log(isLegitimate("((ab(cd)g(aa))(cc))"))
console.log(isLegitimate("(ab(cd))(bbdsf)(1"))

3.1.4 小結(jié)

棧的底層是不是使用了數(shù)組不重要森逮，重要的是棧的后進先出的特性，重要的是你只能操作棧頂元素磁携，一定要忽略底層如何實現(xiàn)褒侧，去關(guān)心棧的特性。
在我們寫代碼的時候谊迄，經(jīng)常進行回退的操作闷供，control+z就可以了，那你有沒有想過统诺，這個就可以用棧來實現(xiàn)歪脏，每一步都放到棧中，當你想回退的時候粮呢，將棧頂元素彈出唾糯，你就得到了你之前一步的操作