数据结构-栈

[iuapwuxiaoliang]

数据结构-栈

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或者待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈的创建

JS 中没有栈这个数据结构，但可以用数组 Array 模拟实现栈相关的全部功能。

function Stack(){
   var items = [];
}

对栈操作的相关方法有：

• push(element) -- 添加新元素到栈顶。
• pop() -- 移除栈顶的元素，同时返回被移除的元素。
• peek() -- 返回栈顶的元素，但不对栈做任何操作。
• isEmpty() -- 如果栈里没有任何元素就返回true,否则返回false。
• clear() -- 移除栈里的所有元素。
• size() -- 返回栈里的元素个数。

基本实现代码：

function Stack(){
    var items = [];
    
    this.push = function(element){
        items.push(element);
    }
    
    this.pop = function(){
        return items.pop();    
    }
    
    this.peek = function(){
        return items[items.length-1];
    }
    
    this.isEmpty = function(){
        return items.length == 0;
    }
    
    this.size = function(){
        return items.length;
    }
    
    this.clear = function(){
        items = [];
    }
    
    this.print = function(){
        console.log(items.toString());
    }
}

应用场景一：进制转换问题

如何将十进制与其他进制进行转换，可以用stack来解决这个问题。
比如要把十进制转化成二进制，可以将十进制数字和2相除，直到结果是0为止。

function baseConverter(decNumber,base){
    var remStack = new Stack(), rem, baseString='', digits = '0123456789ABCDEF';
    while(decNumber > 0){
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    while(!remStack.isEmpty()){
        baseString += digits[remStack.pop()];
    }
    return baseString;
}

console.log(baseConverter(100345,2));
console.log(baseConverter(100345,8));
console.log(baseConverter(100345,16));

应用场景二：判断括号的闭合（LeeCode）

应用场景三：JS中的事件回调