栈数据结构

• 描述
  栈是一种遵从后进先出原则的有序集合。新添加或待删除的元素都保存在栈的同一端叫栈顶，另一端叫栈底，在栈里新元素靠近栈顶，旧元素靠近栈底。

创建一个基于数组的栈

• 描述
  栈中需要声明的方法：

1. push()：添加一个或几个新元素到栈顶。
2. pop():移除栈顶的元素，同时返回移除的元素。
3. peek():返回栈顶的元素同时不对栈做任何修改。
4. isEmpty()：如果栈为空返回true,否则返回false。
5. clear():移除栈中所有元素。
6. size():返回栈里的元素个数。

• 实现代码

class Stack{
    constructor(){
        this.items=[]
    }
    // 像栈顶添加元素
    push(element){
        this.items.push(element)
    }
    // 移除栈顶元素返回被移除的元素
    pop(){
        return this.items.pop()
    }
    // 查看栈顶的元素
    peek(){
        return this.items[this.items.length-1]
    }
    // 检查栈是否为空
    isEmpty(){
        return this.items.length===0
    }
    // 判断栈的长度
    size(){
    return this.items.length
    }
    // 清空栈的元素
    clear(){
        this.items=[]
    }
}

创建一个基于JavaScript对象的Stack类

• 描述
  基于对象的栈实现过程与基于数组的实现类似，只不过使用对象算法复杂度更低。
• 实现代码

class Stack{
    constructor(){
        this.count=0
        this.items={}
    }
    // 向栈顶插入元素
    push(element){
      this.items[this.count]=element
      this.count++
    }
    // 验证栈是否为空和大小
    size(){
        return this.count
    }
    isEmpty(){
        return this.count===0
    }
    // 从栈中弹出元素同时返回弹出的元素
    pop(){
        if(this.isEmpty()){
            return undefined
        }
        this.count--
        const result=this.items[this.count]
        delete this.items[this.count]
        return result
    }
    // 查看栈顶的值
    peek(){
        if(this.isEmpty()){
            return undefined
        }
        return this.items[this.count-1]
    }
    // 清空栈
    clear(){
        this.items={}
        this.count=0
    }
    // 创建toString方法
    toString(){
        if(this.isEmpty()){
            return undefined
        }
        let objString=`${this.items[0]}`
        for(let i=1;i<this.count;i++){
            objString=`${objString},${this.items[i]}`
        }
        return objString
    }
}

栈解决十进制转二进制问题

• 实现过程如下

function decimalToBinary(decNumber){
    const remStack=new Stack()
    let number=decNumber
    let rem
    let binaryString=''
    while(number>0){
        rem=Math.floor(number%2)
        remStack.push(rem)
        number=Math.floor(number/2)
    }
    while(!remStack.isEmpty()){
    binaryString+=remStack.pop().toString()
    }
    return binaryString
}