首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >白话文讲栈

白话文讲栈

作者头像
幺鹿
发布于 2019-04-18 08:48:58
发布于 2019-04-18 08:48:58
45503
代码可运行
举报
文章被收录于专栏:Java呓语Java呓语
运行总次数:3
代码可运行

思考题

给定一个仅包含字符:(,),[,]的字符串,确定输入字符串是否有效。 字符串有效的定义如下:

  • 开括号必须用同一类型的括号闭合。
  • 开方括号必须按正确顺序闭合。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 示例1
Input: "()"
Output: true
// 示例2
Input: "()[]{}"
Output: true
// 示例3
Input: "(]"
Output: false

可以先思考一下这个问题,是否可以结合栈解决呢?

栈(stack)又名堆栈,它是一种操作受限的线性表。其限制是仅允许在线性表头进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。

  • 向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;
  • 从一个栈删除元素又称作出栈、退栈或弹栈,它是把栈顶元素删掉,使下方的元素成为新的栈顶元素;

栈按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

关于栈我列举一个很贴切的例子,就是一摞叠在一起的书。假设我们平时放书的时候,都是从下往上一本一本的放,取书的时候也都是从上往下一本一本的取,不能从中间任意位置抽取和放置,这就是典型的栈结构。

一叠书.png

如何实现栈呢?

前面我们讲解过数组和链表,栈也可以使用这两个数据结构去实现。基于数组实现的栈,我们称之为数组栈。基于链表实现的栈,我们称之为链式栈。由于数组的特性,数组栈的空间是有界的,当栈的空间不满足需求时,需要执行扩容。而链表理论上则是无界的,因为实际受到物理资源限制。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组,申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了,直接返回 false,入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置,并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

了解了定义和基本操作,那它的操作的时间、空间复杂度是多少呢?

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。

注意,这里存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这 n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

空间复杂度分析是不是很简单?时间复杂度也不难。不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)。

Java中的栈的实现

Java中的栈我们主要关注Stack类,它继承自VectorVector是线程安全容器,但由于使用synchronized锁,在要求高性能高并发环境下并不推荐。

Stack使用数组存储元素,但凡使用数组构建的数据结构都会有一个共通的问题——需要扩容。在JDK8中,默认情况下Stack的扩容规则是当栈的大小等于容量大小时,则将当前容量扩大为现在容量的两倍。如果要修改默认扩容行为,可以通过构造器设定扩容的步长,以求更合理的配置扩容。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Object (java.lang)
       AbstractCollection (java.util)
              AbstractList (java.util)
                     Vector (java.util)
                            Stack (java.util)

解答思考题

