【Java技术】盘点 Java 中的队列

队列是一种重要的数据结构,Java 语言提供了队列的支持,内置了多种类型的队列供我们使用。限于篇幅,本文不会讨论太多细节。

队列数据结构

队列是一个先进先出的抽象数据结构,可类比于生活中的排队场景。通常情况下,队列有数组和链表两种实现方式。

采用链表实现的队列,没有个数限制。插入元素时直接接在链表的尾部,取出元素时直接从链表的头部取出即可。

采用数组实现的队列,通常是循环数组,受限于数组的大小,存在天然的个数上限。插入和取出元素时,必须采用队列头部指针和队列尾部指针进行队列满和队列空的判断。

Java 队列定义

Java 定义了队列的基本操作,接口类型为 java.util.Queue,接口定义如下所示。Queue 定义了两套队列操作方法:

  • add、remove、element 操作失败抛出异常;

  • offer 操作失败返回 false 或抛出异常,poll、peek 操作失败返回 null;


  • public interface Queue<E> extends Collection<E> {
        //插入元素,成功返回true,失败抛出异常
        boolean add(E e);
    
        //插入元素,成功返回true,失败返回false或抛出异常 
        boolean offer(E e);
    
        //取出并移除头部元素,空队列抛出异常 
        E remove();
    
        //取出并移除头部元素,空队列返回null 
        E poll();
    
        //取出但不移除头部元素,空队列抛出异常 
        E element();
    
        //取出但不移除头部元素,空队列返回null 
        E peek();
    }


    Queue 作为先进先出队列,只能从头部取元素、插入元素到尾部。Java 同样定义了双向队列 Deque,可以同时在头部、尾部插入和取出元素,接口定义如下所示。Deque 也同样定义了两套队列操作方法,针对头部操作方法为 xxxFirst、针对尾部操作方法为 xxxLast:

  • add、remove、get 操作失败抛出异常;

  • offer 操作失败返回 false 或抛出异常,poll、peek 操作失败返回 null;

  • Deque 另外还有 removeFirstOccurrence、removeLastOccurrence 方法用于删除指定元素,元素存在则删除,不存在则队列不变。


    public interface Deque<E> extends Queue<E> {
        //插入元素到队列头部,失败抛出异常 
        void addFirst(E e);
    
        //插入元素到队列尾部,失败抛出异常  
        void addLast(E e);
    
        //插入元素到队列头部,失败返回false或抛出异常 
        boolean offerFirst(E e);
    
        //插入元素到队列尾部,失败返回false抛出异常  
        boolean offerLast(E e);
    
        //取出并移除头部元素,空队列抛出异常 
        E removeFirst();
    
        //取出并移除尾部元素,空队列抛出异常 
        E removeLast();
    
        //取出并移除头部元素,空队列返回null
        E pollFirst();
    
        //取出并移除尾部元素,空队列返回null
        E pollLast();
    
        //取出但不移除头部元素,空队列抛出异常
        E getFirst();
    
        //取出但不移除尾部元素,空队列抛出异常
        E getLast();
    
        //取出但不移除头部元素,空队列返回null
        E peekFirst();
    
        //取出但不移除尾部元素,空队列返回null
        E peekLast();
    
        //移除指定头部元素,若不存在队列不变,移除成功返回true 
        boolean removeFirstOccurrence(Object o);
    
        //移除指定尾部元素,若不存在队列不变,移除成功返回true 
        boolean removeLastOccurrence(Object o);
    
        //单向队列方法,参考Queue   
        //栈方法,参考栈
        //集合方法,参考集合定义   
    }


    Java 并发工具包中定义了阻塞队列 BlockingQueue 和 BlockingDueue。阻塞队列在前面的队列定义基础上增加了以下几个方法,来支持阻塞操作。

  • take:取出并移除元素,如队列为空则一直阻塞直到有元素;

  • put:插入元素,如队列满则一直阻塞直到有空位可以插入元素;

  • 可超时的offer:插入元素并指定超时时间,如队列满等待指定的时间;

  • 可超时的poll:取出并移除元素,如队列空等待指定的时间。

  • Java 中的 Queue 实现

    Java 中的队列实现,基本上都继承了 AbstractQueue 类。AbstractQueue 抽象队列实现了 add、remove、element 方法,这些方法调用 offer、poll、peek 方法并在失败时抛出异常,此外还提供了清空队列的 clear 方法和批量插入元素的 addAll 方法。

    非阻塞队列访问队列元素时可以立即返回,主要有优先级队列 PriorityQueue、并发队列 ConcurrentLinkedQueue。

    PriorityQueue 是一个无界优先级队列,基于一个优先级堆实现。队列中的元素按照自然排序先后排列,或者使用创建时提供的 Comparator 比较先后顺序。优先级队列需要比较顺序,因此不能包含 null 元素。使用自然顺序排序时,元素必须是可以比较大小的,否则会导致类型转换异常。优先级队列的头部元素是队列中按照顺序最靠前的元素,如有多个元素排序相等则随机选择一个。

    ConcurrentLinkedQueue 是一个基于链表实现的线程安全的无界队列。内部元素按先进先出的顺序排序,最后插入的元素位于队列尾部。ConcurrentLinkedQueue 不允许插入 null。当有多个线程同时访问队列时,此队列是一个比较合适的选择。

    Queue 接口的子接口 BlockingQueue 定义了阻塞队列。阻塞队列访问队列元素时,可能会一直阻塞直到操作完成,比如从空队列中取元素、向满队列中插入元素等,主要有延时队列、同步队列、链表阻塞队列、数组阻塞队列、优先级阻塞队列。

    DelayQueue 是一个无界延时队列,元素只有在延时时间已经过期的情况下才能被访问。头部元素是队列中延时时间过期最久的元素。如果没有元素过期则没有头部元素,取元素的方法会返回 null。当元素过期时,调用元素的 getDelay 方法会返回 0 或 负数。未过期的元素不能被取出,但是统计队列大小时仍然包含未过期元素。

    SynchronousQueue 是一个同步队列。同步队列与其他阻塞队列不太一样,插入元素时会一直阻塞直到有另一个线程取元素,取元素同样会一直阻塞直到有另一个线程插入元素。同步队列本身没有容量的概念,也不保持元素,可以理解为两个线程交换数据的媒介,因此也不能执行 size、peek 类型的操作。

    LinkedBlockingQueue 是一个基于链表实现的有界的阻塞队列。如未指定队列大小,默认为Integer.MAX_VALUE。内部元素按先进先出的顺序排序,最后插入的元素位于队列尾部。

    ArrayBlockingQueue 是一个基于数组实现的有界的阻塞队列。一旦创建队列的大小不会再发生变化,是一个典型的有界队列。内部元素按先进先出的顺序排序,最后插入的元素位于队列尾部。

    PriorityBlockingQueue 是一个无界优先级阻塞队列。这个队列与 PriorityQueue 类似,但当队列空或满时会阻塞相关操作。

    阻塞队列经常存在生产者等待消费者消费元素的情况,BlockingQueue 的子接口 TransferQueue 定义了一种新队列来支持这种情况,实现类为 LinkedTransferQueue。TransferQueue 允许生产者调用 transfer 方法来等待消费者调用 take 或 poll 消费元素,如果有消费者正在取元素则直接交给消费者,否则便把元素插入队列尾部并阻塞生产者当前线程直到元素被消费者取走。

    Java 中的 Deque 实现

    Deque 接口的实现相对较少,主要有 LinkedList、ArrayDeque、ConcurrentLinkedDeque 和 LinkedBlockingDeque。

    LinkedList 就是我们常用的链表,实现了 Deque 接口。LinkedList 为了提高性能,本身支持从链表两端插入和取出元素,与 Deque 的要求恰好一致。

    ArrayDeque 是一个基于数组的双向队列,大小可变。ArrayDeque 是非线程安全的,在多线程并发时需要外部调用者自行处理并发。

    ConcurrentLinkedDeque 是一个基于链表实现的线程安全的无界双向队列。内部元素按先进先出的顺序排序,最后插入的元素位于队列尾部,不允许插入 null。当有多个线程同时访问双向队列时,此队列是一个比较合适的选择。

    Deque 接口有一个子接口 BlockingDeque 定义了阻塞双向队列。实现类为 LinkedBlockingDeque,是一个基于链表实现的有界的阻塞双向队列。如未指定队列大小,默认为Integer.MAX_VALUE。内部元素按先进先出的顺序排序,最后插入的元素位于队列尾部。

    Java 中的队列就讨论到这里,欢迎留言留下您的观点和看法。

    分享学习笔记和技术总结,内容涉及 Java 技术、软件架构、前沿技术、开源框架、数据结构与算法、编程感悟等多个领域,欢迎关注。本文首发于微信公众号“后端开发那点事儿” 。

    ©著作权归作者所有,转载或内容合作请联系作者
    • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
      沈念sama阅读 203,772评论 6 477
    • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
      沈念sama阅读 85,458评论 2 381
    • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
      开封第一讲书人阅读 150,610评论 0 337
    • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
      开封第一讲书人阅读 54,640评论 1 276
    • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
      茶点故事阅读 63,657评论 5 365
    • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
      开封第一讲书人阅读 48,590评论 1 281
    • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
      沈念sama阅读 37,962评论 3 395
    • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
      开封第一讲书人阅读 36,631评论 0 258
    • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
      沈念sama阅读 40,870评论 1 297
    • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
      茶点故事阅读 35,611评论 2 321
    • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
      茶点故事阅读 37,704评论 1 329
    • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
      沈念sama阅读 33,386评论 4 319
    • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
      茶点故事阅读 38,969评论 3 307
    • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
      开封第一讲书人阅读 29,944评论 0 19
    • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
      开封第一讲书人阅读 31,179评论 1 260
    • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
      沈念sama阅读 44,742评论 2 349
    • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
      茶点故事阅读 42,440评论 2 342

    推荐阅读更多精彩内容