数据结构与算法 – 栈

栈是一种特殊的列表, 栈内的元素只能通过列表的一端访问, 这一端称为栈顶。 咖啡厅内的一摞盘子是现实世界常见的栈的例子。 只能从最上面取盘子, 盘子洗净后, 也只能摞在这一摞盘子的最上面。 栈被称为一种后入先出(LIFO, last-in-first-out) 的数据结构。

由于栈具有后入先出的特点, 所以任何不在栈顶的元素都无法访问。 为了得到栈底的元素, 必须先拿掉上面的元素。

栈的实现类:

function Stack(){
	this.dataStore = [];
	this.top = 0;
	this.push = push;
	this.pop = pop;
	this.peek = peek;
	this.clear = clear;
	this.length = length;
}
function push(ele){
	this.dataStore[this.top++] = ele;
}
function pop(){
	return this.dataStore[--this.top];
}
function peek(){
	return this.dataStore[this.top-1];
}
function clear(){
	this.top = 0;
}
function length(){
	return this.top;
}

使用栈来解决问题:

1、数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。 假设想将数字 n 转换为以 b 为基数
的数字, 实现转换的算法如下。

(1) 最高位为 n % b, 将此位压入栈。
(2) 使用 n/b 代替 n。
(3) 重复步骤 1 和 2, 直到 n 等于 0, 且没有余数。
(4) 持续将栈内元素弹出, 直到栈为空, 依次将这些元素排列, 就得到转换后数字的字符
串形式。

注:此算法只针对基数为 2~9 的情况。

function mulBase(num,base){
	var s = new Stack();
	do{
		s.push(num % base);
		num = Math.floor(num / base);
	}while(num>0)
	var converted = '';
	while(s.length()>0){
		converted += s.pop();
	}
	return converted;
}
alert(mulBase(11,2)); //1101

2、判断一个字符串是否回文

回文是指这样一种现象: 一个单词、 短语或数字, 从前往后写和从后往前写都是一样的。比如, 单词“ dad”、“ racecar” 就是回文; 如果忽略空格和标点符号, 下面这个句子也是回文,“ A man, a plan, a canal: Panama” ; 数字 1001 也是回文。

使用栈,我们可以很轻松判断一个字符串是否是回文。

function isPalindrome(word){
	var s = new Stack();
	for(var i=0;i<word.length;i++){ s.push(word[i]); } var sword = ''; while(s.length()>0){
		sword += s.pop();
	}
	if(word===sword){
		return true;
	}
	return false;
}
alert(isPalindrome("1001")); //true
alert(isPalindrome("1000")); //false
  • 支付宝二维码 支付宝
  • 微信二维码 微信
相关文章