数据结构 - 栈

image.png
使用arraylist来创建stack是因为push和pop操作都只在尾部操作，这样数组的效率是最高的。使用双向链表也可以，单向链表删除需要从头开始找到尾

class Stack {
    constructor() {
        this.list = new ArrayList();
    }

    // 清空栈
    clear() {
        this.list.clear();
    }

    // 获取size
    getSize() {
        return this.list.getSize();
    }

    // 判断是否为空
    isEmpty() {
        return this.list.isEmpty();
    }

    // 入栈 
    // 由于是从最后插入，数组不需要挪位置，所以复杂度：O(1)
    push(ele) {
        this.list.add(ele);
    }

    // pop出栈
    // 数组删除最后一个也不需要挪位置 复杂度：O(1) 
    pop() {
        return this.list.remove(this.list.getSize() - 1);
    }

    // 获取栈顶元素 复杂度：O(1)
    top() {
        return this.list.get(this.list.getSize() - 1);
    }
}