数据结构---栈

前言

数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。 但是有时候，我们为了实现某些功能，必须对这种任意性加以限制。 栈和队列就是比较常见的受限的线性结构。

特点

1. 栈是后进先出（last in first out）的，就是后进入的元素，先出栈。类似于自动餐托盘，最后放上的托盘，往往先拿出去使用
2. 栈的最上面的元素被称为栈顶，栈的最内的元素，被称为栈底
3. 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
4. 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的操作

push：压入栈顶

pop：从栈顶弹出

peak：获取栈顶元素

size：栈的长度

代码实现

class STACK {
    constructor() {
        this.static = [];
    }

    push(val) {
        this.static.push(val);
    }

    pop(val) {
        this.static.pop(val);
    }

    peak() {
        return this.static[this.static.length - 1];
    }

    size() {
        return this.static.length;
    }
}

export default STACK;

栈相关的基础算法题

一、后缀表达式（逆波兰表达式）

题： 已知一个后缀表达式 6 5 2 3 + 8 * + 3 + *，求该后缀表达式的值。

解： 后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。则其求值过程如下：

• 1）遍历表达式，遇到的数字首先放入栈中，此时栈为 [6 5 2 3] 。
• 2）接着读到 +，则弹出3和2，计算 3 + 2，计算结果等于 5，并将 5 压入到栈中，栈为 [6 5 5] 。
• 3）读到 8 ，将其直接放入栈中，[6 5 5 8] 。
• 4）读到 *，弹出 8 和 5 ，计算 8 * 5，并将结果 40 压入栈中，栈为 [6 5 40]。而后过程类似，读到 +，将 40 和 5 弹出，将 40 + 5 的结果 45 压入栈，栈变成[6 45]，读到3，放入栈 [6 45 3]...以此类推，最后结果为 288。

function ReversePoland(arr) {
    if (!Array.isArray(arr)) return;
    const stack = new STACK();

    for (const item of arr) {
        if (typeof item === 'number') {
            stack.push(item);
        } else {
            const val1 = stack.pop();
            const val2 = stack.pop();

            switch (item) {
                case '+':
                    stack.push(val2 + val1);
                case '-':
                    stack.push(val2 - val1);
                case '*':
                    stack.push(val2 * val1);
                case '/':
                    stack.push(val2 / val1);
                default
            };
        }
    }
}