栈.md

栈的介绍

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在末尾,称作栈顶。在栈里，新元素靠近栈顶，旧元素在栈底(例如书架) 。栈在编译器和内存中保存变量、方法调用等

创建一个栈 stack

function Stack(){
    this.store = []
    //从栈中移除元素
    this.pop = function(){
        return this.store.pop()
    }
    //�添加一个元素
    this.push = function(element){
        this.store.push(element)
    }
    //返回最后一个添加的�元素
    this.peek = function(){
        return this.store[this.store.length-1]
    }
    this.length = function(){
        return this.store.length
    }
    //判断内部�数组长度是否为0
    this.isEmpty = function(){
        return this.store.length === 0
    }
    //清空栈
    this.clear = function(){
        delete this.store
        this.store = []
    }
    //返回栈内所有的元素
    this.print = function(){
        return this.store.toString()
    }
}

栈的应用

十进制转为二进制

function transformBy2(target){
    var tranStack  = new Stack(),
        remainder,
        result = ''
    while(target>0){
        remainder = Math.floor(target%2)
        tranStack.push(remainder)
        target  = Math.floor(target/2)
    }
    console.log(tranStack,'tranStack')
    while(!tranStack.isEmpty()){
        result += tranStack.pop().toString()
    }
    return result
}

基于之前的算法，转换为任意进制

function transformAny(target,base){
    var tranStack = new Stack(),
    remainder,
    result = '',
    linkText = '0123456789ABCDEF'
    while(target>0){
        remainder = Math.floor(target % base)
        tranStack.push(remainder)
        target = target / base
    }
    while(!tranStack.isEmpty()){
        result += linkText[tranStack.pop()]
    }
    return result
}

回文 类似于dad 、mom、 racecar等这种从前往后和从后往前一样的 function isBackText(str){ var s = new Stack() for(let i=0;i<str.length;i++){ s.push(str[i]) } let reStr =''; while(s.length>0){ reStr+=s.pop() } return reStr === str } 使用栈模拟递归 function fatchrial(n){ if(n===0){ return 1 }else{ return nfatchrial(n-1) } } ====> function fatchStack(n){ let s = new Stack() while(n>1){ s.push(n--) } let item = 1 ; while(s.length()>0){ item=s.pop() } return item }

有关栈的题目

现实生活中栈的一个例子是佩兹糖果盒。想象一下你有一盒佩兹糖果,里面塞满了红 色、黄色和白色的糖果,但是你不喜欢黄色的糖果。使用栈(有可能用到多个栈)写一 段程序,在不改变盒内其他糖果叠放顺序的基础上,将黄色糖果移出。

解题思路：从放糖果的栈中(stack)中，将不喜欢的放入不喜欢的栈(hateStack)中，然后将喜欢的放入喜欢栈(likeStack)中，然后再从喜欢的栈中把所有的元素逐个放回原来的栈(stack)中 function dealColor(element,stack){ let hateStack = new Stack() let likeStack = new Stack() while(stack.length()>0){ if(stack.peek() === element){ hateStack.push(element) }else{ likeStack.push(stack.peek()) } stack.pop() } while(likeStack.length()>0){ stack.push(likeStack.pop())

    }
}