《javascript数据结构和算法》读书笔记
《javascript数据结构和算法》读书笔记
第一讲 栈
简介
汉诺塔问题： 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
栈是和数组非常相似的一类数据结构。在数组的基础上，定义了更为丰富的规则。
它是遵循先进后出(后进先出，LIFO)原则的有序集合。栈的最新数据，称为栈顶，反之，最旧的元素就是栈底。
汉诺塔，一叠书，一桶羽毛球。都是栈。
以下反映的是出栈和入栈的流程。（图引自网络）
用js创建一个栈
javascript是没有栈这种数据类型的，唯一相似的就是数组。因此需要自己创建一个。我们需要实现以下功能：
- push：添加一个或几个元素到栈顶
- pop：移除栈顶的元素，并返回之。
- peek：返回栈顶元素，但不做任何修改
- isEmpty：判断栈是否为空栈
- clear：清理栈的所有元素
- size：返回栈元素的个数
- print：打印栈内元素
功能都十分简单，马上写出来吧：
class Stack {
constructor(array=[]){
this.array=array;
}
// 入栈
push(item){
this.array.push(item);
}
// 出栈并返回（出栈）
pop(){
return this.array.pop()
}
// 查看栈顶
peek(){
return this.array[this.array.length-1]
}
// 是否为空
isEmpty(){
return this.array.length==0
}
// 清除栈
clear(){
this.array=[];
}
// 返回栈元素个数
size(){
return this.array.length;
}
// 打印
print(){
console.log(this.array)
}
}
// 测试用例
let stack=new Stack();
console.log(stack.isEmpty())//true
stack.push('1')
stack.push('2')
stack.pop()
console.log(stack.size())//1
console.log(stack.isEmpty())//false
stack.print()//['1']
stack.clear()
stack.print()//[]在这个类的设计中，只希望暴露这个类的方法，而不希望直接暴露类。目前来说，栈的基本操作都实现了。
栈的应用
相对于数组，栈的方法更加受限，同时也给人以一种新的解决问题方式。那这种数据结构用来做什么呢？
实例1 十进制和二进制的换算
要把十进制转化为二进制。可把十进制数不断和2整除。把余数返回到栈中。然后再把依次余数移除的过程。
实现方式是两个while循环
const divideBy2=(decNum)=>{
let stack=new Stack();
let _decnum=decNum;
while (_decnum!==0) {
stack.push(_decnum%2);
_decnum=parseInt(_decnum/2)
}
let result=''
while(!stack.isEmpty()){
result+=stack.pop().toString()
}
return Number(result)
}
console.log(divideBy2(32))上述代码很容易转化为其它进制。
那么二进制转十进制呢？更加简单。从最低位（最右）算起，位上的数字乘以本位的权重，权重就是2的第几位的位数减一次方。
const divideBy10=(decNum)=>{
let result=0;
for(let i=0;i<decNum.length;i++){
result+=decNum[i]*(Math.pow(2,decNum.length-i-1))
}
return result
}
console.log(divideBy10('1010'))实例2 语法检查
很多语数据格式比如html，xml都会有闭合标签。表示一个标签的结束。比如说：
<p>这是一段话。</p>
<p>这是错误示例<p></p>
</p>错了<p>
<p>这也是<p>错误</p>的</p>
<p>这同样是非法的<p></p></p>如果标签不能被闭合表示这个标签不能被正确解析。
为了简单期间，现在把p标签抽象为一对括号 (和 )。试写出检查合法性的算法。
思路：通过for循环遍历这段字符串。遇到左括号，就把左括号放入栈中、直到遇到右括号，执行出栈操作。最后判断栈是否为空！
const isLegal=(str)=>{
let stack=new Stack();
for(let i=0;i<str.length;i++){
if(str[i]='('){
stack.push(str[i])
}else if(str[i]==')'){
if(stack.isEmpty()){
return false;
}else{
stack.pop()
}
}
}
return stack.isEmpty()
}进阶
stack方法已经比较成熟了。但是还是扩展一下。
实例3 定义一个新栈，扩展min方法
试在Stack上扩展新的 min方法：无论栈里怎面变，总是返回一个栈结构的最小元素。并使时间复杂度为O(0)
思路：一个栈解决不了的问题，那就两个。第一个用于储存栈结构的数据，一个用于储存最小元素。无论栈怎么变，那么两个栈必须同时改变。
class MinStack{
constructor(){
this.array=[];
this.stack=new Stack();//存放栈的数据结构
this.min_stack=new Stack();//存放最小元素的栈
}
push(item){
//无论stack怎么入栈，min_stack总是存放最小的元素
this.stack.push(item)
if(this.min_stack.isEmpty()||item<this.min_stack.peek()){
this.min_stack.push(item)
}
}
pop(){
//无论stack怎么出栈，min_stack总是存放最小的元素
if(this.stack.peek()<=this.min_stack.peek()){
this.min_stack.pop();
}
this.stack.pop();
}
min(){
return this.min_stack.peek()
}
print(){
return this.stack.print()
}
}
//测试用例
let min_stack=new MinStack();
min_stack.push(4)
min_stack.push(2)
console.log(`stack:${min_stack.print()}`,`min: ${min_stack.min()}`)
min_stack.push(1)
console.log(`stack:${min_stack.print()}`,`min: ${min_stack.min()}`)
min_stack.push(3)
console.log(`stack:${min_stack.print()}`,`min: ${min_stack.min()}`)
min_stack.pop()
min_stack.pop()
min_stack.pop()
console.log(`stack:${min_stack.print()}`,`min: ${min_stack.min()}`)期望的结果如下：
功能顺利实现
实例4 计算后缀表达式
后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）.
计算式 3+5*6
中缀表达式 [3,'+',5,'*',6]
后缀表达式 [3,5,6,'*','+']
如何从中缀表达式转化为后缀表达式呢？
思考：你会发现，后缀表达式所有的运算符前面必然会有两个元素或表达式。他是一个严格从左到右计算，继承上次结果计算的表达式。
const change=(arr)=>{
let stack=new Stack();
for(let i=0;i<arr.length;i++){
if(['+','-','*','/'].indexOf(arr[i])==-1){
stack.push(arr[i])
}else{
let a=stack.pop();
let b=stack.pop();
let c=eval(`${a}${arr[i]}${b}`);
stack.push(c)
}
}
return stack.pop()
}
console.log(change([3,5,6,'*','+']))//33实例5 中缀表达式转后缀表达式
例如：
原型：1+2：输入 [1,'+',2]，结果为 [1,2,'+']。
原型：1+(4+5)/3+(6+8)/2输入 [1,'+','(',4,'+',5,')','/',3,'+','(','6','+','8',')','/',2]，结果为 [1,4,5,'+',3,'/',6,8,'+',2,'/','+']。
这题比较难。因为要考虑运算优先级。括号优先级最大，*/次之，最小是+-。
let _arr=[1,'+','(',4,'+',5,')','/',3,'+','(',6,'+',8,')','/',2]
let __arr=[1,4,5,'+',3,'/',6,8,'+',2,'/','+']
const change2=(arr)=>{
let _dict=['+','-','*','/']
let dict={
'+':1,
'-':1,
'*':2,
'/':2,
};
let stack=new Stack();
let result=[];
for(let i=0;i<arr.length;i++){
if(!isNaN(arr[i])){
// 是数字，放入返回值
result.push(arr[i])
}else if(arr[i]=='('){
//括号开始，直接压栈
stack.push(arr[i])
}
else if(arr[i]==')'){
//括号结束后，表示扫描结束.无需压栈，括号内运算符优先出栈
while (stack.peek()!=='(') {
result.push(stack.pop());
// console.log(stack.pop())
}
stack.pop()
}else if(_dict.indexOf(arr[i])>=0){
console.log(arr[i])
// 是四则运算符,判断：
// 如果优先级大于栈顶，压栈。否则：
// 弹出运算符到返回值，直至优先级
while (!stack.isEmpty()
&&_dict.indexOf(stack.peek()>=0)
&&dict[stack.peek()]>=dict[arr[i]]
){
result.push(stack.pop()) ;
}
stack.push(arr[i]) ;
}
}
while (!stack.isEmpty()) {
result.push(stack.pop())
}
return result
}