栈（Stack）

首发于：2020-08-03

概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。具备后进先出（LIFO）的特性。

JavaScript 中的实现

JavaScript 中的数组实现了栈的特性。

let stack = [1, 2, 3]
// 入栈
stack.push(4) // 4
// 出栈
stack.pop() // 4
// 删除栈底元素并取出
stack.shift() // 1
// 在栈底添加元素，并返回栈的长度
stack.unshift(1) // 3

下面我们也可以来实现一个自己的栈

class Stack {
    constructor() {
        this.items = []
    }

    push(item) {
        this.items.push(item)
    }

    pop() {
        return this.items.pop()
    }

    peek() {
        return items[this.items.length - 1]
    }

    isEmpty() {
        return this.items.length === 0
    }

    clear() {
        this.items = []
    }

    size() {
        return this.items.length
    }

    toString() {
        return this.items.toString()
    }
}