[js数据结构]–栈

定义

栈是一种遵从先进后出原则的有序集合。新添加的以及待删除的元素都保存在栈的一端（栈顶）

相反另一端就是栈底。很好的一个例子就是浏览器的后退，前进功能，前进就是入栈的操作，后退就是出栈。

冷静分析

栈的功能应该包括以下：

1. 添加元素至栈顶
2. 移除栈顶元素切返回被移除的元素
3. 查找栈顶元素
4. 检验栈是否含有元素
5. 清除栈
6. 返回栈的长度

代码实现

// 数组版
class Stack{
    constructor(){
        this.index = 0
        this.eles = []
    }
    push(ele){
        this.eles[index] = ele
    }
    pop(){
        return this.eles.pop()
    }
    isEmpty(){
        return this.eles.length === 0
    }
    clear(){
        this.eles.length = 0
    }
    size(){
        return this.eles.length
    }
}
// 对象版本
class Stack {
    constructor() {
        this._index = 0
        this._eles = {}
    }
    push(ele) {
        this._eles[this._index] = ele
        this._index++
    }
    pop() {
        if (this.isEmpty()) {
            return undefined
        }
        this._index--
        const delEle = this._eles[this._index]
        delete this._eles[this._index]
        return delEle
    }
    isEmpty() {
        return this._index === 0
    }
    clear() {
        this._index = 0
        this._eles = {}
    }
    size() {
        return this._index
    }
}

复制代码

疑问

数组版本和对象版本的区别在哪？

数组大部分的方法时间冗杂度都是O(n) 意味着元素越多，所需时间更多，占用内存空间也更多。

采用对象形式来实现复杂度均为O(1)