数据结构-栈

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保持在栈的同一端， 称为栈顶，另一端就叫栈底。 在栈里， 新元素都靠近栈顶， 旧元素都接近栈底。

在现实生活中的例子就是下图里的一摞书或者餐厅里叠放的盘子。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等， 也用于浏览器历史记录（浏览器的返回按钮）。

创建一个基于JavaScript对象是stack类

创建一个Stack类的最简单的方式是使用数组来存储其元素。在处理大量数据的时候（这在现实生活中的项目里很常见），我们同样需要评估如何操作数据是最高效的。在使用数组时，大部分方法的时间复杂度是O（n）。我们需要迭代整个数组直到找到要找的那个元素， 在最坏的情况下需要迭代数组的所有位置。 其中的n代表数组的长度。 如果数组有更多元素的话， 所需要的时间会更长。 另外，数组是一个有序集合， 为了保证元素排列有序， 它会占用更多的内存空间。 所以，我们可以使用一个JavaScript对象来存储所有的栈元素， 保证它们的顺序并且遵守LIFO原则。

首先声明一个Stack类

class Stack {
    constructor() {
        this.count = 0;
        this.items = {};
    }
}
复制代码

1. 向栈中插入元素

push(item) {
    this.items[this.count] = item;
    this.count++;
}
复制代码

2. 验证一个栈是否为空和它的大小

count属性也表示栈的大小。因此，我们可以简单的返回count的属性的值来实现size方法。

size() {
    return this.count;
}
复制代码

3. 验证栈是否为空，可以简单的判断count是否为0

isEmpty() {
    return this.count === 0;
}
复制代码

4. 从栈中弹出元素

pop() {
    if(this.isEmpty()) {
        return undefined;
    }
    
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
}
复制代码

5. 查看栈顶的值

peek() {
    if(this.isEmpty()) {
        return undefined;
    }
    return this.items[this.count - 1];
}
复制代码

6.清空栈

clear() {
    this.items = {};
    this.count = 0;
}

复制代码