浅谈Js栈

lynhao

2017-03-01

JavaScript

栈和队列是我们常用数据结构,在数组中我们可以对任意位置进行操作,这就用到了栈.首先,栈是一种遵守LIFO原则的有序集合,即后进先出.

找了这么一张图比较容易看懂

stack

创建栈

function stack(){
  //初始化一个全局变量用于保存栈中的元素
  var temp = [];
}

这里会用到下面几个方法

push()
pop()
peak()
isEmpty()
clear()
size()
print()

peak是用于返回栈顶的元素,但不会移除
isEmpty是用于判断当前栈中是否有元素,没有的话返回true,否者false

分别实现上面的栈方法

function Stack(){
	var temp = [];
	
	this.push = function(element){
		temp.push(element);
	}
	this.pop = function(){
		return temp.pop();
	}
	this.peak = function(){
		return temp[temp.length-1];
	}
	this.isEmpty = function(){
		return temp.length == 0;
	}
	this.clear = function(){
		temp = [];
	}
	this.size = function(){
		return temp.length;
	}
	this.print = function(){
		console.log(temp.toString());
	}
}

Ok,下面通过栈的处理来实现进制之间的转换

function divideBy2(decNum){
	var remStack = new Stack(); //实例一个stack对象
	var rem;   //余数
	var binaryString = ''; //转换后的二进制
}
while(decNum>0){
	rem = Math.floor(decNum % 2);   //拿到余数
	remStack.push(rem);			//进栈
	decNum = Math.floor(decNum / 2);		
}
while(!remStack.isEmpty()){
	binaryString += remStack.pop().toString;  //将拿到的二进制进栈
}
return binaryString;

优化,让进制间自由转换

function baseConvertr(decNum, base){
	var remStack = new Stack(); //实例一个stack对象
	var rem;   //余数
	var baseString = ''; //转换后的base进制
	digits = '0123456789ABCDEF';
}
while(decNum>0){
	rem = Math.floor(decNum % 2);   //拿到余数
	remStack.push(rem);			//进栈
	decNum = Math.floor(decNum / 2);		
}
while(!remStack.isEmpty()){
	baseString += digits[remStack.pop()];  //将拿到的base进制进栈
}
return baseString;