使用栈这种数据结构,使得我们很容易解决诸如逆波兰式汉诺塔等问题。熟悉栈的定义并不难,但我们对栈的理解不能仅仅停留在静态栈的层面上,更多的需要思考栈的动态性,结合这些动态性我们可以解决哪些问题。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public boolean isValid(String s) {

        if ((s.length() & 1) == 1) {
            return false;
        }

        HashMap<Character, Character> symbolMap = new HashMap<>();
        symbolMap.put(')', '(');
        symbolMap.put('}', '{');
        symbolMap.put(']', '[');

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case ')':
                case '}':
                case ']':
                    if (stack.empty()) {
                        return false;
                    } else if (Objects.equals(stack.lastElement(), symbolMap.get(c))) {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                    break;
                default:
                    stack.push(c);
                    break;
            }
        }
        return stack.empty();
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.04.10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
混杂模式
一般情况下,网卡往往只会接收目的地址是它的数据包而不会接收目的地址不是它的数据包。
随心助手
2024/05/31
4640
混杂模式
Python黑帽编程 4.1 Sniffer(嗅探器)之数据捕获(上)
Python黑帽编程 4.1 Sniffer(嗅探器)之数据捕获(上) 网络嗅探,是监听流经本机网卡数据包的一种技术,嗅探器就是利用这种技术进行数据捕获和分析的软件。 编写嗅探器,捕获数据是前置功能,
用户1631416
2018/04/12
3.6K0
Python黑帽编程 4.1 Sniffer(嗅探器)之数据捕获(上)
Linux 网络接口混杂模式(Promiscuous mode)认知
认定一件事,即使拿十分力气都无法完成,也要拿出十二分力气去努力。 ---《剑来》
山河已无恙
2024/03/06
2.2K0
Linux 网络接口混杂模式(Promiscuous mode)认知
Linux 网络配置常用命令及示例
这样配置的IP地址在重启机器后会丢失,所以一般应该把网络配置写入文件中。 如Ubuntu可以将网卡配置写入/etc/network/interfaces(Redhat和CentOS则需要写入 /etc/sysconfig/network-scripts/ifcfg-eth0中):
程序熵
2025/05/02
5340
Linux 网络配置常用命令及示例
Linux:ifconfig命令
ifconfig命令被用于配置和显示Linux内核中网络接口的网络参数。用ifconfig命令配置的网卡信息,在网卡重启后机器重启后,配置就不存在。要想将上述的配置信息永远的存的电脑里,那就要修改网卡的配置文件了。
HLee
2021/08/11
1.7K0
Linux:ifconfig命令
网络互联参考模型(详解)
数据以电子信号的形式穿越介质到达正确的计算机,然后转换成最初的形式,以便接收者能够阅读
黄规速
2022/04/14
1.3K0
网络互联参考模型(详解)
Linux 命令(108)—— ifconfig 命令
ifconfig(configure a network interface)命令是系统管理员命令,用于查看和配置网络接口。
恋喵大鲤鱼
2020/02/17
2.1K0
详解Linux双网卡绑定之bond0「建议收藏」
网卡bond是通过多张网卡绑定为一个逻辑网卡,实现本地网卡的冗余,带宽扩容和负载均衡,在生产场景中是一种常用的技术。Kernels 2.4.12及以后的版本均供bonding模块,以前的版本可以通过patch实现。
全栈程序员站长
2022/07/21
14.1K0
数据包发送与嗅探
实验过程中采用过libnet与libpcap,最后全部转为Raw Socket发送与嗅探。
公众号guangcity
2019/09/20
2.8K0
数据包发送与嗅探
ifconfig command
ifconfig(configure a network interface)命令是系统管理员命令,用于查看和配置网络接口。
恋喵大鲤鱼
2023/10/12
2450
ifconfig命令
ifconfig代表interface configuration,其用于查看和更改系统上网络接口的配置。
WindRunnerMax
2021/02/25
1.1K0
一天一个 Linux 命令(46):ifconfig 命令
Linux下的ifconfig命令(英文全称是“network interfaces configuring”)是用于配置和显示Linux内核中网络接口的网络命令。用ifconfig命令配置的网卡信息,在网卡重启后机器重启后,配置就不存在。要想将上述的配置信息永远的存的电脑里,那就要修改网卡的配置文件了。有点类似windows系统下的ipconfig命令行工具
joshua317
2022/03/25
6980
Linux 多网卡的7种bond模式原理
网卡绑定mode共有七种(0~6) bond0、bond1、bond2、bond3、bond4、bond5、bond6
用户6543014
2019/10/25
8.4K0
Linux下多网卡绑定bond及模式介绍
主要是通过将多个物理网卡绑定到一个逻辑网卡上,实现了本地网卡的冗余,带宽扩容以及负载均衡。
用户8705048
2021/06/08
8.3K0
Linux 网络参数和 ifconfig
一般来说,直接输入 ifconfig 就会列出目前已经被启动的卡,不论这个卡是否有设置 IP,都会被显示出来。而如果是输入 ifconfig eth0,则会显示出这个接口的相关数据,而不管该接口是否启动。所以,如果你想要知道某个网卡的 Hardware Address,直接输入“ifconfig "网络接口代号"”即可。至于上述代码中出现的各项数据是这样的(数据排列由上而下、由左而右)。
ICT系统集成阿祥
2024/12/03
3330
Linux 网络参数和 ifconfig
LVS工作总结之原理篇–DR模式
先解释几个名词: LB(Load Balancer) :负载均衡器,也就是装有LVS(ipvsadm)的server VIP(Virtual IP):虚拟IP,也就是给远程客户端(网民)提供服务的外部IP,比如,提供80服务,域名是www.a.com,则www.a.com 对应的A记录就是VIP LD(Load Balancer Director):同LB,负载均衡调度器 real server:即后端提供真是服务的server,比如你提供的是80服务,那你机器可能就是装着Apache这中web服务器 DI
老七Linux
2018/05/09
1.6K0
12 Sep 2019 网络学习(一)
cidr例子:16.158.165.91/22 (32 = 22 (16 + 6) + 10)
俊采
2023/10/17
2140
Linux网络配置和重置ROOT密码
Linux服务器默认网卡配置文件在/etc/sysconfig/network-scripts/下,命名的名称一般为:ifcfg-eth0 ifcfg-eth1 ,eth0表示第一块网卡,eth1表示第二块网卡,依次类推。一般DELL R720标配有4块千兆网卡。
用户8826052
2021/07/12
4.1K0
linux(九)之网络基础
一、ping命令   1.1、作用      用于检测主机。执行ping指令会使用ICMP传输协议,发出要求回应的信息,若远端主机的网络功能没有问题,就会回应该信息,因而得知该主机运作正常。   1.2、命令说明    ping [-dfnqrRv][-c<完成次数>][-i<间隔秒数>][-I<网络界面>][-l<前置载入>][-p<范本样式>][-s<数据包大小>][-t<存活数值>][主机名称或IP地址]   1.3、参数说明           ● -d 使用Socket的SO_D
用户1195962
2018/01/18
1.1K0
linux(九)之网络基础
Ubuntu14.04双网卡主备配置
近日有个需求,交换机有两台,做了堆叠,服务器双网卡,每个分别连到一台交换机上。这样就需要将服务器的网卡做成主备模式,以增加安全性,使得当其中一个交换机不通的时候网卡能够自动切换。 整体配置不难,网上也有相应的教程,可能有些是ubuntu的版本不同,所以配置以后没有达到应有的效果,最终通过51运维网的Ubuntu双网卡绑定的设置方法一文中的方法实现了该功能,本文简单记录之。 一、Bond的工作模式 Linux bonding驱动提供了一个把多个网络接口设备捆绑为单个的网络接口设置来使用,用于网络负载均衡及网络
魏守峰
2018/04/28
3K0
相关推荐
混杂模式
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档