javascript数据结构 -- 栈
学习数据结构非常重要。首要原因是数据结构和算法可以很高效的解决常见问题。作为前端,通过javascript学习数据结构和算法要比学习java和c版本容易的多。
在讲数据结构之前我们先了解一下ES6的一些方法。因为这可能对我们了解数据结构有帮助。
ES6操作数组的方法
首先我们来用箭头函数定义一个函数。
const isEven = x => x % 2 === 0; let numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
1.event方法迭代
此方法会迭代数组中每个元素,如果每个元素都返回true,此方法才会返回true.
numbers.every(isEven);
因为并不是每个数字都是偶数。所以返回false;
2.some方法迭代
此方法会迭代数组中每个元素,如果有元素都返回true,此方法才会返回true.
numbers.some(isEven);
因为有偶数元素,所以返回true;
3.forEach方法迭代
此方法会迭代数组中的每个元素,然后分别执行传入的回到函数。
number.forEach(callback);
4.map方法迭代
此方法会将数组的每个元素通过回调函数,并将每个返回值组成新的数组返回。
numbers.map(isEven);
返回[false,true,false,true,false,true,false,true,false,true,false,true,false,true,false];
5.filter方法迭代
此方法返回的新数组由使回调函数返回true的元素组成。
numbers.filter(isEven);
因为2,4,6,8,10,12,14模2等于0;所以返回[2,4,6,8,10,12,14];
6.reduce方法迭代
此方法有四个参数previousValue,currentValue,index,array.后连个参数为可选参数,可以不传。这个函数会返回一个将被叠加到叠加器的值。
numbers.reduce((previous, current) => previous + current)
我们来分解一下reduce执行过程。第一个previous为1,current为2 return为1+2=3。在第二次迭代中previous为上一个迭代的返回值3,current为3, return为6 …因此最后返回120。
除此之外,ES6还新增了很多语法糖。有兴趣的同学可以去阮大神的个人博客。
栈
1.什么是栈?
基础的东西简单的介绍完了,接下来我们来点干货。那么什么是栈呢?栈是一种遵从后进先出(LIFO)原则的有序集合。新添加和待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。就像生活中厨房里叠放的盘子。
2.创建基于JavaScript数组的栈
先从声明一个Stack类开始。
class Stack { constructor() { this.items = []; } }
接下来我们添加一些方法。
- 1.push(element);添加元素到栈顶
- 2.pop();移除栈顶元素,并返回移除元素
- 3.peek();返回栈顶的元素
- 4.isEmpty();如果站里没有元素则按返回true,反之返回false
- 5.clear();移除栈里所有元素
- 6.size();返回栈里元素个数
push方法
push(element) { this.items.push(element); }
pop方法
pop() { return this.items.pop(); }
peek方法
peek() { return this.items[this.items.length - 1]; }
isEmpty方法
isEmpty() { return this.items.length === 0; }
clear方法
clear() { this.items = []; }
size方法
size() { return this.items.length; }
3.创建基于JavaScript对象的栈
先从声明一个Stack类开始。
class Stack { constructor() { this.count = 0; this.items = {}; } }
接下来我们添加一些方法。
- 1.push(element);添加元素到栈顶
- 2.pop();移除栈顶元素,并返回移除元素
- 3.peek();返回栈顶的元素
- 4.isEmpty();如果站里没有元素则按返回true,反之返回false
- 5.clear();移除栈里所有元素
- 6.size();返回栈里元素个数
push方法
push(element) { this.items[this.count] = element; this.count ++; }
pop方法
pop() { if(this.isEmpty()) { return undefined; } this.count --; let result = this.items[this.count]; delete this.items[this.count] return result; }
peek方法
peek() { if(this.isEmpty()) { return undefined; } return this.items[this.count - 1]; }
isEmpty方法
isEmpty() { return this.count == 0; }
clear方法
clear() { this.count = 0; this.items = {}; }
size方法
size() { return this.items.count; }
toString方法
因为数组版本的栈的toString()方法可以直接使用数组提供的toString方法,为对象版则需要我们自己封装。
toString() { if(this.isEmpty()) { return '' } let objString = `${this.items[0]}`; for(let i=1; i<this.count; i++) { objString = `${objString},${this.items[i]}` } return objString; }
这就是我们用javascript版本的栈数据结构。
4.用栈解决问题
下面我们以10进制转2进制为例,看看如何用栈决绝问题。
function decimalToBinary(decNumber) { const remStack = new Stack(); let number = decNumber; let rem; let binaryString = ''; while(number > 0) { rem = Math.floor(number % 2); remStack.push(rem); number = Math.floor(number / 2); } if(!remStack.isEmpty()) { binaryString += this.pop().toString(); } return binaryString; }
这便是用数据结构解决问题。后续我会将用JavaScript讲解什么是队列、链表、集合、字典、哈希表(HashTable)、递归、树、二叉堆、图等数据结构。
原创博客:转载请注明:javascript数据结构 – 栈