数据结构---栈

前言

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

特点

  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
            };
        }
    }
}

相关推荐

  1. 数据结构--

    2024-07-20 18:36:03       61 阅读
  2. 数据结构-

    2024-07-20 18:36:03       58 阅读
  3. 数据结构---(Stack)

    2024-07-20 18:36:03       65 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 18:36:03       123 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 18:36:03       131 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 18:36:03       109 阅读
  4. Python语言-面向对象

    2024-07-20 18:36:03       117 阅读

热门阅读

  1. Python语言的优势所在

    2024-07-20 18:36:03       22 阅读
  2. Xubuntu22.04 终端命令调用图形设置工具

    2024-07-20 18:36:03       22 阅读
  3. 远程连接VScode到云服务器 ECS

    2024-07-20 18:36:03       22 阅读
  4. SQL Server邮件通知:数据库通信的自动化利器

    2024-07-20 18:36:03       23 阅读
  5. Elasticsearch 统计订单销售高峰时间段

    2024-07-20 18:36:03       27 阅读
  6. Vue 自定义组件编写 案例实战

    2024-07-20 18:36:03       22 阅读
  7. 音视频环境搭建

    2024-07-20 18:36:03       25 阅读
  8. 编织文字的魔法:探索WebKit的CSS文本效果

    2024-07-20 18:36:03       31 阅读
  9. c++判断路径是否存在,判断文件夹是否存在

    2024-07-20 18:36:03       24 阅读
  10. Python数据类型转换:掌握数据形态的转换艺术

    2024-07-20 18:36:03       32 阅读
  11. Spring Boot与JPA:无缝集成,轻松管理数据库】

    2024-07-20 18:36:03       28 阅读