自定義棧

function Stack() {
    // 保存棧內(nèi)元素
    this.dataStore = [];
    // 變量 top 記錄棧頂位置
    this.top = 0;
}

Stack.prototype = {
    // 向棧中壓入一個新元素
    push: function(element) {
        // 注意 ++ 操作符的位置，放在 this.top 的后面，這樣新入棧的元素就被放在 top 的當前值對應(yīng)的位置，然后再將變量 top 的值加1，指向下一個位置
        this.dataStore[this.top++] = element;
    },
    // 返回數(shù)組的第 top - 1 個位置的元素，即棧頂元素，peek() 方法則只返回棧頂元素，而不刪除它
    peek: function() {
        return this.dataStore[this.top - 1];
    },
    // 方位棧頂?shù)脑?，但是調(diào)用 pop 方法之后，棧頂元素也從棧中被永久性地刪除了
    pop: function() {
        return this.dataStore[--this.top];
    },
    // 返回變量 top 值的方式返回棧內(nèi)的元素個數(shù)
    length: function() {
        return this.top;
    },
    // 清空棧
    clear: function() {
        this.top = 0;
    }
};

棧的應(yīng)用

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());   // length: 3
console.log(s.peek());                  // Bryan

var popped = s.pop();
console.log("The popped element is: " + popped);    // The popped element is: Bryan
console.log(s.peek());                              // Raymond

s.push("Cynthia");
console.log(s.peek());                              // Cynthia
s.clear();
console.log("length: " + s.length());               // length: 0
console.log(s.peek());                              // undefined
s.push("Clayton");
console.log(s.peek());                              // Clayton

判斷給定字符串是否是回文

function isPalindrome(word) {
    var s = new Stack();
    for (var i = 0; i < word.length; ++i) {
        s.push(word[i]);
    }
    
    var rword = "";
    while (s.length() > 0) {
        rword += s.pop();
    }
    
    if (word == rword) {
        return true;
    } else {
        return false;
    }
}

var word = "hello";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome.");
} else {
    console.log(word + " is not a palindrome");
}

word = "racecar";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome.");
} else {
    console.log(word + " is not a palindrome.");
}

利用棧將一個數(shù)字從一種數(shù)制轉(zhuǎn)換成另一種數(shù)制
假設(shè)想將數(shù)字 n 轉(zhuǎn)換為以 b 為基數(shù)的數(shù)字，實現(xiàn)轉(zhuǎn)換的算法如下：
（1）最高位為 n % b，將此位壓入棧。
（2）使用 n / b 代替 n。
（3）重復(fù)步驟 1 和 2，直到 n 等于 0，且沒有余數(shù)。
（4）持續(xù)將棧內(nèi)元素痰出，直到棧為空，依次將這些元素排列，就得到轉(zhuǎn)化后數(shù)字的字符串形式。

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

使用棧來判斷一個算術(shù)表達式中的括號是否匹配

// 對于表達式進行掃描，遇到'('、'['、'{'就進棧，遇到')'、']'、'}'就出棧，表達式掃描完畢之后，該棧應(yīng)該為空。
function matching(exp) {
    var s = new Stack();
    
    var left = '{[(';
    var right = '}])';
    
    var flag = true;
    
    for (var i = 0; i < exp.length; i++) {
        if (left.includes(exp[i])) {
            s.push(exp[i]);
        } else if (right.includes(exp[i])) {
            var popValue = s.pop();
            if (left.indexOf(popValue) !== right.indexOf(exp[i])) {
                flag = false;
            } else {
                flag = true;
            }
        }
    }
    return flag;                                
}

var exp1 = "(1+2)*2+{3+[(5+3)*2)]}";
if (matching(exp1)) {
    console.log("表達式 " + exp1 + " 括號是匹配的");
} else {
    console.log("表達式 " + exp1 + " 括號是不匹配的");
}

佩茲糖果盒 —— 你有一盒佩茲糖果，里面塞滿了紅色、黃色和白色的糖果，但是你不喜歡黃色的糖果。
使用棧（有可能用到多個棧）寫一段程序，在不改變盒內(nèi)其它糖果疊放順序的基礎(chǔ)上，將黃色糖果移出。

var sweetBox = new Stack();
sweetBox.push("red");
sweetBox.push("yellow");
sweetBox.push("red");
sweetBox.push("yellow");
sweetBox.push("white");
sweetBox.push("yellow");
sweetBox.push("white");
sweetBox.push("yellow");
sweetBox.push("white");
sweetBox.push("red");

function getColor(element, stack) {
    var getColorStack = new Stack();
    var setColorStack = new Stack();
    
    while(stack.length() > 0) {
        if (stack.peek() == element) {
            getColorStack.push(element);
            stack.pop();
        } else {
            setColorStack.push(stack.peek());
            stack.pop();
        }
    }
    
    while(setColorStack.length() > 0) {
        stack.push(setColorStack.peek());
        setColorStack.pop();
    }
    
    console.log(stack.peek());
}

getColor("red", sweetBox);