栈

什么是栈？

后入先出(LIFO)，栈就是和列表类似的一种数据结构，也是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。

栈顶: 栈内的元素只能通过列表的一端访问，这一端称为栈顶，任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

栈的操作

入栈
出栈
返回栈的栈顶元素

还是从一个构造函数开始：

function Stack() {
    this.dataStore = [];//用数组 dataStore 保存栈内元素 
    this.top = 0;       //用于记录哪个位置加入新元素
    this.push = push;   //入栈
    this.pop = pop;     //返回移出的栈顶元素 
    this.peek = peek;   //返回当前的栈顶元素 
    this.clear = clear; //清空
    this.length = length; //返回栈内元素个数
}

下面的几个方法同构造列表时一个原理，不多做解释。

入栈

function push(element) {
    this.dataStore[this.top++] = element;
}

返回移出的栈顶元素

function pop() {
     return this.dataStore[--this.top];
}

peek() 方法返回数组的第 top-1 个位置的元素，即真正的栈顶元素

function peek() {
    return this.dataStore[this.top-1];
}

栈内存储了多少个元素

function length() {
    return this.top;
}

清空栈

function clear() {
     this.top = 0;
}

栈的应用

数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数的数字，实现转换的算法如下

最高位为 n % b，将此位压入栈。
使用n/b代替n。
重复步骤 1 和 2，直到 n 等于 0，且没有余数。
持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式。

此算法只针对基数为 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;
}

var num = 32;
var base = 2;
var newNum = mulBase(num, base);

console.log(num + " converted to base " + base + " is " + newNum);
// 32 converted to base 2 is 100000

num = 125;
base = 8;
var newNum = mulBase(num, base);

console.log(num + " converted to base " + base + " is " + newNum);
//125 converted to base 8 is 175

回文

回文是指这样一种现象:一个单词、短语或数字，从前往后写和从后往前写都是一样的。比如，单词“dad”、“racecar”就是回文;如果忽略空格和标点符号，下面这个句子也是回文，“A man, a plan, a canal: Panama”;数字 1001 也是回文。

使用栈实现回文。原理：将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底，字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。这时只需要比较这两个字符串即可，如果它们相等，就是一个回文。

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.");
    }
    //hello is not a palindrome.
    
    word = "racecar"
    if (isPalindrome(word)) {
       console.log(word + " is a palindrome.");
    } else {
       console.log(word + " is not a palindrome.");
    }
    //racecar is a palindrome.

递归

为了演示如何用栈实现递归，先看一下求阶乘函数的递归，首先看看5的阶乘是怎么实现的:

5! = 5×4×3×2×1 = 120

下面是一个递归函数，可以计算任何数字的阶乘:

function factorial(n) { 
    if(n===0){
	return 1; 
    } else {
       return n * factorial(n-1);
    } 
}

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

使用栈来模拟计算 5! 的过程，原理：首先将数字从5到1压入栈，然后使用一个循环，将数字挨个弹出连乘，就得到了正确的答案:120。

function fact(n) {
    var s = new Stack(); while(n>1){
       s.push(n--);
    }
    var product = 1;
    while (s.length() > 0) {
        product *= s.pop();
    }
    return product;
}

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