JavaScript数据结构与算法—— 栈

我们可以在数组的任何位置上删除或者添加元素，但有时候我们还需要在元素的添加或删除时有更多控制的数据结构，有两种数据结构类似于数组，但在添加或删除元素时更为可控，它们就是栈和队列。

本节主要介绍栈。

1.栈数据结构

栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，叫做栈顶，另一端叫栈底。在栈中，新元素靠近栈顶，旧元素接近栈底。如下图所示：

2.创建栈

// 首先创建一类表示栈
function Stack(){
    let items = []; // 选择数组来保存栈中的元素 
    //各种属性和方法
}

下面要为栈声明一些方法：

push()  //  添加一个或多个新元素到栈顶
pop()  //  移除栈顶元素，同时返回被移除的元素
peek()  // 仅仅返回栈顶元素，不对栈做任何修改
isEmpty()  //  如果栈中没有元素返回true，否则返回false
clear()  // 移除栈中所有元素
size()  // 返回栈中元素的个数（和数组length类似）

2.1 向栈添加元素

this.push() = function(element) {
    items.push(element);
}

2.2 从栈移除元素

this.pop = function() {
    items.pop();
}

2.3 查看栈顶元素

this.peek = function() {
    return items[items.length - 1];
}

2.4 查看栈是否为空

this.isEmpty = function(){
    return items.length === 0;
}
this.size = function() {
    return items.lenght;
}

2.5 清空和打印栈元素

this.clear = function() {
    items = [];
} 
this.print = function() {
    console.log(items.toString());
}

经过上述的方法的添加，我们就完整的创建了一了个栈 Stack。

3.栈的应用—十进制转N进制

首先我们写出将十进制转为二进制：

function divideBy2(decNum) {
    var remStack = new Stack(),
        rem,
        binaryString = '';
    // 将十进制数除2的余数放入一个stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % 2);
        // 入栈
        remStack.push(rem);
        decNum = Math.floor(decNum / 2);
    }    
    // 从栈中取出转化为字符串然后连接起来构成二进制
    while(!remStack.isEmpty()) {
        // 出栈
        binaryString += remStack.pop().toString();
    } 
    return binaryString;
}

下面十进制转化N进制算法

function divideByN(decNum, n) {
    var remStack = new Stack(),
        rem,
        binaryString = '',
        digits = '0123456789ABCDEF';
    // 将十进制数除N的余数放入一个stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % n);
        // 入栈
        remStack.push(rem);
        decNum = Math.floor(decNum / n);
    }    
    // 从栈中取出转化为字符串然后连接起来构成二进制
    while(!remStack.isEmpty()) {
        // 出栈 使用digits方便在16进制中做个对应转化
        binaryString += digits[remStack.pop()];
    } 
    return binaryString;
}