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

Scott 發(fā)布于2019-08-23 12:01 / 1141人閱讀

摘要：棧就是和列表類(lèi)似的一種數(shù)據(jù)結(jié)構(gòu)它可以用來(lái)解決計(jì)算機(jī)世界里的很多問(wèn)題棧是一種高效的數(shù)據(jù)結(jié)構(gòu)因?yàn)閿?shù)據(jù)只能在棧頂添加或刪除所以這樣的操作很快而且容易實(shí)現(xiàn)棧的使用遍布程序語(yǔ)言的方方面面從表達(dá)式求值到處理函數(shù)調(diào)用棧的操作棧只能通過(guò)列表的一端訪問(wèn)這一端

棧就是和列表類(lèi)似的一種數(shù)據(jù)結(jié)構(gòu), 它可以用來(lái)解決計(jì)算機(jī)世界里的很多問(wèn)題. 棧是一種高效的數(shù)據(jù)結(jié)構(gòu), 因?yàn)閿?shù)據(jù)只能在棧頂添加或刪除, 所以這樣的操作很快, 而且容易實(shí)現(xiàn). 棧的使用遍布程序語(yǔ)言的方方面面, 從表達(dá)式求值到處理函數(shù)調(diào)用.

棧的操作

棧只能通過(guò)列表的一端訪問(wèn), 這一端稱(chēng)為棧頂.
棧被稱(chēng)為 先進(jìn)后出 的數(shù)據(jù)結(jié)構(gòu)與 隊(duì)列 相反.

由于棧具有先進(jìn)后出的特點(diǎn), 所以任何不在棧頂?shù)脑囟紵o(wú)法訪問(wèn). 為了得到棧底的元素, 必須拿掉上面的元素.

對(duì)棧的三種主要操作:

將一個(gè)元素壓入棧使用push().

將一個(gè)元素彈出棧使用pop().

預(yù)覽棧頂?shù)脑?peek().

這里需要注意的是的第三種. pop()方法雖然可訪問(wèn)棧頂?shù)脑? 但是調(diào)用該方法后, 棧頂元素也就從棧中被永久刪除. peek()只返回棧頂元素, 而不刪除.

這三種為主要方法, 但是棧還有其他方法和屬性. clear()清除棧內(nèi)所有元素, length屬性記錄棧內(nèi)元素的個(gè)數(shù). 我們還可以定義一個(gè)empty屬性, 用以表示棧內(nèi)是否含有元素, 不過(guò)使用length屬性也可以達(dá)到相同目的.

棧的實(shí)現(xiàn)

實(shí)現(xiàn)一個(gè)棧, 首要條件是決定存儲(chǔ)數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu). 這里采用數(shù)組.

從定義Stack類(lèi)的構(gòu)造函數(shù)開(kāi)始:

class Stack {
    constructor() {
        this._dataStore = [];
        this._top = 0;
    }
    push(element) {
        this._dataStore[this._top++] = element;
    }
    pop(element) {
        return this._dataStore[--this._top];
    }
    peek() {
        return this._dataStore[this._top - 1];
    }
    length() {
        return this._top;
    }
    clear() {
        this._top = 0;
    }
}

用數(shù)組_dataStore保存棧內(nèi)元素, 構(gòu)造函數(shù)將其初始化為一個(gè)空數(shù)組. 變量_top記錄棧頂位置, 被構(gòu)造函數(shù)初始化為0, 表示棧頂對(duì)應(yīng)數(shù)組的其實(shí)位置0. 如果有元素被壓入棧, 該變量將隨之變化.

push()方法. 向棧中壓入一個(gè)新元素時(shí), 需要將其保存在數(shù)組中變量_top所對(duì)應(yīng)的位置, 然后將_top加1, 讓其指向數(shù)組中下一個(gè)空位置. 這里要注意++操作符的位置, 它放在變量后面, 新元素就會(huì)放在_top當(dāng)前值對(duì)應(yīng)位置, 然后再加1, 指向下一個(gè)位置.

