JavaScript数据结构与算法—— 栈

我们可以在数组的任何位置上删除或者添加元素，但有时候我们还需要在元素的添加或删除时有更多控制的数据结构，有两种数据结构类似于数组，但在添加或删除元素时更为可控，它们就是栈和队列。本节主要介绍栈。1.栈数据结构栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，叫做栈顶，另一端叫栈底。在栈中，新元素靠近栈顶，旧元素接近栈底。如下图所示：2.创建栈// 首先创建一类表示栈function Stack(){ let items = []; // 选择数组来保存栈中的元素 //各种属性和方法}下面要为栈声明一些方法：push() // 添加一个或多个新元素到栈顶pop() // 移除栈顶元素，同时返回被移除的元素peek() // 仅仅返回栈顶元素，不对栈做任何修改isEmpty() // 如果栈中没有元素返回true，否则返回falseclear() // 移除栈中所有元素size() // 返回栈中元素的个数（和数组length类似） 2.1 向栈添加元素this.push() = function(element) { items.push(element);}2.2 从栈移除元素this.pop = function() { items.pop();}2.3 查看栈顶元素this.peek = function() { return items[items.length - 1];}2.4 查看栈是否为空this.isEmpty = function(){ return items.length === 0;}this.size = function() { return items.lenght;}2.5 清空和打印栈元素this.clear = function() { items = [];} this.print = function() { console.log(items.toString());}经过上述的方法的添加，我们就完整的创建了一了个栈 Stack。3.栈的应用—十进制转N进制首先我们写出将十进制转为二进制：function divideBy2(decNum) { var remStack = new Stack(), rem, binaryString = ‘’; // 将十进制数除2的余数放入一个stack中 while(decNum > 0) { // 取余 rem = Math.floor(decNum % 2); // 入栈 remStack.push(rem); decNum = Math.floor(decNum / 2); } // 从栈中取出转化为字符串然后连接起来构成二进制 while(!remStack.isEmpty()) { // 出栈 binaryString += remStack.pop().toString(); } return binaryString;}下面十进制转化N进制算法function divideByN(decNum, n) { var remStack = new Stack(), rem, binaryString = ‘’, digits = ‘0123456789ABCDEF’; // 将十进制数除N的余数放入一个stack中 while(decNum > 0) { // 取余 rem = Math.floor(decNum % n); // 入栈 remStack.push(rem); decNum = Math.floor(decNum / n); } // 从栈中取出转化为字符串然后连接起来构成二进制 while(!remStack.isEmpty()) { // 出栈 使用digits方便在16进制中做个对应转化 binaryString += digits[remStack.pop()]; } return binaryString;}