主页 > 教程合集 > Html/css >

JS实现栈结构的方法

时间:2021-04-12 阅读:0

实现栈结构


//创建栈
function Stack (){
        let 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())
        }
}
 

JS实现栈结构的方法

ES6改造


//使用Symbol添加私有属性
class Stack {
        let _items = Symbol()
        constructor(){
                this[_items] = []
        }
        push(element){
                this[_items].push(element)
        }
}

//可以拿到所有的symbol对象
Object.getOwnPropertySymbols(Stack)

//使用weakMap
const items = new weakMap()

class Stack {
        constructor(){
                items.set(this,[])
        }
        push(element){
                let s = items.get(this)
                s.push(element)
        }
        pop(){
                let s = items.get(this)
                let r = s.pop()
                return r
        }
}

//利用闭包实现私有属性
let Stack = (function(){
      const items = new WeackMap()
     
      class Stack {
        constructor(){
                items.set(this,[])
        }
        push(element){
                let s = items.get(this)
                s.push(element)
        }
        pop(){
                let s = items.get(this)
                let r = s.pop()
                return r
        }
}
      return Stack
})()
 

进制转换


//10进制转2进制
function divideBy2(decNumber){
        var remStack = new Stack(),
        rem,
        binaryString = '';
       
        while(decNumber > 0){
                rem = Math.floor(decNumber % 2)
                remStack.push(rem)
                decNumber = Math.floor(decNumber/ 2)
        }
       
        while(!remStack.isEmpty()){
                binaryString += remStack.pop().toString()
        }
}

//任意进制转换
function baseConverter(decNumber,base){
    const remStack = new Stack();
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    let number = decNumber;
    let rem;
    let baseString = '';

    if (!(base >= 2 && base <= 36)) {
        return '';
    }

    while (number > 0) {
        rem = Math.floor(number % base);
        remStack.push(rem);
        number = Math.floor(number / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];
    }

    return baseString;
}
 

平衡圆括号


function balancedSymbols(symbols){
        const stack = new Stack()
        const opens = `([{`
        const closers = `)]}`
       
        let balanced = true
        let index = 0
        let symbol
        let top
       
        while(index < symbols.length && balanced){
                symbol = symbols[index]
               
                if(opens.indexOf(symbol) >= 0){
                        stack.push(symbol)
                } else if(stack.isEmpty()){
                        balanced = false
                } else {
                        top = stack.pop()
                        if(!(opens.indexOf(top) === closers.indexOf(symbol))){
                                balanced = false
                        }
                }
               
                index ++
        }
        return balanced && stack.isEmpty()
}
 

汉诺塔

递归,即定义一组基本操作,这组操作将规模小一点(或大一点)的操作当做一个整体——无需关心它的细节,只当它已经完成了——然后执行剩下的操作。而在更小或更大的规模中也依此操作,直到规模达到预定值。


function towerOfHanoi(plates,source,helper,dest,sourceName,helperName,destName,moves = []){
        if(plates <= 0){
                return moves
        }
        if(plates === 1){
                dest.push(source.pop())
                const move = {}
                move[sourceName] = source.toString()
                move[helperName] = helper.toString()
                move[destName] = dest.toString()
                moves.push(move)
        }
        else {
                towerOfHanoi(
                        plates - 1,
                        source,
                        dest,
                        helper,
                        sourceName,
                        destName,
                        helperName,
                        moves
                )
                dest.push(source.pop())
                const move = {}
                move[sourceName] = source.toString()
                move[helperName] = helper.toString()
                move[destName] = dest.toString()
                moves.push(move)
                towerOfHanoi(
                        plates - 1,
                        helper,
                        source,
                        dest,
                        helperName,
                        sourceName,
                        destName,
                        moves
                )
        }
        return moves
}

function hanoiStack(plates){
        const source = new Stack()
        const dest = new Stack()
        const helper = new Stack()
       
        for(let i = plates; i > 0; i --){
                source.push(i)
        }
       
        return towerOfHanoi(
                plates,
                source,
                helper,
                dest,
                source,
                helper,
                dest
        )
}

function hanoi(plates,source,helper,dest,moves = []){
        if(plates <= 0){
                return moves
        }
        if(plates === 1){
                moves.push([source,dest])
        } else {
                hanoi(
                        plates - 1,
                        source,
                        dest,
                        helper,
                        moves
                )
                moves.push([source,dest])
        }
        return moves
}
//用栈来实现汉诺塔
console.log(hanoiStack(3));
//用递归来来实现
console.log(hanoi(3, 'source', 'helper', 'dest'));
 

开通特权,即可免费下载全站所有千余TB网络资源,点击 >>> 资源目录 查看所有资源,覆盖音乐、影视、有声书、电子书、漫画、动漫、课程等,不限时间次数,永久免费,点击 >>> 特权详情 了解更多!

余斗余斗
  • 版权声明:原创文章由发表在Html/css分类下,2021-04-12最后更新,转载注明出处。

相关推荐

返回顶部