众所周知,栈结构是一种特殊的数据结构,它遵从先进后出,后进先出的原则,即(LIFO:last in first out);生活中其实都存在栈结构的影子,例如仓库中对货物的存放和搬取;子弹的上膛和发射.....等等。那么栈结构是如何实现的呢,下面让我们来深入了解一下前端的栈结构。
上图为栈结构的入栈和出栈示意图,可以看出第一个入栈的data_01第一个压入栈中,出栈的时候却是最后一个出栈。由此,那我们是不是就可以很轻松的把栈结构的代码实现了呢?
写代码之前,先问大家一个问题---为什么要把构造函数的方法放到原型对象上,直接在函数内部声明不行吗?
我们知道,函数上自带【prototype】属性,prototype上的【方法、属性】可被构造函数实例共享;对象上自带【__proto__】属性,指向其构造函数prototype,但在对象上找【属性、方法】找不到时,会通过__proto__继续,一级级往上找,直到找到或__proto__指向是null为止
1.每次通过new 关键字创建一个实例对象时,会return一个全新的【相互独立】对象,即其构造函数上定义属性和方法,在每个实例对象深拷贝一份,放在不同内存空间;
2.实际上很多时候,我们只需要实例对象属性是独立,方法是共享;
3.如果相同方法在每个实例对象上都重新定义一次,太浪费内存。所以把共享部分提出来,只定义一次,放在共享空间,而每个实例对象只需要一个指针指向共享空间。这个指针就是每个对象上的__proto__,共享空间就是对象的构造函数上的prototype上的属性方法占用的内存空间
明白了吗?明白之后咱就开始具体实现一下 ,实现思想就是基于数组的实现,通过调用数组的方法来实现栈结构的相关功能,以下是综合代码:
//这里我们用数组实现
//声明一个栈函数
function Stack() {
//用数组来存储元素
this.items = []
//入栈
Stack.prototype.push = function (val) {
return this.items.unshift(val)
}
//出栈
Stack.prototype.pop = function () {
return this.items.shift()
}
//获取栈底元素
Stack.prototype.peek = function () {
return this.items[this.items.length - 1]
}
//检测栈内是否还有元素
Stack.prototype.isEmpty = function () {
return this.items.length === 0
}
//栈中的元素个数
Stack.prototype.size = function () {
return this.items.length
}
//遍历栈中的元素
Stack.prototype.toString = function () {
return this.items.join('')
}
}
使用栈结构:
//创建实例对象
var stack = new Stack()
stack.push(6)
stack.push(5)
stack.push(4)
stack.push(3)
stack.push(2)
stack.push(1)
console.log(stack.toString());//123456
console.log(stack.pop());//1
console.log(stack.pop());//2
console.log(stack.pop());//3
console.log(stack.peek());//6
console.log(stack.pop());//4
console.log(stack.pop());//5
console.log(stack.size());//1
栈的应用:十进制转二进制(面试题)
//声明用来转二进制的函数
function toBin(des) {
//创建栈的实例
var stack = new Stack()
while (des > 0) {
//将余数压入栈中
stack.push(des % 2)
//计算出每次与2相除的结果
des = Math.floor(des / 2)
}
//遍历栈中存在的元素
return stack.toString()
}
//调用函数打印结果
console.log(toBin(100))//1100100
console.log(toBin(1000))//1111101000
通过以上的练习,相信你已经对栈结构有了一定的了解了吧,俗话说:“熟能生巧”,不要说你学不会,只是练的问题;在闲暇时间应该多练习相应的题才能有助于自我提升,加油!!!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)