pop()方法. 恰好與push()方法相反. 有返回值, 返回棧頂元素. 這里要注意--操作符的位置, 它放在變量前面, 先對(duì)_top減1然后再刪除對(duì)應(yīng)位置元素.

peek()方法. 返回?cái)?shù)組的第_top - 1個(gè)位置的元素, 即棧頂元素. 如果對(duì)空棧調(diào)用peek(), 結(jié)果為undefined.

length()方法. 通過(guò)返回變量_top值的方式返回棧內(nèi)的元素個(gè)數(shù).

clear()方法. 將變量_top設(shè)為0, 輕松清空一個(gè)棧.

實(shí)例 數(shù)制間的相互轉(zhuǎn)換

可以利用棧將一個(gè)數(shù)字從一種數(shù)制轉(zhuǎn)化成另一種數(shù)制. 假設(shè)將數(shù)字n轉(zhuǎn)化為以b為基數(shù)的數(shù)字, 實(shí)現(xiàn)轉(zhuǎn)化的算法如下.

最高位為n % b, 將此位壓入棧.

使用n / b代替n.

重復(fù)步驟1和2, 直到n等于0, 且沒(méi)有余數(shù).

持續(xù)將棧內(nèi)元素彈出, 直到棧為空, 依次將這些元素排列, 就得到轉(zhuǎn)換后數(shù)字的字符串形式.

注意: 此算法只針對(duì)基數(shù)為2~9的情況.

function mulBase(num, base) {
    var s = new Stack();
    
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    
    
    var converted = "";
    while(s.length() > 0) {
        converted += s.pop();
    };
    return converted;
};

console.log(mulBase(32, 2)); // 得到32的二進(jìn)制值: 100000
console.log(mulBase(88, 8)); // 得到88的八進(jìn)制值: 130

回文

回文: 一個(gè)單詞、短語(yǔ)和數(shù)字, 從前往后寫(xiě)和從后往前寫(xiě)都是一樣的. eg: 單詞"dad"、"racecar"就是回文; 忽略空格和標(biāo)點(diǎn)下面這個(gè)句子也是回文: "A man, a plan, a canal: Panama"; 數(shù)字101也是回文.

使用?？梢暂p松判斷一個(gè)字符串是否是回文. 我們將拿到的字符串的每一個(gè)字符按從左至右的順序入棧. 當(dāng)所有字符都入棧后, 棧內(nèi)就保存了一個(gè)反轉(zhuǎn)后的字符串, 最后的字符在棧頂, 第一個(gè)字符在棧底.
字符串完整壓入棧內(nèi)后, 通過(guò)持續(xù)彈出棧中的每一個(gè)字母就可以得到一個(gè)新的字符串, 該字符串剛好與原來(lái)的字符串順序相反. 我們只需要比較這兩個(gè)字符串即可.

function isPalindrome(word) {
    const s = new Stack();
    
    for(let w of word) {
        s.push(w)
    };
    let rword = "";
    while(s.length() > 0) {
        rword += s.pop();
    };

    return word === rword;
};

console.log(isPalindrome("hello")); // false
console.log(isPalindrome("dad")); // true

遞歸演示

棧常常被用來(lái)實(shí)現(xiàn)編程語(yǔ)言, 使用棧實(shí)現(xiàn)遞歸即為一例. 這里只是用棧來(lái)模擬遞歸過(guò)程.

為了演示如何用棧實(shí)現(xiàn)遞歸, 考慮一下求階乘函數(shù)的遞歸定義. 首先看5的階乘是怎么定義的: 5! = 5 * 4 * 3 * 2 * 1 = 120

下面是一個(gè)遞歸函數(shù), 可以計(jì)算任何數(shù)字的階乘:

function factorial(n) {
    if(n === 0) return 1;

    return n * factorial(n - 1);
};

// 尾掉優(yōu)化
function factorial(n, total = 1) {
    if(n === 0) return total;

    return factorial(n - 1, n * total);
};

console.log(factorial(5)); // 120

