前言
栈是一种遵循后进先出(LIFO)原则的有序集合,新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另外一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。可以想象桌上的一叠书,或者厨房里的堆放的盘子。
一、栈的创建
可以创建一个类来表示栈
//1、创建一种数据结构来保存栈里面的数据,这里选择数组
//2、声明一些栈的方法
// push(element(s)) : 添加一个或一些元素到栈顶
// pop() : 移除栈顶的元素,同时返回被移除的元素。
// peek() : 返回栈顶的元素,仅仅是返回,不做任何修改。
// isEmpty() : 如果栈里面没有任何元素就返回true,否者为false。
// clear() : 清除栈里面的元素。
// size() : 返回栈里面的个数。
function Stack(){
var items = [];
this.push = function(element){
items.push(element);
}
this.pop = function(){
return items.pop();
}
this.peek = function(){
return items[items.length-1];
}
this.isEmpty = function(){
return items.length == 0;
}
this.clear = function(){
items = [];
}
this.size = function(){
return items.length;
}
this.print = function(){
console.log(items.toString());
}
}
//使用栈
var stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(100);
stack.push(200);
console.log(stack.isEmpty());//false
console.log(stack.size());//2
console.log(stack.peek());
stack.pop();
stack.print();//100
二、栈的应用
十进制转二进制
//算法描述:将该十进制的数和2整除,或者每次的余数(0或1),直到结果为0位置。比图10的二进制为:
// 10/2 = 5 ,余数 0
// 5/2 = 2 ,余数 1
// 2/2 = 1 ,余数 0
// 1/2 = 0 ,余数 1
// 10的二进制表示为:0101
function diviceBy2(decNumber){
var remStack = new Stack(),
rem,
binaryString = '';
while(decNumber > 0){
rem = Math.floor(decNumber%2);
remStack.push(rem);
decNumber = Math.floor(decNumber/2);
}
while(!remStack.isEmpty()){
binaryString += remStack.pop().toString();
}
return binaryString;
}
console.log(diviceBy2(10)); //1010
console.log(diviceBy2(520)); //1000001000
console.log(diviceBy2(1000)); //1111101000
十进制转成其他进制
function diviceByBase(decNumber, base){
var remStack = new Stack(),
rem,
baseString = '',
digits = '0123456789ABCDEF';//8进制是余数是(0-7)16进制是(0-9A-F)
while(decNumber > 0){
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(!remStack.isEmpty()){
baseString += digits[remStack.pop()];
}
return baseString;
}
console.log(diviceByBase(100345, 2)); // 11000011111111001
console.log(diviceByBase(100345, 8)); // 303771
console.log(diviceByBase(100345, 16)); // 187F9