基本定义:
只允许在有序的线性资料集合的一端(称为堆栈顶端,top)进行加入数据(push)和移除数据(pop)的运算。它有两种基本操作:推入或者弹出,遵循着先入后出,后入先出的特点。
在javascript中实现栈结构
在javascript中实现栈结构,最常见的就是借助数组来实现,数组中提供了push和pop方法,可以很轻松的实现栈结构的特点。
栈结构的常用操作
- push:添加一个新元素到栈顶
- pop:移除栈顶的元素,同时返回被移除的元素
- peek:返回栈顶的元素,不对栈做任何修改,单纯的看一眼栈顶是谁
- isEmpty:如果栈里没有元素就返回true,反之返回false
- size:返回栈里元素的个数
- toString:将栈结构的内容以字符串的形式返回
利用数组实现栈结构
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop(item) {
return this.items.pop(item);
}
peek() {
return this.items[0];
}
isEmpty() {
return this.items.length > 0 ? false : true;
}
size() {
return this.items.length;
}
toString() {
let str = "";
this.items.forEach(item => {
str = str + item + " ";
});
return str;
}
}
const stack = new Stack();
实现十进制转换成二进制
在实现之前要了解一点理论知识,十进制转换成二进制是怎么转换的?如果过程都不知道,自然不可能将其转换为代码了。
十进制是我们日常生活中最常见的,二进制则是我们计算机底层的实现,类似于电路的开和关,也就对应着0和1,比如说100我们该如何转换成二进制呢?首先我们将100除于2然后去余数,然后得到50和余数0,然后继续拿50除于2,得到25和余数0,继续拿25除于2,得到12.5和余数1,12.5我们直接向下取整,得到12,然后继续拿12除于2,得到6和余数0,以此类推,最后我们反向将得到的余数拼在一起,最后得到110 0100。
既然知道了十进制转换成二进制的过程,接下来我们用代码对其进行复现
function dec2bin(number) {
const stack = new Stack();
// 只要number> 0就继续求余数
while (number > 0) {
stack.push(number % 2);
number = Math.floor(number / 2);
}
//从栈中挨个取出元素,然后拼接在一起
let bin = "";
while (!stack.isEmpty()) {
bin += stack.pop();
}
return bin;
}