栈（stack）是一种常见的数据结构，它是遵循后进先出的有序集合，(LIFO)，生活中书桌上堆放的书本，餐桌上叠起来的盘子，都是典型的栈的形象。
使用JS来实现一个栈的数据结构，可以基于数组开始。
class Stack {
constructor() {
this.items = [];
}
}
栈的方法有
- push(elements) 添加一个或者多个元素到栈顶
- pop() 移除栈顶的元素
- peek() 返回栈顶的元素，并对栈不做修改
- isEmpty() 栈为空返回true，否则返回false;
- clear() 清空栈
- size() 返回栈的元素个数
使用javascript的数组可以实现上述方法
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.items.length
}
使用数组来创建栈十分方便，但是数组属于元素的有序集合，为了保证有序，占用的内存空间也更多。
我们可以使用对象来再次创建一个栈，实现上述的方法。
class Stack {
constructor() {
this.count = 0;
this.items = {};
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if(this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
peek() {
if (this.isEmpty) {
return undefined;
}
return this.items[this.count - 1];
}
clear() {
this.count = 0;
this.items = {};
}
}
为了保护类内部的数据，可以设置下划线命名，this._items,this._count;
或者使用symbol，或者weakMap，感兴趣的友友们，可以参考学习javascript数据结构和算法，这些文章的编写也是对我平时阅读这本书的一些总结，个人练习输出，这本书是写的很不错的，解释的很简洁明确。
用栈解决问题的一个实例是，进制转换。
比如十进制转换二进制。
function decimalToBinary(decNumber) {
const stack = new Stack();
let number = decNumber;
let rem; // 余数
let binaryNumber = '';
while(number > 0) {
rem = Math.floor(number % 2);
stack.push(rem);
number= Math.floor(number / 2);
}
while(!stack.isEmpty()) {
binaryNumber += stack.pop().toString();
}
return binaryNumber;
}
扩展到其他进制转换。
function baseConvert(decNumber, base) {
const stack = new Stack();
let number = decNumber;
let rem;
let baseString = '';
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
if (!(base >= 2 && base <= 36)) {
return '';
}
while(number > 0) {
rem = Math.floor(number % base);
stack.push(rem);
number = Math.floor(number / base);
}
while(!stack.isEmpty()) {
baseString += digits[stack.pop()];
}
return baseString;
}
