js学习栈以及使用栈实现约瑟夫环问题

广告位

js学习栈 一、栈的结构 栈是常用的数据结构,遵循先进后出或后进先出的原则(LIFO),结构如下: 只能在一端…

js学习栈

一、栈的结构

栈是常用的数据结构,遵循先进后出或后进先出的原则(LIFO),结构如下:

js学习栈以及使用栈实现约瑟夫环问题
只能在一端进行插入和删除操作,即栈顶,另一端成为栈底;向栈中添加一个元素成为进栈或压栈,从栈顶删除一个元素成为出栈或弹出栈。

函数调用栈:通过函数的形式形成栈方式的调用

        function A(){             B();             console.log('A已执行完');         }         function B(){             C();             console.log('B已执行完');         }         function C(){             console.log('C已执行完');         }         A(); 

二、封装栈(形成栈结构)

栈与数组或链表挂钩,但是仅具备它们之中的部分方法:

(1)push():进栈
(2)pop():出栈并返回出栈元素
(3)peek():查看栈顶元素
(4)isEmpty():判断栈是否为空
(5)clear():清空栈
(6)size():查看栈元素个数

封装栈常用的是构造函数和类的方法:

使用数组方式封装栈:

            //构造函数方式             function Stack(){             this.item = [];             Stack.prototype.push = function(element){                 this.item.push(element);             }             Stack.prototype.pop = function(element){                 return this.item.pop(element);             }             Stack.prototype.peek = function(){                 return this.item[this.item.length - 1];             }             Stack.prototype.isEmpty = function(){                 return this.item.length == 0;             }             Stack.prototype.clear = function(){                 this.item = [];             }             Stack.prototype.size = function(){                 return this.item.length;             }         }     //类   class Stack{     constructor(){         this.item = [];     }     //入栈     push(element){         this.item.push(element);     }     //出栈     pop(element){         return this.item.pop(element);     }     //查看栈顶元素     peek(){         return this.item[this.item.length - 1];     }     //判断栈是否为空     isEmpty(){         return this.item.length == 0;     }     //清空栈     clear(){         this.item = [];     }     //获取栈的大小     size(){         return this.item.length;     }     toString() {         let re = '';         for (let i = 0; i < this.item.length; i++) {             const element = this.item[i];             re += "," + element;         }         return re.slice(1);     } } 

三、栈的实际运用

例1、十进制转换成二进制

          function transformToBin(transNum){             let stack = new Stack();             while(transNum > 0){                 let remiander = transNum % 2;                 stack.push(remiander);                 transNum = Math.floor(transNum / 2);             }                          let twoBinNum = '';             while(!stack.isEmpty()){                 twoBinNum += stack.pop();             }             return Number(twoBinNum);         } 

例2、对例1的改进,可以根据输入的进制来将十进制转换为任意进制

        //改进:可以自己决定从十进制转换的进制         function transformTo(transNum, base){             let stack = new Stack();             while(transNum > 0){                 let remiander;                 if(base < 10){                     remiander = transNum % base;                     stack.push(remiander);                     transNum = Math.floor(transNum / base);                 }else if(base >= 10){                     remiander = transNum % base;                     if(remiander - 10 >= 0){                         let trasRemainder = String.fromCharCode(65 + (remiander - 10));                         stack.push(trasRemainder);                     }else{                         stack.push(remiander);                     }                     transNum = Math.floor(transNum / base);                 }             }                          let binNum = '';             while(!stack.isEmpty()){                 binNum += stack.pop();             }             return binNum;         } 

例3、使用栈实现约瑟夫环

约瑟夫环:m个人围成一个圈, 指定一个数字n,从第一个人开始报数, 每轮报到n的选手出局,由下一个人接着从头开始报,最后一个人是赢家。其中m>1,n>2。

        //用栈:         function josephRingStack(people, num, winNum) {             //数据不合法时             if (people < 1 || num < 2) {                 return -1;             }             //创建数组用于存放存活下来的人             let arr = [];             //创建一个栈             let stack = new Stack();             //将所有人倒着进栈存放编号             for (let i = people; i > 0; i--) {                 stack.push(i);             }             //n用于计数当前数到的数字             let n = 0;             check(n);             function check(n) {                 //使用变量保存栈的大小,保证for循环的完整性                 let len = stack.size();                 for (let i = 0; i < len; i++) {                     //这里循环条件不能直接写i < stack.size(),因为stack.size()是动态变化的                     //进入一次循环计数加1                     ++n;                     //当数到num时,将那个人淘汰                     if (n == num) {                         //将栈顶的人淘汰                         stack.pop(stack.peek());                         //将计数器重新置零                         n = 0;                     } else {                         //存活下来的人放入数组中存放                         arr.push(stack.pop(stack.peek()));                     }                 }                 //没有到最后两个人就继续循环将数组的人倒着压栈                 if (arr.length > winNum) {                     //将数组中存放的人倒着压栈,为下一轮做准备                     for (let i = arr.length - 1; i >= 0; i--) {                         stack.push(arr[i]);                         //当该编号的人进栈后,删除数组对应的编号的人,最后将数组置空,用于下一轮存放存活的人                         arr.pop();                     }                 }else{                     //仅剩最后两人游戏结束,输出胜出的人编号                     console.log(arr);                     return;                 }                 //递归调用直到得到最后两个人                 check(n);             }         }         josephRingStack(41, 3, 2); 

說着敷衍話

关于作者: 說着敷衍話

为您推荐