学习《JavaScript 数据结构与算法》读书笔记

第2章栈

3.1 栈数据结构

后进先出（LIFO）

function Stack() {
	let items = [];
	this.push = function(element) {
		items.push(element);
	};
	this.pop = function() {
		return items.pop();
	};
	this.peek = function() {
		return items[items.length - 1];
	};
	this.isEmpty = function() {
		return items.length === 0;
	};
	this.size = function() {
		return items.length;
	};
	this.clear = function() {
		items = [];
	};
	this.print = function() {
		console.log(items.toString());
	};
}

3.2 ECMAScript 6 和 Stack 类

用 ES6 语法声明 Stack 类

class Stack {
	constructor() {
		this.items = [];
	}
	push(element) {
		this.items.push(element);
	}
	/* 其他方法 */
}

我们只是用 ES6 的简化语法把 Stack 函数转换为 Stack 类。这种方法不能像其他语言（Java、C++、C#）一样直接在类里面声明变量，只能在类的结构函数 constructor 里声明，在类的其他函数里用 this.nameofVariable 就可以引用这个变量

尽管代码看起来更简洁、更漂亮，变量 item 确实公共的。 ES6 的类是基于原型的。虽然基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性（变量）或方法。而且，在这种情况下，我们希望 Stack 类的用户只能访问暴露给类的方法。否则，就有可能从栈中间移除元素。

1. 用 ES6 的限定作用域 `Symbol` 实现类

ES6 新增了一种叫做 Symbol 的基本类型，它是不可变的，可以用作对象的属性。

let _items = Symbol();

class Stack {
	constructor() {
		this[_items] = [];
	}
	/* Stack 方法 */
}

这种方法创建了一个假的私有系统，因为 ES6 新增的 Object。getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性

let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); /* 1 */
console.log(objectSymbols); /* [Symbol()] */
console.log(objectSymbols[0]); /* Symbol() */
stack[objectSymbols[0]].push(1);
stack.print(); /* 5, 8, 1 */

2. 用 ES6 的 `WeakMap` 实现类

有一种数据类型可以确保属性是私有的，这就是 WeakMap ，可以存储键值对，其中键是对象，值可以是任意数据类型

const items = new WeakMap();

class Stack {
	constructor () {
		items.set(this, []);
	}
	push(element) {
		let s = items.get(this);
		s.push(element);
	}
	pop() {}
		let s = items.get(this);
		let r = s.pop();
		return r;
	}
	/* 其他方法 */

现在， items 在 Stack 类里是真正的私有属性，但现在 items 仍然是在 Stack 类以外声明的，因此谁都可以改动它。我们要用一个闭包（外层函数）把 Stack 类包起来，这样就只能在这个函数里访问 WeakMap

let Stack = (function() {
	const items = new WeakMap();
	class Stack {
		constructor() {
			items.set(this, []);
		}
		/* 其他方法 */
	}
	return Stack;
})()

3.3 用栈解决问题

从十进制到二进制

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;
}

进制转换算法

function(decNumber, base) {
	var remStack = new Stack(),
	rem,
	baseString = '',
	digits = '0123456789ABCDEF';

	while(decNumber > 0) {
		rem = Math.floor(decNumber % base);
		remStack.push(rem);
		decNumber = Math.floor(decNumber / base);
	}

	while(!remStack.isEmpty()) {
		baseString += digits[remStack.pop()];
	}

	return baseString;
}

第2章 栈