栈
栈是一种遵守后进先出原则的一种有序集合；新添加或待删除的元素都保存在栈的末尾，叫栈顶，另一端叫栈底；在栈里，新元素都靠近栈顶，旧元素都靠近栈底；栈也被用在编程语言的编译器和内存中保存变量、方法调用等；
栈的创建
function Stack(){
}
// 我们创建一个类来表示栈。我们用数组来模拟；
var list=[];
1
2
3
4
5
2
3
4
5
接下来需要一点给栈声明一些方法
- push()： 添加一个或多个新元素到栈顶；
- pop()：移除栈顶的元素，同时返回该移除的元素；
- peek()：返回栈顶的元素；
- isEmpty()：判断栈里面是否存在元素，存在则返回true，不存在就返回false；
- clear(): 移除栈里的所有元素；
- size(): 返回栈里元素的个数；
我们根据功能给类里面添加方法；
function Stack(){
var list=[];
//添加push方法；添加元素
this.push=function(element){
list.push(element);
};
//添加pop方法，移除元素；
this.pop=function(element){
list.pop(element);
};
//添加peek方法，返回栈顶元素；
this.peek=function(element){
return list[list.length-1]
};
//isEmpty方法，判断是否有元素；
this.isEmpty=function(){
if(!list.length){
return false;
}
return true;
};
//clear:清除栈元素
this.clear=function(){
list=[];
}
//size:返回栈的元素个数
this.size=function(){
return list.length;
}
}
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
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
从十进制到二进制
上面我们模拟了栈，现在我们就用它来解决从十进制到二进制的转换；
ps: 把十进制转成二进制，是将十进制的数字和2整除，如果余数不为零就继续用余数和2进行整除，直到结果为0为止；
10/2=5 rem===0;
5/2=2 rem===1;
2/2=1 rem===0;
1/2=0 rem===1;
将结果从下往上放入栈中，然后输出；
1
2
3
4
5
6
2
3
4
5
6
那么，我们如何模拟实现这个方法呢？
function divideBy2(decNumber){
let remStack = new Stack();
let rem,str='';
while(decNumber>0){
rem = Math.floor(decNumber%2);//取余数；
remStack.push(rem);//将余数放入栈中；
decNumber=Math.floor(decNumber/2);//此时数字应该变成未除尽的数；
}
while(!remStack.isEmpty()){
str += remStack.pop().toString();
}
return str;
}
console.log(divideBy2(10))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
我们很容易修改上面的算法，使函数变成能把十进制转成任意进制的；
function divideBy2(decNumber,base){
let remStack = new Stack();
let rem,str='',digits='0123456789ABCDEF';
while(decNumber>0){
rem = Math.floor(decNumber%base);//取余数；
remStack.push(rem);//将余数放入栈中；
decNumber=Math.floor(decNumber/base);//此时数字应该变成未除尽的数；
}
while(!remStack.isEmpty()){
str += digits[remStack.pop()];
}
return str;
}
console.log(divideBy2(100345,16))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15