什么是栈？
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
显示生活中也能发现很多栈的例子，如书本的堆放和取出，叠盘子等。栈也被用在编程语言的编译器和内存中保存变量、方法调用等。JavaScript的基本类型变量就保存在栈中。在计算机中，栈运用的经典例子就是保存历史记录，例如Ctrl+Z这种撤回操作的实现。
JavaScript实现栈
栈是一种先进后出的数据结构，我们最容易想到的就是JS中数组的push、pop操作。用数组保存栈结构，这是一种最简便的实现形式。另外一种就是使用对象和指针保存栈结构的形式。两者的区别是，用数组存储栈元素，在处理大量数据的时候，需要迭代整个数组，大部分方法的时间复杂度是O(n)，而采用对象的形式能直接通过属性获取元素。
接来下我们分别实现两种方法，主要实现栈的以下几个主要功能：
- push（element）: 添加元素到栈顶。
- pop（）：移除栈顶元素，同时返回被修改的元素。
- peek（）：返回栈顶元素，不对栈做任何修改。
- isEmpty（）：检查栈是否为空，返回一个Boolean值。
- clear（）：清空栈元素。
- size（）：返回栈里元素的个数。
数组存储实现
class StackByArray {
constructor() {
this.items = [];
}
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 StackByObject {
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;
}
peek() {
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
clear() {
this.count = 0;
this.items = {};
}
size() {
return this.count;
}
// 需要手动实现toString打印
toString(){
if(this.isEmpty()){
return '';
}
let s = `${this.items[0]}`;
for(let i = 1;i< this.count;i++){
s += `,${this.items[i]}`;
}
return s;
}
}
