开发者社区> 磊哥聊Java> 正文

如何手撸一个队列?队列详解和面试题汇总(含答案)(上)

简介: 如何手撸一个队列?队列详解和面试题汇总(含答案)(上)
+关注继续查看

队列(Queue):


与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。Queue 类关系图,如下图所示:


微信图片_20220117183843.png


注:为了让读者更直观地理解,上图为精简版的 Queue 类关系图。本文如无特殊说明,内容都是基于 Java 1.8 版本。 


队列(Queue)


1)Queue 分类


从上图可以看出 Queue 大体可分为以下三类。


  1. 双端队列:双端队列(Deque)是 Queue 的子类也是 Queue 的补充类,头部和尾部都支持元素插入和获取。


  1. 阻塞队列:阻塞队列指的是在元素操作时(添加或删除),如果没有成功,会阻塞等待执行。例如,当添加元素时,如果队列元素已满,队列会阻塞等待直到有空位时再插入。


  1. 非阻塞队列:非阻塞队列和阻塞队列相反,会直接返回操作的结果,而非阻塞等待。双端队列也属于非阻塞队列。


2)Queue 方法说明


Queue 常用方法,如下图所示:


微信图片_20220117183846.png


方法说明:


  • add(E):添加元素到队列尾部,成功返回 true,队列超出时抛出异常;
  • offer(E):添加元素到队列尾部,成功返回 true,队列超出时返回 false;
  • remove():删除元素,成功返回 true,失败返回 false;
  • poll():获取并移除此队列的第一个元素,若队列为空,则返回 null;
  • peek():获取但不移除此队列的第一个元素,若队列为空,则返回 null;
  • element():获取但不移除此队列的第一个元素,若队列为空,则抛异常。


3)Queue 使用实例


Queue<String> linkedList = new LinkedList<>();
linkedList.add("Dog");
linkedList.add("Camel");
linkedList.add("Cat");
while (!linkedList.isEmpty()) {
    System.out.println(linkedList.poll());
}


程序执行结果:


Dog Camel Cat


阻塞队列


1)BlockingQueue


BlockingQueue 在 java.util.concurrent 包下,其他阻塞类都实现自 BlockingQueue 接口,BlockingQueue 提供了线程安全的队列访问方式,当向队列中插入数据时,如果队列已满,线程则会阻塞等待队列中元素被取出后再插入;


当从队列中取数据时,如果队列为空,则线程会阻塞等待队列中有新元素再获取。


BlockingQueue 核心方法插入方法:


  • add(E):添加元素到队列尾部,成功返回 true,队列超出时抛出异常;
  • offer(E):添加元素到队列尾部,成功返回 true,队列超出时返回 false ;
  • put(E):将元素插入到队列的尾部,如果该队列已满,则一直阻塞。


删除方法:


  • remove(Object):移除指定元素,成功返回 true,失败返回 false;
  • poll(): 获取并移除队列的第一个元素,如果队列为空,则返回 null;
  • take():获取并移除队列第一个元素,如果没有元素则一直阻塞。


检查方法:


  • peek():获取但不移除队列的第一个元素,若队列为空,则返回 null。


2)LinkedBlockingQueue


LinkedBlockingQueue 是一个由链表实现的有界阻塞队列,容量默认值为 Integer.MAX_VALUE,也可以自定义容量,建议指定容量大小,默认大小在添加速度大于删除速度情况下有造成内存溢出的风险,LinkedBlockingQueue 是先进先出的方式存储元素。


3)ArrayBlockingQueue


ArrayBlockingQueue 是一个有边界的阻塞队列,它的内部实现是一个数组。它的容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变。


ArrayBlockingQueue 也是先进先出的方式存储数据,ArrayBlockingQueue 内部的阻塞队列是通过重入锁 ReenterLock 和 Condition 条件队列实现的,因此 ArrayBlockingQueue 中的元素存在公平访问与非公平访问的区别,对于公平访问队列,被阻塞的线程可以按照阻塞的先后顺序访问队列,即先阻塞的线程先访问队列。


而非公平队列,当队列可用时,阻塞的线程将进入争夺访问资源的竞争中,也就是说谁先抢到谁就执行,没有固定的先后顺序。示例代码如下:


// 默认非公平阻塞队列
ArrayBlockingQueue queue = new ArrayBlockingQueue(6);
// 公平阻塞队列
ArrayBlockingQueue queue2 = new ArrayBlockingQueue(6,true);
// ArrayBlockingQueue 源码展示
public ArrayBlockingQueue(int capacity) {
    this(capacity, false);
}
public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}


4)DelayQueue


DelayQueue 是一个支持延时获取元素的无界阻塞队列,队列中的元素必须实现 Delayed 接口,在创建元素时可以指定延迟时间,只有到达了延迟的时间之后,才能获取到该元素。实现了 Delayed 接口必须重写两个方法 ,getDelay(TimeUnit) 和 compareTo(Delayed),如下代码所示:


class DelayElement implements Delayed {
        @Override
        // 获取剩余时间
        public long getDelay(TimeUnit unit) {
            // do something
        }
        @Override
        // 队列里元素的排序依据
        public int compareTo(Delayed o) {
            // do something
        }
    }


DelayQueue 使用的完整示例,请参考以下代码:


public class DelayTest {
    public static void main(String[] args) throws InterruptedException {
        DelayQueue delayQueue = new DelayQueue();
        delayQueue.put(new DelayElement(1000));
        delayQueue.put(new DelayElement(3000));
        delayQueue.put(new DelayElement(5000));
        System.out.println("开始时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
        while (!delayQueue.isEmpty()){
            System.out.println(delayQueue.take());
        }
        System.out.println("结束时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
    }
    static class DelayElement implements Delayed {
        // 延迟截止时间(单面:毫秒)
        long delayTime = System.currentTimeMillis();
        public DelayElement(long delayTime) {
            this.delayTime = (this.delayTime + delayTime);
        }
        @Override
        // 获取剩余时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列里元素的排序依据
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
                return 1;
            } else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
                return -1;
            } else {
                return 0;
            }
        }
        @Override
        public String toString() {
            return DateFormat.getDateTimeInstance().format(new Date(delayTime));
        }
    }
}


程序执行结果:


开始时间:2019-6-13 20:40:38 2019-6-13 20:40:39 2019-6-13 20:40:41 2019-6-13 20:40:43 结束时间:2019-6-13 20:40:43

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
9433 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
13023 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
20090 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
13715 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
33100 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
18380 0
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
34896 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
18848 0
+关注
磊哥聊Java
是非审之于己,毁誉听之于人,得失安之于数。欢迎关注我的公众号「Java中文社群」
760
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载