并发编程-Java jdk中队列Queue的详解与应用

一、什么是队列，队列有什么用？

假设春运火车站只有一个售票窗口，但是买火车票的人非常多，如果大家一哄而上到窗口进行买票，估计售票员会发疯，因此聪明的人类发明了排队这种游戏规则，则先到先得的机制，在不断的发展过程中，排队的规则也慢慢完善，比如有些例外比如军人优先或者老弱病残优先则可以进行插队，通过这样的规则可以让面对人流高峰也可以平稳进行工作。

这个规则运用到实际开发中也是如此，在程序中队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在队列的前端进行删除操作，而在队列的后端进行插入操作。但是java的某些队列运行在任何地方插入删除（如军人插队）

在java中根据队列特性，队列可分为阻塞队列和非阻塞队列，有界队列和无界队列、单向链表队列和双向链表队列之分,

二、阻塞/非阻塞队列

2.1 阻塞队列

入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超过队列总数时，就会解除阻塞状态，进而可以继续入列；

出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而继续出列；

阻塞队列优点 ：阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况,只要是阻塞队列，都是线程安全的；

实现类

• DelayQueue：一个支持延时获取元素的无界阻塞队列
• LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
• ArrayBlockingQueue：有界队列，阻塞式,初始化时必须指定队列大小，且不可改变；，底层由数组实现；
• SynchronousQueue：最多只能存储一个元素，每一个put操作必须等待一个take操作，否则不能继续添加元素
• PriorityBlockingQueue：一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，而且它也是无界的，也就是没有容量上限，虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError 错误；

2.2 非阻塞队列

不管出列还是入列，都不会进行阻塞，入列时，如果元素数量超过队列总数，则会抛出异常，出列时，如果队列为空，则取出空值；

一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法：

• 出队阻塞方法 ： take()
• 入队阻塞方法 ： put()

实现类

• ConcurrentLinkedQueue：单向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全，内部基于节点实现
• ConcurrentLinkedDeque：双向链表结构的无界并发队列, 非阻塞队列，由CAS实现线程安全
• PriorityQueue: 内部基于数组实现，线程不安全的队列

三、有界/无界队列

有界和无界

• 有界：有界限，大小长度受限制
• 无界：无限大小，其实说是无限大小，其实是有界限的，只不过超过界限时就会进行扩容，就想ArrayList 一样，在内部动态扩容，最大值为Integer.MAX_VALUE

四、单向/双向链表队列

4.1 单向链表

每个元素中除了元素本身之外，还存储一个指针，这个指针指向下一个元素；

4.2 双向链表

除了元素本身之外，还有两个指针，一个指针指向前一个元素的地址，另一个指针指向后一个元素的地址；

四、 Java中队列的继承关系

五、队列常用方法

队列常用方法

PS知识点： remove、element、offer 、poll、peek 属于Queue接口的定义。

六、代码示例

假设现在需要售卖一趟车票共100张，并且有3个窗口开放售票，当有大量人购买时如何保障出票安全，我们使用ArrayBlockingQueue阻塞式有界队列来模拟常见代码。

package com.queue;

