专栏首页SpringCloud专栏3Java学习笔记之数据结构——栈

3Java学习笔记之数据结构——栈

栈,是一种特殊的链表。栈,只能在表尾进行插入和删除。好比一个弹夹,往里面压子弹,每次添加时都是在弹夹最外部添加,打出子弹时也是每次都从最外部打出。

它是一种LIFO(last in first out)的线性结构。约定:末尾,也就是允许被插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。

平时在开发中貌似很少用到这个数据结构,或者说不知道该什么场合下使用栈,可能总是习惯性用数组Array来解决问题。其实在某些场合下,栈是最应景的结构。

像Android里的activity,打开一个界面再打开一个,按返回键时,就是先关闭最后打开的页面,这就是典型的栈,还有浏览器的返回按钮也一样。包括jvm的栈区,能保存方法调用层级,当递归过深时会发生栈溢出。

从实现上来看,栈这样的结构比较简单,比单链表要简单,毕竟它不能指定插入位置。这里就不写栈的实现类了,直接用java官方的Stack。

主要有下面的一些方法

1-->public Stack()创建一个空堆栈

2-->public boolean empty()测试堆栈是否为空;

3-->public E pop()移除堆栈顶部的对象,并作为此函数的值返回该对象。 

4-->public E push(E item)把项压入堆栈顶部

5-->public E peek()查看堆栈顶部的对象,但不从堆栈中移除它。 

6-->public boolean empty()测试堆栈是否为空

主要通过几个应用的场景例子来描述栈的作用。

一:将10进制的数M,转为N进制

这个是将25转为2进制的一个算法表示。后面的1、0代表除2后的余数,等到除以2等于0时,计算完毕,将余数倒序排列,即得到二进制值。即25的二进制值是11001.

可以用栈来存储余数,计算完毕后,从栈里读取即可。

private static void ten2n(int m, int n) {
        Stack<Integer> stack = new Stack<>();
        //除后不为0的依次入栈
        while (m / n != 0) {
            stack.push(m % n);
            m = m / n;
        }
        //入栈最后一位
        stack.push(m % n);

        StringBuffer sb = new StringBuffer();
        //栈里有值,就依次出栈
        while (!stack.empty()) {
            Integer x = stack.pop();
            sb.append(x);
        }
        System.out.print(sb.toString());
    }

二:括号配对问题

判断一行包含多个括号的字符串,是否括号是一一配对的。

譬如[({})]这个就是配对的,而([[]})这种就是不配对的。

private static boolean match(String s) {
        Stack<Character> stack = new Stack<>();
        if (s == null) {
            throw new NullPointerException("空串");
        }
        //遍历s的每个字符,如果为左括号就入栈,如果为右括号,就和栈顶的进行匹配,如果不匹配,就return false,如果匹配,就移除栈顶的左括号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                //如果出现的是右括号,但是栈里已经空了,说明肯定不匹配
                if (stack.empty()) {
                    return false;
                }
                if (c == ')') {
                    //和栈顶的匹配,继续下次循环。不匹配,return false
                    if ('(' != stack.pop()) {
                        return false;
                    }
                }
                if (c == ']') {
                    //和栈顶的匹配,继续下次循环。不匹配,return false
                    if ('[' != stack.pop()) {
                        return false;
                    }
                }
                if (c == '}') {
                    //和栈顶的匹配,继续下次循环。不匹配,return false
                    if ('{' != stack.pop()) {
                        return false;
                    }
                }
            }
        }
        //循环完毕,如果栈空,则匹配完毕。不空则不匹配
        return stack.empty();
    }

以上就是使用栈来处理的两个小算法。另外还有很多,譬如递归等。等我以后碰到了特别适合栈来处理的事情时再补充。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ3527: [Zjoi2014]力(FFT)

    那么\(E_j = \sum_{i = 1}^{j - 1} q_i (i - j)^2 - \sum_{i = j + 1}^n q_i (i - j)^2\...

    attack
  • 「小程序JAVA实战」 小程序抽离公用方法进行模块化(12)

    区别如果用了 ${} 最外层需要用``符号,如果你喜欢老套路可以按照我的 "Goodbye " + name + " !" 这种。

    IT故事会
  • 多线程通信的三大法器,你真的会用吗?

    wait, notify, notifyAll 是多线程之间通信最重要的 3 个方法,今天,栈长给大家普及一下它们的知识要点及应用实战。

    Java技术栈
  • 短小强悍!一个基于 Redis 的限流系统的设计~

    本文讲述基于 Redis 的限流系统的设计,主要会谈及限流系统中限流策略这个功能的设计;在实现方面,算法使用的是令牌桶算法来,访问 Redis 使用 lua 脚...

    java思维导图
  • 「小程序JAVA实战」 小程序私有页面的生命周期以及导航(10)

    PS:这块主要是对配置的生命周期的熟悉,了解下redirectTo 和 navigateTo 之前的区别。

    IT故事会
  • Java必会技术图,是可以帮你薪资翻倍的

    可以说,Java是现阶段中国互联网公司中,覆盖度最广的研发语言,掌握了Java技术体系,不管在成熟的大公司,快速发展的公司,还是创业阶段的公司,都能有立足之地。

    奋斗蒙
  • IntelliJ IDEA 2018.3 正式版发布!

    IntelliJ IDEA 今年的最后一次大版本更新 2018.3 现已正式发布,值得关注的更新包括支持 Java 12、Git submodule、GitHu...

    Java技术栈
  • Intellij IDEA Debug 调试技巧

    F8: 跳到下一步 F7:进入到代码 Alt+shift+F7:强制进入代码 Shift+F8:跳到下一个断点 Atl+F9:运行到光标处 ctrl+shift...

    Java技术栈
  • BAT等一线互联网公司中,Java开发的招聘标准

    扎实的计算机专业基础,包括算法和数据结构,操作系统,计算机网络,计算机体系结构,数据库等

    美的让人心动
  • Golang 之协程详解

      对于 进程、线程,都是有内核进行调度,有 CPU 时间片的概念,进行 抢占式调度(有多种调度算法)

    李海彬

扫码关注云+社区

领取腾讯云代金券