JavaScript实现栈结构详细过程
这篇文章主要介绍了JavaScript实现栈结构详细过程,栈即stack它是一种受限的线性表,后进先出LIFO,更多具体的内容,需要的小伙伴参考下面文章的详细内容
目录
一、认识栈结构
二、栈结构封装
三、十进制转化为二进制
一、认识栈结构
我们知道数组是一种常见的数据结构,并且可以在数组的任意位置插入和删除数据,但是有时候,我们为了实现某些功能,必须对这种任意性加以限制,而栈和队列就是比较常见的受限的数据结构,我们先来看看栈。
栈(stack
),它是一种受限的线性表,后进先出(LIFO
)
其限制性是允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对的,把另一端,称为栈底。
LIFO
(last in first out)表示就是后进入的元素,第一个弹出栈空间。向一个栈中插入一个新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;
从一个栈删除元素又称作出栈或者退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
其结构图如下所示:
生活中类似于栈的
例如:当我们敲代码时,如果发生错误需要删除,那么最先敲上去的是最后被删除的。
接下来我们就一起来实现一下栈结构的封装,将采用的方式是基于数组实现的。
二、栈结构封装
首先创建一个类封装栈结构,如下:
1 2 3 | function Stack(){ } |
在其内部添加属性和方法,将数组通过属性的方法添加给该类。然后采用原型的方法添加常用的操作。
栈常用的操作有:
push
(element):添加一个新元素到栈顶位置。pop()
:移除栈顶的元素peek( )
:返回栈顶的元素,不对栈做任何修改isEmpty()
:判断栈是否空,如果栈里没有任何元素,则返回true
,否则返回false
size()
:返回栈里的元素个数toString()
:将栈结构的内容以字符形式返回
接下来,我们就来将他们一一实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | function Stack(){ this .items = []; // 添加一个新元素到栈顶位置。push() Stack.prototype.push = function (element){ this .items.push(element); } // 移除栈顶的元素pop() Stack.prototype.pop = function (){ return this .items.pop(); } // 返回栈顶的元素,不对栈做任何修改peek() Stack.prototype.peek = function (){ return this .items[ this .items.length-1]; } // 判断栈是否空isEmpty() Stack.prototype.isEmpty = function (){ if ( this .items.length == 0){ return true ; } else { return false ; } } // 返回栈里的元素个数size() Stack.prototype.size = function (){ return this .items.length; } // 将栈结构的内容以字符形式返回toString() Stack.prototype.toString = function (){ var str = '' ; for ( var i =0;i< this .items.length;i++){ str += this .items[i] + ' ' ; } return str; } } |
注意:这里为什么要通过原型的方式添加呢?是因为通过该方法添加的方法是添加在类上的,而如果直接通过this来添加,是添加到具体的实例对象上的,会造成浪费内存的情况。
最后进行验证。代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 | var stack = new Stack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); console.log(stack); console.log( '移除的栈顶元素是:' +stack.pop()); console.log( '栈顶元素为:' +stack.peek()); console.log( '栈是否为空:' +stack.isEmpty()); console.log( '栈里的元素个数是:' +stack.size()); console.log( '栈结构的内容是:' ); console.log(stack.toString()); |
输出结果为:
构建成功。
接下来来看一个实例!
三、十进制转化为二进制
如何实现十进制转化为二进制呢?
要把十进制转化成二进制,我们可以将该十进制数字和2整除,将得到的余数压入栈中,直到结果是0为止,最后在将得到的栈中元素依次出栈,得到最终结果,
如下图所示:
具体代码为:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | function Stack(){ this .items = []; //入栈 Stack.prototype.push = function (element){ this .items.push(element); } //出栈 Stack.prototype.pop = function (){ return this .items.pop(); } //判断栈是否为空 Stack.prototype.isEmpty = function (){ if ( this .items.length == 0){ return true ; } else { return false ; } } } function decToBin(decNumber){ var stack = new Stack; while (decNumber>0){ //获取余数,放入栈中 stack.push(decNumber%2); //获取新的除数 decNumber = Math.floor(decNumber/2); } //获取栈顶元素 var str = '' ; while (!stack.isEmpty()){ str += stack.pop(); } return str; } console.log( '100转化成二进制是:' +decToBin(100)); console.log( '50转化成二进制是:' +decToBin(50)); console.log( '20转化成二进制是:' +decToBin(20)); console.log( '34转化成二进制是:' +decToBin(34)); |
输出结果为:
到此这篇关于JavaScript
实现栈结构详细过程的文章就介绍到这了
原文链接:https://blog.csdn.net/m0_48375854/article/details/121631212