精华内容
下载资源
问答
  • 队列面试题

    万次阅读 2020-11-24 10:03:49
    1 面试题 1.1 说说你对队列的理解,队列和集合的区别。 答:对队列的理解: 首先队列本身也是个容器,底层也会有不同的数据结构,比如 LinkedBlockingQueue 是底层是链表结构,所以可以维持先入先出的顺序,比如 ...

    1 面试题

    1.1 说说你对队列的理解,队列和集合的区别。

    答:对队列的理解:

    首先队列本身也是个容器,底层也会有不同的数据结构,比如 LinkedBlockingQueue 是底层是链表结构,所以可以维持先入先出的顺序,比如 DelayQueue 底层可以是队列或堆栈,所以可以保证先入先出,或者先入后出的顺序等等,底层的数据结构不同,也造成了操作实现不同;
    部分队列(比如 LinkedBlockingQueue )提供了暂时存储的功能,我们可以往队列里面放数据,同时也可以从队列里面拿数据,两者可以同时进行;
    队列把生产数据的一方和消费数据的一方进行解耦,生产者只管生产,消费者只管消费,两者之间没有必然联系,队列就像生产者和消费者之间的数据通道一样,如 LinkedBlockingQueue;
    队列还可以对消费者和生产者进行管理,比如队列满了,有生产者还在不停投递数据时,队列可以使生产者阻塞住,让其不再能投递,比如队列空时,有消费者过来拿数据时,队列可以让消费者 hodler 住,等有数据时,唤醒消费者,让消费者拿数据返回,如 ArrayBlockingQueue;
    队列还提供阻塞的功能,比如我们从队列拿数据,但队列中没有数据时,线程会一直阻塞到队列有数据可拿时才返回。
    队列和集合的区别:

    和集合的相同点,队列(部分例外)和集合都提供了数据存储的功能,底层的储存数据结构是有些相似的,比如说 LinkedBlockingQueue 和 LinkedHashMap 底层都使用的是链表,ArrayBlockingQueue 和 ArrayList 底层使用的都是数组。

    和集合的区别:

    2.1 部分队列和部分集合底层的存储结构很相似的,但两者为了完成不同的事情,提供的 API 和其底层的操作实现是不同的。

    2.2 队列提供了阻塞的功能,能对消费者和生产者进行简单的管理,队列空时,会阻塞消费者,有其他线程进行 put 操作后,会唤醒阻塞的消费者,让消费者拿数据进行消费,队列满时亦然。

    2.3 解耦了生产者和消费者,队列就像是生产者和消费者之间的管道一样,生产者只管往里面丢,消费者只管不断消费,两者之间互不关心。

    1.2 哪些队列具有阻塞的功能,大概是如何阻塞的?

    答:队列主要提供了两种阻塞功能,如下:

    LinkedBlockingQueue 链表阻塞队列和 ArrayBlockingQueue 数组阻塞队列是一类,前者容量是 Integer 的最大值,后者数组大小固定,两个阻塞队列都可以指定容量大小,当队列满时,如果有线程 put 数据,线程会阻塞住,直到有其他线程进行消费数据后,才会唤醒阻塞线程继续 put,当队列空时,如果有线程 take 数据,线程会阻塞到队列不空时,继续 take。
    SynchronousQueue 同步队列,当线程 put 时,必须有对应线程把数据消费掉,put 线程才能返回,当线程 take 时,需要有对应线程进行 put 数据时,take 才能返回,反之则阻塞,举个例子,线程 A put 数据 A1 到队列中了,此时并没有任何的消费者,线程 A 就无法返回,会阻塞住,直到有线程消费掉数据 A1 时,线程 A 才能返回。

    1.3 底层是如何实现阻塞的?

    答:队列本身并没有实现阻塞的功能,而是利用 Condition 的等待唤醒机制,阻塞底层实现就是更改线程的状态为沉睡,细节我们在锁小节会说到。

    1.4 LinkedBlockingQueue 和 ArrayBlockingQueue 有啥区别。

    答:相同点:

    两者的阻塞机制大体相同,比如在队列满、空时,线程都会阻塞住。
    不同点:

    LinkedBlockingQueue 底层是链表结构,容量默认是 Interge 的最大值,ArrayBlockingQueue 底层是数组,容量必须在初始化时指定。
    两者的底层结构不同,所以 take、put、remove 的底层实现也就不同。

    1.5 往队列里面 put 数据是线程安全的么?为什么?

    答:是线程安全的,在 put 之前,队列会自动加锁,put 完成之后,锁会自动释放,保证了同一时刻只会有一个线程能操作队列的数据,以 LinkedBlockingQueue 为例子,put 时,会加 put 锁,并只对队尾 tail 进行操作,take 时,会加 take 锁,并只对队头 head 进行操作,remove 时,会同时加 put 和 take 锁,所以各种操作都是线程安全的,我们工作中可以放心使用。

    1.6 take 的时候也会加锁么?既然 put 和 take 都会加锁,是不是同一时间只能运行其中一个方法。

    答:1:是的,take 时也会加锁的,像 LinkedBlockingQueue 在执行 take 方法时,在拿数据的同时,会把当前数据删除掉,就改变了链表的数据结构,所以需要加锁来保证线程安全。

    2:这个需要看情况而言,对于 LinkedBlockingQueue 来说,队列的 put 和 take 都会加锁,但两者的锁是不一样的,所以两者互不影响,可以同时进行的,对于 ArrayBlockingQueue 而言,put 和 take 是同一个锁,所以同一时刻只能运行一个方法。

    1.7 工作中经常使用队列的 put、take 方法有什么危害,如何避免。

    答:当队列满时,使用 put 方法,会一直阻塞到队列不满为止。

    当队列空时,使用 take 方法,会一直阻塞到队列有数据为止。

    两个方法都是无限(永远、没有超时时间的意思)阻塞的方法,容易使得线程全部都阻塞住,大流量时,导致机器无线程可用,所以建议在流量大时,使用 offer 和 poll 方法来代替两者,我们只需要设置好超时阻塞时间,这两个方法如果在超时时间外,还没有得到数据的话,就会返回默认值(LinkedBlockingQueue 为例),这样就不会导致流量大时,所有的线程都阻塞住了。

    这个也是生产事故常常发生的原因之一,尝试用 put 和 take 方法,在平时自测中根本无法发现,对源码不熟悉的同学也不会意识到会有问题,当线上大流量打进来时,很有可能会发生故障,所以我们平时工作中使用队列时,需要谨慎再谨慎。

    1.8 把数据放入队列中后,有木有办法让队列过一会儿再执行?

    答:可以的,DelayQueue 提供了这种机制,可以设置一段时间之后再执行,该队列有个唯一的缺点,就是数据保存在内存中,在重启和断电的时候,数据容易丢失,所以定时的时间我们都不会设置很久,一般都是几秒内,如果定时的时间需要设置很久的话,可以考虑采取延迟队列中间件(这种中间件对数据会进行持久化,不怕断电的发生)进行实现。

    1.9 DelayQueue 对元素有什么要求么,我把 String 放到队列中去可以么?

    答:DelayQueue 要求元素必须实现 Delayed 接口,Delayed 本身又实现了 Comparable 接口,Delayed 接口的作用是定义还剩下多久就会超时,给使用者定制超时时间的,Comparable 接口主要用于对元素之间的超时时间进行排序的,两者结合,就可以让越快过期的元素能够排在前面。

    所以把 String 放到 DelayQueue 中是不行的,编译都无法通过,DelayQueue 类在定义的时候,是有泛型定义的,泛型类型必须是 Delayed 接口的子类才行。

    1.10 DelayQueue 如何让快过期的元素先执行的?

    答:DelayQueue 中的元素都实现 Delayed 和 Comparable 接口的,其内部会使用 Comparable 的 compareTo 方法进行排序,我们可以利用这个功能,在 compareTo 方法中实现过期时间和当前时间的差,这样越快过期的元素,计算出来的差值就会越小,就会越先被执行。

    1.11 如何查看 SynchronousQueue 队列的大小?

    答:此题是个陷进题,题目首先设定了 SynchronousQueue 是可以查看大小的,实际上 SynchronousQueue 本身是没有容量的,所以也无法查看其容量的大小,其内部的 size 方法都是写死的返回 0。

    1.12 SynchronousQueue 底层有几种数据结构,两者有何不同?

    答:底层有两种数据结构,分别是队列和堆栈。

    两者不同点:

    队列维护了先入先出的顺序,所以最先进去队列的元素会最先被消费,我们称为公平的,而堆栈则是先入后出的顺序,最先进入堆栈中的数据可能会最后才会被消费,我们称为不公平的。
    两者的数据结构不同,导致其 take 和 put 方法有所差别,具体的可以看 《 SynchronousQueue 源码解析 》章节。

    1.13 假设 SynchronousQueue 底层使用的是堆栈,线程 1 执行 take 操作阻塞住了,然后有线程 2 执行 put 操作,问此时线程 2 是如何把 put 的数据传递给 take 的?

    答:这是一个好问题,也是理解 SynchronousQueue 的核心问题。

    首先线程 1 被阻塞住,此时堆栈头就是线程 1 了,此时线程 2 执行 put 操作,会把 put 的数据赋值给堆栈头的 match 属性,并唤醒线程 1,线程 1 被唤醒后,拿到堆栈头中的 match 属性,就能够拿到 put 的数据了。

    严格上说并不是 put 操作直接把数据传递给了 take,而是 put 操作改变了堆栈头的数据,从而 take 可以从堆栈头上直接拿到数据,堆栈头是 take 和 put 操作之间的沟通媒介。

    1.14 如果想使用固定大小的队列,有几种队列可以选择,有何不同?

    答:可以使用 LinkedBlockingQueue 和 ArrayBlockingQueue 两种队列。

    前者是链表,后者是数组,链表新增时,只要建立起新增数据和链尾数据之间的关联即可,数组新增时,需要考虑到索引的位置(takeIndex 和 putIndex 分别记录着下次拿数据、放数据的索引位置),如果增加到了数组最后一个位置,下次就要重头开始新增。

    1.15 ArrayBlockingQueue 可以动态扩容么?用到数组最后一个位置时怎么办?

    答:不可以的,虽然 ArrayBlockingQueue 底层是数组,但不能够动态扩容的。

    假设 put 操作用到了数组的最后一个位置,那么下次 put 就需要从数组 0 的位置重新开始了。

    假设 take 操作用到数组的最后一个位置,那么下次 take 的时候也会从数组 0 的位置重新开始。

    1.16 ArrayBlockingQueue take 和 put 都是怎么找到索引位置的?是利用 hash 算法计算得到的么?

    答:ArrayBlockingQueue 有两个属性,为 takeIndex 和 putIndex,分别标识下次 take 和 put 的位置,每次 take 和 put 完成之后,都会往后加一,虽然底层是数组,但和 HashMap 不同,并不是通过 hash 算法计算得到的。

    2 总结

    队列是锁、线程池等复杂 API 的基础,很多面试官都会在问这些 API 时冷不防的问你队列的知识,如果你回答不好,面试官可能会认为你仅仅是用过锁和线程池,但却对其底层的原理和实现了解的不够全面,所以说队列还是蛮重要的,但队列的源码比较复杂,建议大家可以尝试 debug 的方式来理解源码。

    展开全文
  • 消息队列面试题

    2019-09-07 16:14:12
  • Java笔试面试-消息队列面试题总结

    万次阅读 多人点赞 2019-09-26 15:10:12
    1.消息队列的应用场景有哪些? 答:消息队列的应用场景如下。 应用解耦,比如,用户下单后,订单系统需要通知库存系统,假如库存系统无法访问,则订单减库存将失败,从而导致订单失败。订单系统与库存系统耦合,这...

    1.消息队列的应用场景有哪些?

    答:消息队列的应用场景如下。

    • 应用解耦,比如,用户下单后,订单系统需要通知库存系统,假如库存系统无法访问,则订单减库存将失败,从而导致订单失败。订单系统与库存系统耦合,这个时候如果使用消息队列,可以返回给用户成功,先把消息持久化,等库存系统恢复后,就可以正常消费减去库存了。
    • 削峰填谷,比如,秒杀活动,一般会因为流量过大,从而导致流量暴增,应用挂掉,这个时候加上消息队列,服务器接收到用户的请求后,首先写入消息队列,假如消息队列长度超过最大数量,则直接抛弃用户请求或跳转到错误页面。
    • 日志系统,比如,客户端负责将日志采集,然后定时写入消息队列,消息队列再统一将日志数据存储和转发。

    2.RabbitMQ 有哪些优点?

    答:RabbitMQ 的优点如下:

    • 可靠性,RabbitMQ 的持久化支持,保证了消息的稳定性;
    • 高并发,RabbitMQ 使用了 Erlang 开发语言,Erlang 是为电话交换机开发的语言,天生自带高并发光环和高可用特性;
    • 集群部署简单,正是因为 Erlang 使得 RabbitMQ 集群部署变的非常简单;
    • 社区活跃度高,因为 RabbitMQ 应用比较广泛,所以社区的活跃度也很高;
    • 解决问题成本低,因为资料比较多,所以解决问题的成本也很低;
    • 支持多种语言,主流的编程语言都支持,如 Java、.NET、PHP、Python、JavaScript、Ruby、Go 等;
    • 插件多方便使用,如网页控制台消息管理插件、消息延迟插件等。

    3.RabbitMQ 有哪些重要的角色?

    答:RabbitMQ 包含以下三个重要的角色:

    • 生产者:消息的创建者,负责创建和推送数据到消息服务器;
    • 消费者:消息的接收方,用于处理数据和确认消息;
    • 代理:就是 RabbitMQ 本身,用于扮演“快递”的角色,本身不生产消息,只是扮演“快递”的角色。

    4.RabbitMQ 有哪些重要的组件?它们有什么作用?

    答:RabbitMQ 包含的重要组件有:ConnectionFactory(连接管理器)、Channel(信道)、Exchange(交换器)、Queue(队列)、RoutingKey(路由键)、BindingKey(绑定键) 等重要的组件,它们的作用如下:

    • ConnectionFactory(连接管理器):应用程序与 RabbitMQ 之间建立连接的管理器,程序代码中使用;
    • Channel(信道):消息推送使用的通道;
    • Exchange(交换器):用于接受、分配消息;
    • Queue(队列):用于存储生产者的消息;
    • RoutingKey(路由键):用于把生成者的数据分配到交换器上;
    • BindingKey(绑定键):用于把交换器的消息绑定到队列上。

    运行流程,如下图所示:
    在这里插入图片描述

    5.什么是消息持久化?

    答:消息持久化是把消息保存到物理介质上,以防止消息的丢失。

    6.RabbitMQ 要实现消息持久化,需要满足哪些条件?

    答:RabbitMQ 要实现消息持久化,必须满足以下 4 个条件:

    • 投递消息的时候 durable 设置为 true,消息持久化,代码:channel.queueDeclare(x, true, false, false, null),参数 2 设置为 true 持久化;
    • 设置投递模式 deliveryMode 设置为 2(持久),代码:channel.basicPublish(x, x, MessageProperties.PERSISTENTTEXTPLAIN,x),参数 3 设置为存储纯文本到磁盘;
    • 消息已经到达持久化交换器上;
    • 消息已经到达持久化的队列。

    7.消息持久化有哪些缺点?如何缓解?

    答:消息持久化的缺点是很消耗性能,因为要写入硬盘要比写入内存性能较低很多,从而降低了服务器的吞吐量。可使用固态硬盘来提高读写速度,以达到缓解消息持久化的缺点。

    8.如何使用 Java 代码连接 RabbitMQ?

    答:使用 Java 代码连接 RabbitMQ 有以下两种方式:

    方式一:

    public static Connection GetRabbitConnection() {
        ConnectionFactory factory = new ConnectionFactory();
        factory.setUsername(Config.UserName);
        factory.setPassword(Config.Password);
        factory.setVirtualHost(Config.VHost);
        factory.setHost(Config.Host);
        factory.setPort(Config.Port);
        Connection conn = null;
        try {
            conn = factory.newConnection();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return conn;
    }
    

    方式二:

    public static Connection GetRabbitConnection2() {
        ConnectionFactory factory = new ConnectionFactory();
        // 连接格式:amqp://userName:password@hostName:portNumber/virtualHost
        String uri = String.format("amqp://%s:%s@%s:%d%s", Config.UserName, Config.Password, Config.Host, Config.Port,
                Config.VHost);
        Connection conn = null;
        try {
            factory.setUri(uri);
            factory.setVirtualHost(Config.VHost);
            conn = factory.newConnection();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return conn;
    }
    

    9.使用 Java 代码编写一个 RabbitMQ 消费和生产的示例?

    答:代码如下:

    public static void main(String[] args) {
        publisher();     // 生产消息
        consumer();     // 消费消息
    }
    
    /**
     * 推送消息
     */
    public static void publisher() {
        // 创建一个连接
        Connection conn = ConnectionFactoryUtil.GetRabbitConnection();
        if (conn != null) {
            try {
                // 创建通道
                Channel channel = conn.createChannel();
                // 声明队列【参数说明:参数一:队列名称,参数二:是否持久化;参数三:是否独占模式;参数四:消费者断开连接时是否删除队列;参数五:消息其他参数】
                channel.queueDeclare(Config.QueueName, false, false, false, null);
                String content = String.format("当前时间:%s", new Date().getTime());
                // 发送内容【参数说明:参数一:交换机名称;参数二:队列名称,参数三:消息的其他属性-routing headers,此属性为MessageProperties.PERSISTENT_TEXT_PLAIN用于设置纯文本消息存储到硬盘;参数四:消息主体】
                channel.basicPublish("", Config.QueueName, null, content.getBytes("UTF-8"));
                System.out.println("已发送消息:" + content);
                // 关闭连接
                channel.close();
                conn.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    
    /**
     * 消费消息
     */
    public static void consumer() {
        // 创建一个连接
        Connection conn = ConnectionFactoryUtil.GetRabbitConnection();
        if (conn != null) {
            try {
                // 创建通道
                Channel channel = conn.createChannel();
                // 声明队列【参数说明:参数一:队列名称,参数二:是否持久化;参数三:是否独占模式;参数四:消费者断开连接时是否删除队列;参数五:消息其他参数】
                channel.queueDeclare(Config.QueueName, false, false, false, null);
    
                // 创建订阅器,并接受消息
                channel.basicConsume(Config.QueueName, false, "", new DefaultConsumer(channel) {
                    @Override
                    public void handleDelivery(String consumerTag, Envelope envelope, AMQP.BasicProperties properties,
                            byte[] body) throws IOException {
                        String routingKey = envelope.getRoutingKey(); // 队列名称
                        String contentType = properties.getContentType(); // 内容类型
                        String content = new String(body, "utf-8"); // 消息正文
                        System.out.println("消息正文:" + content);
                        channel.basicAck(envelope.getDeliveryTag(), false); // 手动确认消息【参数说明:参数一:该消息的index;参数二:是否批量应答,true批量确认小于index的消息】
                    }
                });
    
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    

    10.RabbitMQ 交换器类型有哪些?

    答:RabbitMQ 消费类型也就是交换器(Exchange)类型有以下四种:

    • direct:轮询方式
    • headers:轮询方式,允许使用 header 而非路由键匹配消息,性能差,几乎不用
    • fanout:广播方式,发送给所有订阅者
    • topic:匹配模式,允许使用正则表达式匹配消息

    RabbitMQ 默认的是 direct 方式。

    11.RabbitMQ 如何确保每个消息能被消费?

    答:RabbitMQ 使用 ack 消息确认的方式保证每个消息都能被消费,开发者可根据自己的实际业务,选择 channel.basicAck() 方法手动确认消息被消费。

    12.RabbitMQ 接收到消息之后必须消费吗?

    答:RabbitMQ 接收到消息之后可以不消费,在消息确认消费之前,可以做以下两件事:

    • 拒绝消息消费,使用 channel.basicReject(消息编号, true) 方法,消息会被分配给其他订阅者;
    • 设置为死信队列,死信队列是用于专门存放被拒绝的消息队列。

    13.topic 模式下发布了一个路由键为“com.mq.rabbit.error”的消息,请问以下不能接收到消息的是?

    A:cn.mq.rabbit.*
    B:#.error
    C:cn.mq.*
    D:cn.mq.#

    答:C

    题目解析:“*”用于匹配一个分段(用“.”分割)的内容,“#”用于匹配 0 和多个字符。

    14.以下可以获取历史消息的是?

    A:topic 交换器
    B:fanout 交换器
    C:direct 交换器
    D:以上都不是

    答:C

    题目解析:fanout 和 topic 都是广播形式的,因此无法获取历史消息,而 direct 可以。

    15.RabbitMQ 包含事务功能吗?如何使用?

    答:RabbitMQ 包含事务功能,主要是对信道(Channel)的设置,主要方法有以下三个:

    • channel.txSelect() 声明启动事务模式;
    • channel.txComment() 提交事务;
    • channel.txRollback() 回滚事务。

    16.RabbitMQ 的事务在什么情况下是无效的?

    答:RabbitMQ 的事务在 autoAck=true 也就是自动消费确认的时候,事务是无效的。因为如果是自动消费确认,RabbitMQ 会直接把消息从队列中移除,即使后面事务回滚也不能起到任何作用。

    17.Kafka 可以脱离 ZooKeeper 单独使用吗?

    答:Kafka 不能脱离 ZooKeeper 单独使用,因为 Kafka 使用 ZooKeeper 管理和协调 Kafka 的节点服务器。

    18.Kafka 有几种数据保留的策略?

    答:Kafka 有两种数据保存策略:按照过期时间保留和按照存储的消息大小保留。

    19.Kafka 同时设置了 7 天和 10G 清除数据,到第五天的时候消息达到了 10G,这个时候 Kafka 将如何处理?

    答:这个时候 Kafka 会执行数据清除工作,时间和大小不论哪个满足条件,都会清空数据。

    20.什么情况会导致 Kafka 运行变慢?

    答:以下情况可导致 Kafka 运行变慢:

    • CPU 性能瓶颈
    • 磁盘读写瓶颈
    • 网络瓶颈

    21.使用 Kafka 集群需要注意什么?

    答:Kafka 集群使用需要注意以下事项:

    • 集群的数量不是越多越好,最好不要超过 7 个,因为节点越多,消息复制需要的时间就越长,整个群组的吞吐量就越低;
    • 集群数量最好是单数,因为超过一半故障集群就不能用了,设置为单数容错率更高。
    展开全文
  • 栈、队列面试题

    千次阅读 2016-07-10 17:10:14
    栈和队列面试题

     

     

    栈、队列面试题

    分析
    基本思路:用栈保存没有匹配的左括号,遍历字符串中的字符。如果字符为左括号就入栈;如果是右括号,看栈顶元素是否与其匹配,匹配则出栈,否侧返回false。
    注意:在处理过程中、处理后要小心检查栈空的情况。
    public boolean isValid(String s) {
    	if(s.equalsIgnoreCase("")) return true;
    	Map<Character,Character> ps=new HashMap<Character,Character>();
    	ps.put('{', '}');ps.put('[', ']');ps.put('(', ')');
    	Stack<Character> stack=new Stack<Character>();
    	for(char c:s.toCharArray()){
    		if(ps.containsKey(c)){
    			stack.push(c);
    		}else{
    			if(stack.isEmpty()){
    				return false;
    			}else{
    				Character top=stack.peek();
    				if(ps.get(top).equals(c)){
    					stack.pop();
    				}else{
    					return false;
    				}
    			}
    		}
    	}
    	if(!stack.isEmpty())
    		return false;
    	else
    		return true;
    }
    分析
    想要O(1)时间内获取栈中的最小值,显然就暗示不允许我们通过遍历的方式来查找最小值。
    我们能是否能用一个变量记录栈的最小值呢?如果8,2,5,1,6先依次入栈,然后再依次出栈,显然,用单个(常数个)变量是无法追踪栈当前最小值的。
    方案一:O(1)时间内的查找,我们很容易联想到哈希表,我们可以维护这样一个哈希表<栈大小,栈的最小值>,这样我们就可以在O(1)时间内得到栈中的最小值。空间复杂度为O(K),K为栈的最大长度。
    方案二:借鉴方案一的思路,我们可以始终维护一个与元素栈大小相同的最小值栈,保持最小值栈的栈顶元素为元素栈的最小值,并且同步入栈出栈。空间复杂度为O(K),K为栈的最大长度。
    代码一
    public class MinStack {
    	private Stack<Integer> stack;
    	private Map<Integer,Integer> minMap;
        public MinStack() {
            this.stack=new Stack<Integer>();
            this.minMap=new HashMap<Integer,Integer>();
        }
        public void push(int x) {
            if(stack.isEmpty()){
            	stack.push(x);
            	minMap.put(stack.size(), x);
            }else{
            	int preMin=minMap.get(stack.size());
            	stack.push(x);
            	minMap.put(stack.size(), Math.min(preMin, x));
            }
        }
        public void pop() {
            stack.pop();
        }
        
        public int top() {
    		return stack.peek();
        }
        
        public int getMin() {
    		return minMap.get(stack.size());
        }
    }
    代码二
    public class MinStack {
    	private Stack<Integer> stack;
    	private Stack<Integer> minStack;;
        public MinStack() {
            this.stack=new Stack<Integer>();
            this.minStack=new Stack<Integer>();
        }
        public void push(int x) {
            if(stack.isEmpty()){
            	stack.push(x);
            	minStack.push(x);
            }else{
            	stack.push(x);
            	int preMin=minStack.peek();
            	minStack.push(Math.min(preMin, x));
            }
        }
        public void pop() {
            stack.pop();
            minStack.pop();
        }
        
        public int top() {
    		return stack.peek();
        }
        
        public int getMin() {
    		return minStack.peek();
        }
    }
    方案一
    内部用队列保存数据,入栈操作时对应内部队列的入队操作,出栈我们需要获取队列最后一个元素,我们将队列之前的元素先出队到一个临时队列,获取队列末尾元素,然后将临时队列赋值给保存数据的队列。
    public class MyStack {
    	private Queue<Integer> queueOne;
    	private Queue<Integer> queueTemp; 
    	
    	public MyStack(){
        	queueOne=new LinkedList<Integer>();
        	queueTemp=new LinkedList<Integer>();
    	}
        public void push(int x) {
        	queueOne.add(x);
        }
    
        public void pop() {
        	while(true){
        		Integer front=queueOne.poll();
        		if(queueOne.isEmpty()){
        			Queue<Integer> t=queueOne;
        			queueOne=queueTemp;
        			queueTemp=t;
        			break;
        		}else{
        			queueTemp.add(front);
        		}
        	}
        }
    
        public int top() {
        	Integer front=null;
        	while(true){
        		front=queueOne.poll();
        		if(queueOne.isEmpty()){
        			Queue<Integer> t=queueOne;
        			queueOne=queueTemp;
        			queueTemp=t;
        			break;
        		}else{
        			queueTemp.add(front);
        		}
        	}
        	queueOne.add(front);
        	return front;
        }
    
        public boolean empty() {
            return queueOne.isEmpty();
        }
    }
    方案二
    同样用内部队列保存数据,每次入栈操作时,先将元素入队,然后将队列之前的元素依次出队并入队,这样可以保证刚入栈的元素在队列的开头。这样就保证了栈的后入先出特性。
    public class MyStack {
    	private Queue<Integer> queue;
    	
    	public MyStack(){
        	queue=new LinkedList<Integer>();
    	}
        public void push(int x) {
        	int size=queue.size();
        	queue.add(x);
        	for(int i=0;i<size;i++){
        		Integer t=queue.peek();
        		queue.poll();
        		queue.add(t);
        	}
        }
    
        public void pop() {
        	queue.poll();
        }
    
        public int top() {
        	return queue.peek();
        }
    
        public boolean empty() {
            return queue.isEmpty();
        }
    }


     
     
    分析
     
    队列是先入先出,栈是后入先出。这种特性与负负得正特性相似,负(后入先出),正(先入先出)。
    将数据先后通过两个栈的处理就可以保证先入先出了,即用栈实现了队列的特性。但是,在之前用队列实现栈的例子中,队列先入先出的特性不能充分发挥来构造后入先出的特性,只能每次入栈时,处理整个队列才能保证先入后出。
    class MyQueue {
        private Stack<Integer> stackIn;
        private Stack<Integer> stackOut;
        private void inToOut(){
        	while(!stackIn.isEmpty()){
        		Integer top=stackIn.peek();
        		stackIn.pop();
        		stackOut.push(top);
        	}
        }
        public MyQueue(){
        	stackIn=new Stack<Integer>();
        	stackOut=new Stack<Integer>();
        }
        public void push(int x) {
        	stackIn.push(x);
        }
     
        public void pop() {
        	if(stackOut.isEmpty()){
    			inToOut();
    		}
        	stackOut.pop();
        }
        public int peek() {
    		if(stackOut.isEmpty()){
    			inToOut();
    		}
    		Integer top=stackOut.peek();
    		return top;
            
        }
        public boolean empty() {
            return stackIn.isEmpty()&&stackOut.isEmpty();
        }
    }

    分析

    深度优先遍历,利用栈记录遍历路径。

    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> res=new LinkedList<Integer>();
    	Stack<TreeNode> stack=new Stack<TreeNode>();
    	TreeNode p=root;//当前处理的树根
    	while(p!=null||!stack.isEmpty()){
    		while(p!=null){//先处理左子树
    			stack.push(p);
    			p=p.left;
    		}
    	    p=stack.pop();
    		res.add(p.val);
    		//处理右子树
    		p=p.right;
    	}
    	return res;
    }

     

    public List<Integer> preorderTraversal(TreeNode root) {
    	List<Integer> res=new LinkedList<Integer>();
    	Stack<TreeNode> stack=new Stack<TreeNode>();
    	TreeNode p=root;//当前处理的树根
    	while(p!=null||!stack.isEmpty()){
    		while(p!=null){//先处理左子树
    			stack.push(p);
    			res.add(p.val);
    			p=p.left;
    		}
    	    p=stack.pop();
    		//处理右子树
    		p=p.right;
    	}
    	return res;
    }
     

     


    分析
    层次遍历即宽度优先遍历,用栈来记录访问路径。
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    	List<List<Integer>> levels=new LinkedList<List<Integer>>();
    	if(root==null) return levels;
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	queue.add(root);
    	int mark=0;
    	while(!queue.isEmpty()){
    		List<Integer> list=new ArrayList<Integer>();
    		Queue<TreeNode> nextqueue=new LinkedList<TreeNode>();
    		while(!queue.isEmpty()){
    			TreeNode node=queue.poll();
    			list.add(node.val);
    			if(node.left!=null)nextqueue.add(node.left);
    			if(node.right!=null)nextqueue.add(node.right);
    		} 
    		queue=nextqueue;
    		if(mark==1)
    			Collections.reverse(list);
    		mark=(mark+1)%2;
    		levels.add(list);
    	}
    	return levels;
    }

    分析
    经典的利用栈进行表达式计算。
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<Integer>();
        for(String token:tokens){
        	if(token.equalsIgnoreCase("+")){
        		Integer second=stack.pop();
        		Integer first=stack.pop();
        		stack.push(first+second);
        	}else if(token.equalsIgnoreCase("-")){
        		Integer second=stack.pop();
        		Integer first=stack.pop();
        		stack.push(first-second);
        	}else if(token.equalsIgnoreCase("*")){
        		Integer second=stack.pop();
        		Integer first=stack.pop();
        		stack.push(first*second);
        	}else if(token.equalsIgnoreCase("/")){
        		Integer second=stack.pop();
        		Integer first=stack.pop();
        		stack.push(first/second);
        	}else{
        		stack.push(Integer.parseInt(token));
        	}
        }
        return stack.pop();
    }

    分析
    利用二分查找树中序遍历递增的特性,用栈记录遍历路径。
    public class BSTIterator {
    	private Stack<TreeNode> stack;
    	private TreeNode p;
        public BSTIterator(TreeNode root) {
            p=root;
            stack=new Stack<TreeNode>();
        }
     
        public boolean hasNext() {
    		return !(p==null&&stack.isEmpty());
        }
        
        public int next() {
        	while(p!=null){
        		stack.push(p);
        		p=p.left;
        	}
        	TreeNode top=stack.pop();
        	p=top.right;
    		return top.val;
        }
    }

     
     
    分析
    后续遍历同样是利用栈来记录访问路径。注:但是由于是左右中的遍历顺序,当某个根元素存在右子树时,该根元素会两次出现在栈顶,但是只有第二次出现在栈顶的时候才能出栈,因此我们需要利用哈希表标记根元素出现在栈顶的次数。
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> res=new LinkedList<Integer>();
    	Stack<TreeNode> stack=new Stack<TreeNode>();
    	Map<TreeNode,Integer> mark=new HashMap<TreeNode,Integer>();
    	TreeNode p=root;
    	while(p!=null||!stack.isEmpty()){
    		while(p!=null){
    			stack.push(p);
    			p=p.left;
    		}
    		p=stack.peek();
    		if(p.right==null){
    			res.add(p.val);
    			stack.pop();
    			p=null;
    		}else{//有右子树
    			if(mark.get(p)==null){
    				mark.put(p, 1);
    				p=p.right;
    			}else{
    				res.add(p.val);
    				stack.pop();
    				mark.remove(p);
    				p=null;
    			}
    		}
    		
    	}
    	return res;
    }

    分析
    对于表达式的计算(中序表达式),我们可以先将其转换成后序表达式,然后再对其进行计算。
    public int calculate(String s) {
        if(s == null)
            return 0;
        s = reform(s);
        int result = 0, num = 0, base = 1;
        for(char c: s.toCharArray())
            switch(c){
            case '+': result += num; num = 0; base = 1; break;
            case '-': result -= num; num = 0; base = 1; break;
            default: num += (c - '0') * base; base *= 10;
            }
        return result;
    }
    
    private String reform(String s) {
        StringBuilder sb = new StringBuilder();
        Stack<Boolean> stack = new Stack<>();
        stack.push(true);
        boolean add = true;
        for(char c: s.toCharArray())
            switch(c){
            case ' ': break;
            case '(': stack.push(add); break;
            case ')': stack.pop(); break;
            case '+': 
                add = stack.peek(); 
                sb.append(stack.peek() ? '+' : '-'); 
                break;
            case '-': 
                add = !stack.peek(); 
                sb.append(stack.peek() ? '-' : '+'); 
                break;
            default: sb.append(c);
            }
        if(sb.charAt(0) != '+' || sb.charAt(0) != '-')
            sb.insert(0, '+');
        return sb.reverse().toString();
    }

     
    分析
    利用序列化后的字符串重构树,用栈记录路径。如果重构过程失败返回false。
    public boolean isValidSerialization(String preorder) {
    	Stack<String> stack=new Stack<String>();
    	if(preorder.equals("")) return false;
    	String[] values = preorder.split(",");
    	System.out.println(values.length);
    	if(values[0].equals("#")&&values.length==1) return true;
    	if(values[0].equals("#")) return false;
    	stack.push(values[0]);
    	int mark=0;
    	for(int i=1;i<values.length;i++){
    		if(stack.isEmpty())
    			return false;
    		String p=stack.peek();
    		if(mark==0){//左子树
    			if(values[i].equals("#")){ 
    				mark=(mark+1)%2;//左子树为空,转成处理右子树
    			}else{ 
    				stack.push(values[i]);//继续处理左子树的左子树
    			}
    		}else{//右子树
    			if(values[i].equals("#")){ 
    				stack.pop();//继续处理根元素的右子树
    			}else{
    				stack.push(values[i]);
    			}
    		}
    	}
    	if(!stack.isEmpty())
    		return false;
    	else
    		return true;
    }

     
     
     
     
     
    展开全文
  • 消息队列面试题及答案

    万次阅读 多人点赞 2019-11-27 15:48:36
    1、为什么使用消息队列? 消息队列使用的场景和中间件有很多,但解决的核心问题主要是:异步、解耦、消峰填谷。 2、消息队列的优缺点 异步、解耦、消峰填谷这是消息队列最大的优点,除了这些消息队列还可以会解决...
  • 栈和队列面试题总结

    2018-08-13 20:46:54
    栈的基础操作 https://blog.csdn.net/hansionz/article/details/81636557 ...队列的基础操作 ... 栈和队列面试题(c语言实现) 1.实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间复杂度为O(1)....
  • 两个栈实现一个队列—–队列面试题2 使用两个队列实现一个栈比其他的孪生问题来说,能复杂一些 思路 设置一个队列为 queue1, 另一个为 queue2 入栈时,将元素入队列非空队列 出栈时,将非空队列的前 n-1 个...
  • 事件队列面试题

    2018-09-23 21:45:20
    一道面试题就可以测出你是否真正理解异步了,快来试试吧!
  • 1.队列相关问题 1.1 说说你对队列的理解? 答:对队列的理解: 首先队列本身也是个容器,底层也会有不同的数据结构,比如 LinkedBlockingQueue 是底层是链表结构,所以可以维持先入先出的顺序,比如 DelayQueue ...
  • 多线程阻塞队列面试题

    千次阅读 2017-01-09 20:24:18
    1.创建四个线程,打印16个日志对象,使用队列的方式。public class Test { public static void main(String[] args) { BlockingQueue<String> queue=new ArrayBlockingQueue(16); for(int i=0;i;i++){
  •  在之前我曾经实现了两个栈实现一个队列面试题,其实思路也很简单就是充分利用栈的特性-后进先出,将输入的数据先输入栈1,将该栈1再输出到栈2,最后将栈2的数据输出,利用这个交换的特性实现两个栈实现一个队列....
  • 常见栈、队列面试题

    千次阅读 2012-06-06 23:39:57
    栈和队列一般不会在面试题里面单独做为一整个题出现,往往都是作为一种辅助的数据结构,利用栈和队列的性质去解决某一类题目。 栈Stack的特点,先进后出,LIFO。栈的基本操作:push压栈,pop出栈,peek返回栈顶...
  • 一些常见的消息队列面试题整理

    千次阅读 2019-03-29 10:24:52
    或者就一个 queue 但是对应一个 consumer,然后这个 consumer 内部用内存队列做排队,然后分发给底层不同的 worker 来处理。 Kafka 一个 topic,一个 partition,一个 consumer,内部单线程消费,单线程...
  • 1.判断出入栈的合法性 ... 2.使用两个栈实现一个队列 思想:1.栈1中的所有数据弹到栈2...  2.再从栈2弹出所有数据,则可出现队列的效果 ...(默认压数据压到队列1中,从队列2出数据) typedef struct Stack { DataT...
  • 栈和队列面试题(三)

    千次阅读 2016-08-24 14:59:03
    4.元素出栈入栈的合法性,如入栈的序列(1,2,3,4,5),出栈的序列为(4,5,3,2,1). 思想:先入栈一个元素,将出栈序列的第一个元素和该栈的栈顶元素比较,如果相同,那就让该元素出栈且出栈序列往后走一个...
  • [整理III]微软等100题系列V0.1版之三:栈、堆、队列面试题集锦July==============2.设计包含min函数的栈。定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是...
  • //实现方案二 #include<stack> typedef int T; class StackWithMin { public: StackWithMin() {} ~StackWithMin() {} void Push(T x) { s1.push(x); if (s2.empty() || x <= s2.top()) ...}
  • 一:queue是一种”先进先出”的数据结构,他在对尾插入元素,在队头删除元素,他既可以取到自己的队头... 所以用两个队列实现一个栈,就是用队列”先进先出“的原则实现栈“先进后出”特点: 所以只要实现栈的插入,
  • #include<iostream> #include<stack> using namespace std; template<class T> class MinStack { public: MinStack(){} void Push(const T& x) { s1.push(x); if (min.empty() || x <...
  • struct Elem { T minData; T data; };
  • 最新Java面试题,常见面试题及答案汇总

    万次阅读 多人点赞 2019-07-12 08:56:55
    Java最新面试题面试题答案汇总
  • 数据结构—栈和队列经典面试题

    千次阅读 2018-09-21 17:38:22
    栈和队列面试题: 实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1) 使用两个栈实现一个队列 使用两个队列实现一个栈 元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),...
  • 【消息队列面试题及答案整理

    千次阅读 2021-02-24 13:48:31
    消息队列面试题为什么要使用消息队列/消息队列的应用场景使用了消息队列会有什么缺点如何保证消息队列是高可用的RocketMQ是如何保证消息队列是高可用的如何保证消息不被重复消费/如何保证消息消费的幂等性如何保证...
  • RabbitMQ消息队列常见面试题总结

    千次阅读 2021-03-22 02:46:39
    RabbitMQ消息队列常见面试题总结; 1、什么是消息队列?消息队列的优缺点? 2、Kafka、ActiveMQ、RabbitMQ、RocketMQ的区别? 3、如何保证消息不被重复消费? 4、如何保证消息不丢失,进行可靠性传输? 5、如何保证...
  • 面试题:消息队列面试连环炮

    万次阅读 2019-11-02 23:15:58
    目录:你使用过消息中间件吗?你们为什么使用消息中间件?消息队列有什么好处?什么场景下使用的?用来干了个什么的事情?系统中引入消息队列之后会不会有什么坏处?你们使用哪一个消息中间件?为什么...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 91,820
精华内容 36,728
关键字:

队列面试题