栈

基本概念

栈是一种后进先出(LIFO，Last In First Out)的数据结构。只用 pop 和 push 完成增删的“数组”。

栈只有一边开口存取数据，称开口的那一端为“栈顶”，封死的那一端为“栈底”（类似于盛水的木桶，从哪进去的最后还得从哪出来）。

“后进先出”原则

使用栈存储数据元素，对数据元素的“存”和“取”有严格的规定：数据按一定的顺序存储到栈中，当需要调取栈中某数据元素时，需要将在该数据元素之后进栈的先出栈，该数据元素才能从栈中提取出来。

栈操作数据元素的方法

栈操作数据元素只有两种动作：

1. 数据元素用栈的数据结构存储起来，称为“入栈”，也叫“压栈”。
2. 数据元素由于某种原因需要从栈结构中提取出来，称为“出栈”，也叫“弹栈”。

JS实现栈

class Stack {
    constructor() {
        this.dataStore = []    
    }
    // 进栈
    push(element) {
        this.dataStore.push(element)    
    }
    // 出栈
    pop() {
        return this.dataStore.pop()    
    }
    // 返回栈顶元素
    peek() {
        return this.dataStore[dataStore.length - 1]    
    }
    // 是否为空栈
    isEmpty() {
        return this.dataStore.length === 0    
    }
    // 获取栈结构的长度
    size() {
        return this.dataStore.length    
    }
    // 清除所有元素
    clear() {
        this.dataStore = []    
    }
}