import cn.hutool.core.util.StrUtil;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class BlockingQueueTest {
    //售票员窗口
    static final int SALESPERSON=3;
    //总票数100张
    static AtomicInteger ticketTotal=new AtomicInteger(100);
    //假设大厅总排队人数最大可排1000人
    static final int MAX_COUNT=1000;

    public static void main(String[] args) {
        // 阻塞-有界队列
        BlockingQueue<String> queue=new ArrayBlockingQueue<String>(MAX_COUNT);
        for (int i = 0; i < SALESPERSON; i++) {
            //模拟启动三个工作窗口工作排队
            new Thread(new Producer(queue)).start();
            //模拟启动三个工作窗口出票
            new Thread(new Consumer(queue)).start();
        }
    }

    /**
     * 模拟系统排队出票
     */
    static class  Consumer extends Thread{
        BlockingQueue<String> queue;
        public Consumer(BlockingQueue<String> queue) {
            this.queue = queue;
        }
        @Override
        public void run() {
            while (true){
                try {
                    if(ticketTotal.get()==0){
                        System.out.println("结束售票啦，收工下班");
                        return;
                    }
                    System.out.println(StrUtil.format("{},出票号：{}，大厅排队总人数：{}",queue.take(),ticketTotal.getAndDecrement(),queue.size()));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    /**
     * 模拟窗口并发出票发起请求
     */
    static class  Producer implements Runnable{
        BlockingQueue<String> queue;
        public Producer(BlockingQueue<String> queue) {
            this.queue = queue;
        }
        @Override
        public void run() {
           while (true){
               try {
                   queue.put(StrUtil.format("出票窗口{}号,购票请求：{}",Thread.currentThread().getId(),ticketTotal.get()));
               } catch (InterruptedException e) {
                   e.printStackTrace();
               }
           }
        }
    }
}

通过上述代码运行，我看可以看出，当26，23，20同时请求同一个100票号时，系统也可以再多线程下正常出票，有效解决并发和出错票等问题

出票窗口26号,购票请求：100,出票号：100，大厅排队总人数：7
出票窗口23号,购票请求：100,出票号：98，大厅排队总人数：6
出票窗口23号,购票请求：100,出票号：97，大厅排队总人数：217
出票窗口20号,购票请求：100,出票号：99，大厅排队总人数：8
出票窗口23号,购票请求：100,出票号：96，大厅排队总人数：226
出票窗口23号,购票请求：100,出票号：94，大厅排队总人数：237
出票窗口20号,购票请求：100,出票号：95，大厅排队总人数：227
出票窗口26号,购票请求：100,出票号：92，大厅排队总人数：264
出票窗口20号,购票请求：100,出票号：93，大厅排队总人数：246
出票窗口20号,购票请求：100,出票号：90，大厅排队总人数：274
出票窗口23号,购票请求：100,出票号：91，大厅排队总人数：267
出票窗口20号,购票请求：97,出票号：88，大厅排队总人数：292
出票窗口20号,购票请求：97,出票号：89，大厅排队总人数：284
出票窗口20号,购票请求：97,出票号：86，大厅排队总人数：327
出票窗口26号,购票请求：98,出票号：87，大厅排队总人数：298
出票窗口23号,购票请求：97,出票号：85，大厅排队总人数：341
出票窗口20号,购票请求：97,出票号：83，大厅排队总人数：339
出票窗口20号,购票请求：97,出票号：84，大厅排队总人数：340
出票窗口26号,购票请求：97,出票号：81，大厅排队总人数：352
出票窗口23号,购票请求：97,出票号：82，大厅排队总人数：345
出票窗口23号,购票请求：97,出票号：79，大厅排队总人数：362
出票窗口20号,购票请求：97,出票号：80，大厅排队总人数：360
出票窗口20号,购票请求：97,出票号：77，大厅排队总人数：366
出票窗口26号,购票请求：97,出票号：78，大厅排队总人数：366
出票窗口26号,购票请求：97,出票号：75，大厅排队总人数：380
出票窗口20号,购票请求：97,出票号：76，大厅排队总人数：370
出票窗口20号,购票请求：97,出票号：73，大厅排队总人数：403
出票窗口23号,购票请求：97,出票号：74，大厅排队总人数：391
出票窗口20号,购票请求：97,出票号：72，大厅排队总人数：408
出票窗口23号,购票请求：97,出票号：70，大厅排队总人数：406
出票窗口26号,购票请求：97,出票号：71，大厅排队总人数：407
出票窗口20号,购票请求：97,出票号：69，大厅排队总人数：420
出票窗口20号,购票请求：97,出票号：68，大厅排队总人数：422
出票窗口20号,购票请求：97,出票号：66，大厅排队总人数：433
出票窗口26号,购票请求：97,出票号：65，大厅排队总人数：439
出票窗口23号,购票请求：97,出票号：67，大厅排队总人数：429
出票窗口23号,购票请求：97,出票号：63，大厅排队总人数：442
出票窗口20号,购票请求：97,出票号：64，大厅排队总人数：442
出票窗口26号,购票请求：97,出票号：61，大厅排队总人数：457
出票窗口20号,购票请求：97,出票号：62，大厅排队总人数：447
出票窗口23号,购票请求：97,出票号：59，大厅排队总人数：470
出票窗口20号,购票请求：97,出票号：60，大厅排队总人数：469
出票窗口26号,购票请求：97,出票号：57，大厅排队总人数：489
出票窗口20号,购票请求：97,出票号：58，大厅排队总人数：481
出票窗口23号,购票请求：97,出票号：55，大厅排队总人数：509
出票窗口20号,购票请求：97,出票号：56，大厅排队总人数：494
出票窗口23号,购票请求：97,出票号：53，大厅排队总人数：541
出票窗口26号,购票请求：97,出票号：52，大厅排队总人数：547
出票窗口26号,购票请求：97,出票号：54，大厅排队总人数：522
出票窗口26号,购票请求：97,出票号：50，大厅排队总人数：568
出票窗口23号,购票请求：97,出票号：51，大厅排队总人数：557
出票窗口23号,购票请求：97,出票号：49，大厅排队总人数：587
出票窗口23号,购票请求：97,出票号：47，大厅排队总人数：602
出票窗口26号,购票请求：97,出票号：48，大厅排队总人数：596
出票窗口23号,购票请求：97,出票号：45，大厅排队总人数：631
出票窗口26号,购票请求：97,出票号：46，大厅排队总人数：613
出票窗口23号,购票请求：97,出票号：43，大厅排队总人数：656
出票窗口26号,购票请求：97,出票号：44，大厅排队总人数：649
出票窗口23号,购票请求：97,出票号：41，大厅排队总人数：705
出票窗口26号,购票请求：97,出票号：42，大厅排队总人数：679
出票窗口23号,购票请求：97,出票号：39，大厅排队总人数：725
出票窗口26号,购票请求：97,出票号：40，大厅排队总人数：716
出票窗口26号,购票请求：97,出票号：37，大厅排队总人数：756
出票窗口26号,购票请求：97,出票号：38，大厅排队总人数：740
出票窗口26号,购票请求：97,出票号：35，大厅排队总人数：797
出票窗口23号,购票请求：97,出票号：36，大厅排队总人数：771
出票窗口23号,购票请求：97,出票号：33，大厅排队总人数：850
出票窗口26号,购票请求：97,出票号：34，大厅排队总人数：832
出票窗口26号,购票请求：97,出票号：31，大厅排队总人数：887
出票窗口26号,购票请求：97,出票号：32，大厅排队总人数：867
出票窗口26号,购票请求：97,出票号：29，大厅排队总人数：913
出票窗口23号,购票请求：97,出票号：30，大厅排队总人数：898
出票窗口23号,购票请求：97,出票号：27，大厅排队总人数：939
出票窗口26号,购票请求：97,出票号：28，大厅排队总人数：924
出票窗口26号,购票请求：97,出票号：26，大厅排队总人数：953
出票窗口26号,购票请求：97,出票号：25，大厅排队总人数：953
出票窗口26号,购票请求：97,出票号：22，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：23，大厅排队总人数：998
出票窗口23号,购票请求：97,出票号：24，大厅排队总人数：972
出票窗口23号,购票请求：97,出票号：20，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：21，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：18，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：19，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：16，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：17，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：14，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：15，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：12，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：13，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：10，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：9，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：11，大厅排队总人数：999
出票窗口26号,购票请求：97,出票号：7，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：8，大厅排队总人数：1000
出票窗口26号,购票请求：97,出票号：5，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：6，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：3，大厅排队总人数：999
出票窗口23号,购票请求：97,出票号：4，大厅排队总人数：999
结束售票啦，收工下班
出票窗口23号,购票请求：97,出票号：1，大厅排队总人数：999
结束售票啦，收工下班
出票窗口26号,购票请求：97,出票号：2，大厅排队总人数：999
结束售票啦，收工下班