首页 > 代码库 > javascript 数据结构和算法读书笔记 > 第四章 栈
javascript 数据结构和算法读书笔记 > 第四章 栈
1. 对栈的操作
栈是一种特殊的列表，栈中的元素只能通过列表的一端进行访问，即栈顶。类似于累起一摞的盘子，只能最后被放在上面的，最先能被访问到。
就是我们所说的后入先出（LIFO）。
对栈主要有入栈push,出栈pop,获得栈顶元素peek, 三个方法。
2. 栈的实现
基本类结构如下：
function Stack(){ this.dataStore = []; this.top = 0; this.push = push; this.pop = pop; this.peek = peek;
this.length = length;
this.clear = clear;
}
关于进栈操作：
function push(obj){ this.dataStore[this.top++] = obj;}
出栈：
function pop(){
if(this.top!=0){ return this.dataStore[--this.top];
}else{
return undefined;
}}
获取栈顶元素：
function peek(){ return this.dataStore[this.top-1];}
获取长度:
function length(){ return this.top;}
清空：
function clear(){ this.top = 0;}
3 使用 Stack 类
a) 数制间的相互转换
可以利用栈来做10进制转2~9进制的操作
方法如下：一个十进制数a，进制b
1> 将a%b,压入栈内
2> 用a/b替换a
3> 如果a大于0，继续重复撞到1>进行操作
如果小于0，跳出
4> 将栈中元素一次弹出，组成一个新的字符（该字符就是转换完成的结果）
举个例子：
10 转为 2 进制：
10%2 = 0 ——入栈—— 0
5%2 = 1 ——入栈—— 1, 0
2%2 = 0 ——入栈—— 0, 1, 0
1%2 = 1 ——入栈—— 1, 0, 1, 0
最后出栈顺序就是1010
代码如下：
function mulNum(num, base){ var stack = new Stack(); // 操作三 while(num>0){ // 操作一 stack.push(num%base); // 操作二（注意要取整） num = Math.floor(num/base); } var rs = ‘‘; for(stack.length>0){ rs += stack.pop(); } return rs;}
b) 回文
function isPalindromic(str){ var stack = new Stack(); for(var i=0;i<str.length;i++){ stack.push(str[i]); } var revStr; while(stack.length()>0){ revStr += stack.pop(); } if(revStr === str){ return true; }else{ return false; }}
就是通过stack对其进行了翻转操作。
c) 递归演示
第一章中提到过递归求阶乘的方法，这里我们使用stack来求阶乘，模拟递归：
function(num){ var rs = 1; var stack = new Stack(); while(num>1){ stack.push(num--); } while(stack.length>0){ rs *= stack.pop(); } return rs;}
javascript 数据结构和算法读书笔记 > 第四章 栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。