JavaScript 栈

[Checkson]

简介

栈就是和列表类似的一种数据结构，它可用来解决计算机世界里的很多问题。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，俗称“后进先出”，所以这样的操作很快，而且容易实现。栈的使用遍布程序语言实现的方方面面，从表达式求值到处理函数调用。

定义

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。就像日常生活中有很多个盘子堆叠起来，我们只能在这些盘子最上面取盘子和加盘子。

栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用 push() 方法，出栈使用 pop() 方法。另一个常用的操作是预览栈顶的元素。pop() 方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek() 方法则只返回栈顶元素，而不删除它。

栈（Stack）类实现

完整代码地址，这里我们采用的底层数据结构依然是数组。

1. 构造函数

构造函数中，有两个属性，一个是 dataList ，用来存储栈中的元素；另一个是 top，用来记录当前栈顶的指针位置，默认为-1。

function Stack () {
    this.dataList = [];
    this.top = -1;
}

2. push：入栈操作

Stack.prototype.push = function (el) {
    this.dataList[++this.top] = el;
}

3. pop：出栈操作

Stack.prototype.pop = function () {
    return this.dataList[this.top--];
}

4. peek：获取栈顶元素操作

Stack.prototype.peek = function () {
    return this.dataList[this.top];
}

5. clear：清除栈中所有元素

Stack.prototype.clear = function () {
    delete this.dataList;
    this.dataList = [];
    this.top = -1;
}

6. 获取栈中元素个数

Stack.prototype.length = function () {
    return this.top + 1;
}

栈（Stack）类测试

var st = new Stack();
st.push(1);
st.push(2);
console.log(st.peek()); // 2
st.push(3);
console.log(st.length()); // 3
console.log(st.peek()); // 3
console.log(st.pop()); // 3
console.log(st.peek()); // 2
st.clear();
console.log(st.length()); // 0

栈（Stack）类实战

1. 简单的数值之间转换

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

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

使用栈来实现这个算法，就是小菜一碟（此算法只使用2-9进制的数），具体实现如下：

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

2. 回文

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

使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。

字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可，如果它们相等，就是一个回文。

具体实现算法如下：

function isPalindrome (word) {
    var st = new Stack();
    word += ''; // 转换为字符串
    for (var i = 0, len = word.length; i < len; i++) {
        st.push(word[i]);
    }
    var reverseWord = "";
    while (st.length() > 0) {
        reverseWord += st.pop();
    }
    return word === reverseWord;
}