第 3 章
1. 栈数据结构
栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
1.1 栈的操作
为栈声明一些方法：
- push(element(s))：添加一个（或几个）新元素到栈顶。
- pop() ：移除栈顶的元素，同时返回被移除的元素。
- peek() ：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
- isEmpty() ：如果栈里没有任何元素就返回 true ，否则返回 false 。
- clear() ：移除栈里的所有元素。
- size() ：返回栈里的元素个数。这个方法和数组的 length 属性很类似。
//创建一个类来表示栈
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());
};
}
var stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(1);
stack.push(2);
console.log(stack.peek());//2
stack.push(5);
console.log(stack.size());//3
console.log(stack.isEmpty());//false
stack.push(8);
stack.pop();
stack.pop();
console.log(stack.size());//2
stack.print();//1,2
2. ECMAScript 6 和 Stack 类
2.1 用 ES6 语法声明 Stack 类
class Stack{
constructor(){
this.items = [];
}
push(element){
this.items.push(element);
}
}
创建私有属性：
- 用ES6的限定作用域 Symbol 实现类
ES6新增了一种叫作 Symbol 的基本类型，它是不可变的，可以用作对象的属性。
let _items = Symbol();
class Stack{
constructor(){
this[_items] = [];
}
//Stack方法
}
这种方法创建了一个假的私有属性，因为ES6新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性。
let stack = new Stack();
stack.push(1);
stack.push(2);
let objSymbols = Object.getOwnPropertySymbols(stack);
console.log(objSymbols.length);//1
console.log(objSymbols);//[Symbol()]
console.log(objSymbols[0]);//Symbol()
stack[objSymbols[0]].push(5);
stack.print();//1,2,5
- 用ES6的 WeakMap 实现类
let Stack = (function(){
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;
}
//其他方法
}
return Stack;
})();
从十进制到二进制
function divideBy2(decNum){
var remStack = new Stack(),
rem,
binaryStr = '';
while(decNum>0){
rem = Math.floor(decNum%2);
remStack.push(rem);
decNum = Math.floor((decNum/2);
}
while(!remStack.isEmpty()){
binaryStr += remStack.pop().toString();
}
return binaryStr;
}
进制转换算法
function divideBy2(decNum,base){
var remStack = new Stack(),
rem,
binaryStr = '',
digits = '0123456789ABCDE';
while(decNum > 0){
rem = Math.floor(decNum % base);
remStack.push(rem);
decNum = Math.floor((decNum / base);
}
while(!remStack.isEmpty()){
binaryStr += digits[remStack.pop()];
}
return binaryStr;
}