使用棧來(lái)模擬計(jì)算5!的過(guò)程, 首先將數(shù)字從5到1入棧, 然后使用一個(gè)循環(huán), 將數(shù)字挨個(gè)彈出連乘, 就得到正確答案

下面使用棧模擬遞歸過(guò)程:

function fact(n) {
    const s = new Stack();

    while(n > 1) {
        s.push(n--);
    };
    
    let product = 1;
    while(s.length() > 0) {
        product *= s.pop();
    };
    
    return product;
};

console.log(fact(5)); // 120

判斷一個(gè)算數(shù)表達(dá)式中的括號(hào)是否匹配

例如判斷表達(dá)式為2.3 + 23 / 12 + (3.14159 * 0.24的算數(shù)表達(dá)式的括號(hào)是否匹配.

function fn(express) {
    const s = new Stack();
    
    for (let i = 0; i < express.length; ++i) {
        if (express[i] === `(`) {
            s.push(i);
        } else if (express[i] === `)`) {
            s.pop();
        }
    };
    console.log(`在第${s.peek()}個(gè)字符是不匹配的括號(hào)`)
};

fn("2.3 + 23 / 12 + (3.14159 * 0.24"); // 在第16個(gè)字符是不匹配的括號(hào)

中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式

表達(dá)式詳解
一個(gè)算數(shù)表達(dá)式的后綴表達(dá)形式如下:
op1 op2 operator
使用兩個(gè)棧, 一個(gè)用來(lái)存儲(chǔ)操作數(shù), 另一個(gè)用來(lái)存儲(chǔ)操作符, 設(shè)計(jì)并實(shí)現(xiàn)一個(gè)函數(shù), 該函數(shù)可以將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式, 利用棧堆該表達(dá)式求值.

const express = "1+((2+3)*4)-5";

function fn(express) {
    const s1 = new Stack(); // 操作符棧
    const s2 = new Stack(); // 操作數(shù)棧
    const arr = express.split("");
    arr.forEach((i, index) => {
        if(/^[0-9]*$/.test(i)) {
            s2.push(i)
        } else if(["+", "-", "*", "/"].includes(i)) {
            if(s1.length() === 0 || s1.peek() === "(") {
                s1.push(i)
            } else if (["*", "/"].includes(i) && ["+", "-"].includes(s1.peek())) {
                s1.push(i)
            } else {
                s2.push(s1.pop());
                if(s1.length() === 0 || s1.peek() === "(") {
                    s1.push(i);
                }
            }
        } else if (i === "(") {
            s1.push(i);
        } else if (i === ")") {
            while(s1.peek() !== "(") {
                s2.push(s1.pop());
            }
            s1.pop();
        }
    });
    
    while(s1.length() > 0) {
        s2.push(s1.pop());
    };

    let str = ""
    while(s2.length() > 0) {
        str += ` ${s2.pop()}`;
    };
    
    return str;
};

console.log(fn(express))

佩茲糖果盒

現(xiàn)實(shí)生活中的例子是佩茲糖果盒. 想象一下你有一盒佩茲糖果, 里面塞滿了紅色、黃色和白色的糖果, 但是你不喜歡黃色的糖果. 使用棧(有可能用到多個(gè)棧) 寫(xiě)一段程序, 在不改變盒內(nèi)其它糖果疊放順序的基礎(chǔ)上, 將黃色糖果移除.

const boxS = new Stack(); 
boxS.push("red");
boxS.push("yellow");
boxS.push("white");
boxS.push("white");
boxS.push("yellow");
boxS.push("yellow");
boxS.push("red");
boxS.push("red");
boxS.push("white");
boxS.push("yellow");
boxS.push("red");

function changeFn(sourceStack) {
    const s1 = new Stack(); 
    const s2 = new Stack(); 
    const resultS = new Stack(); 

    while(sourceStack.length() > 0) {
        if(sourceStack.peek() === "yellow") {
            s1.push(sourceStack.pop())
        } else {
            s2.push(sourceStack.pop())
        }
    };

    while(s2.length() > 0) {
        resultS.push(s2.pop());
    };
    return resultS;
};
changeFn(boxS);