### 数组 数组是最简单的内存数据结构，由于其简单性和灵活性，很多编程语言都内置数组，JS当然也支持。关于数组的介绍可参考以下文章 [数组基础学习](https://blog.86886.wang/posts/5aed8d6c2e528d4914d62144) [数组方法学习](https://blog.86886.wang/posts/5af048272e528d4914d62146) ### 栈 栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的 同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。 在现实生活中也能发现很多栈的例子，比如一摞书，最新的书在最上面，取书的时候也是先取最上面。栈也被用在编程语言的编译器和内存中保存变量、方法调用等。JS是一门解释性语言，编译过程是由浏览器完成的，JS中的原始值都是在栈中存储的 利用数组的push和pop方法，可以很方面的模拟栈数据结构 首先为栈声明一些方法 ``` push(element(s)) ：添加一个（或几个）新元素到栈顶。 pop() ：移除栈顶的元素，同时返回被移除的元素。 peek() ：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返 回它）。 isEmpty() ：如果栈里没有任何元素就返回 true ，否则返回 false 。 clear() ：移除栈里的所有元素。 size() ：返回栈里的元素个数。这个方法和数组的 length 属性很类似。 ``` 实现声明的方法 ```js class Stack { constructor () { this.items = []; //{1} } push(element) { this.items.push(element); } pop() { return this.items.pop(); } peek() { return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } clear() { this.items = []; } size() { return this.length; } } // 使用 let s = new Stack(); s.push('a'); ``` 这种方式实现的栈结构有个缺点，由于items是公有属性，导致外部能随意操作items中的值。这样实现的栈本质上和数组没什么区别，所以要想办法把items变成私有属性，一个比较简单的方法是使用ES6的WeakMap ```js let Stack = (function(){ const items = new WeakMap(); class Stack { constructor() { items.set(this, []); } //其他方法 } return Stack; })() ``` 除此之外，也可以通过特权方法达到属性私有化的目的 ```js function Stack() { let items = []; // 私有属性 this.push = function(element) { // 特权方法 items.push(element) } // 其他方法 } let s = new Stack(); s.push('a'); ``` #### 应用 使用栈结构实现十进制转二进制 ```js function divideBy2(decNumber){ var remStack = new Stack, rem, binaryString = ''; while (decNumber > 0){ rem = Math.floor(decNumber % 2); remStack.push(rem); decNumber = Math.floor(decNumber / 2); } while (!remStack.isEmpty()){ binaryString += remStack.pop().toString(); } return binaryString; } divideBy2(10); // '1010' ``` ### 队列 队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。 队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。 在现实中，最常见的队列的例子就是排队，比如在电影院、自助餐厅、杂货店收银台，排在第一位的人会先接受服务，服务完成后先离开 使用数组的push和shift方法可以模拟这种数据结构 队列要实现的方法 ``` enqueue(element(s)) ：向队列尾部添加一个（或多个）新的项。 dequeue() ：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。 front() ：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。 isEmpty() ：如果队列中不包含任何元素，返回 true ，否则返回 false 。 size() ：返回队列包含的元素个数，与数组的 length 属性类似。 ``` 使用ES6实现队列 ```js let Queue = (function(){ let items = new WeakMap(); class Queue { constructor() { items.set(this, []); } enqueue() { this.items.push(element); } dequeue() { return this.items.shift(); } front() { return this.items[0]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } } return Queue; })() ``` 使用ES5实现队列 ```js function Queue() { let items = []; this.enqueue = function(element){ items.push(element); }; // 其他方法 } ```