4，Java集合队列

4.1，Queue队列机制

• 队列是一种先进先出的数据结构，队列中插入元素和删除元素分别位于队列的两端。

• 队列：先进先出；队头删除，队尾插入。

  • 属性：队头指针front，队尾指针rear。
  • 方法：入列enQueue，出列deQueue，判断是否为空isEmpty，判断是否已满isFull，清空makeEmpty，返回元素个数size。

• 
  todo img1

• Java中的Queue的实现有三种方式：

  1. 阻塞队列
     • 阻塞队列是一个可以阻塞的先进先出集合，比如某个线程在空队列获取元素时，或者在已满队列存储元素时，都会被阻塞。
  2. 非阻塞队列
     • 非阻塞队列是使用CAS(compare and set)机制实现，并发性能好。
  3. 双端队列（Deque）
     • Deque是一个既可以在头部操作元素，又可以为尾部操作元素，俗称为双向队列。

import java.util.LinkedList;
import java.util.Queue;

public class Test
{
    public static void main(String[] args)
    {
        Queue<String> stringQueue = new LinkedList<>();

        stringQueue.offer("1");
        stringQueue.offer("2");
        stringQueue.offer("3");
        stringQueue.offer("4");
        stringQueue.offer("5");

        //poll()方法提取第一个元素并且删除它
        String content = stringQueue.poll();
        System.out.println("被提取的元素=" + content);

        System.out.println("----------------------------");
        for (String item : stringQueue)
        {
            System.out.println("剩余元素=" + item);
        }
        System.out.println(stringQueue.size());
    }
    /*
    * 输出结果
    *   被提取的元素=1
        ----------------------------
        剩余元素=2
        剩余元素=3
        剩余元素=4
        剩余元素=5
        4
    * */
}

4.2，Queue队列之阻塞队列

• ArrayBlockingQueue基于数组实现的一个阻塞队列，在创建ArrayBlockingQueue对象时必须指定容量大小。

• ArrayBlockingQueue可以指定公平性与非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。

• ArrayBlockingQueue常用方法：

  1. put方法用来向队尾存入元素，如果队列满，则等待。
  2. take方法用来从队首取元素，如果队列为空，则等待。
  3. offer方法用来向队尾存入元素，如果队列满，则等待一定时间，当时间期限达到时，如果还没有插入成功，则返回false；否则返回true。
  4. poll方法用来从队首取元素，如果队列为空，则等待一定的时间，当时间期限达到时，如果取不到，返回null；否则返回取得的元素。

• ArrayBlockingQueue阻塞队列实现的生产者-消费者模式

import java.util.concurrent.ArrayBlockingQueue;

class Provider extends Thread
{
    ArrayBlockingQueue<Integer> queue;
    int queueSize;

    public Provider(ArrayBlockingQueue<Integer> queue, int queueSize)
    {
        this.queue = queue;
        this.queueSize = queueSize;
    }

    @Override
    public void run()
    {
        provide();
    }

    private void provide()
    {
        while (true)
        {
            try
            {
                //put方法用来向队尾存入元素，如果队列满，则等待。
                synchronized (this)
                {
                    queue.put(1);
                    System.out.println("向队列中插入一个元素，队列剩余空间：" + (queueSize - queue.size()));
                }
                Thread.sleep(2000);
            }
            catch (InterruptedException e)
            {
                e.printStackTrace();
            }
        }
    }
}

class Consumer extends Thread
{
    ArrayBlockingQueue<Integer> queue;

    public Consumer(ArrayBlockingQueue<Integer> queue)
    {
        this.queue = queue;
    }

    @Override
    public void run()
    {
        consume();
    }

    private void consume()
    {
        while (true)
        {
            try
            {
                Thread.sleep(3000);
                //take方法用来从队首取元素，如果队列为空，则等待。
                synchronized (this)
                {
                    queue.take();
                    System.out.println("从队列取走一个元素，队列剩余：" + queue.size() + " 个元素");
                }
            }
            catch (InterruptedException e)
            {
                e.printStackTrace();
            }
        }
    }
}

public class Test
{
    private int queueSize = 10;

    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(queueSize);

    public static void main(String[] args)
    {
        Test test = new Test();
        Provider provider = new Provider(test.queue, test.queueSize);
        Consumer consumer = new Consumer(test.queue);
        provider.start();
        consumer.start();
    }
}

4.3，Queue队列之优先级队列

• PriorityQueue优先级队列既可以根据元素的自然排序来排序，也可以根据Comparator来设置排序规则。
• PriorityQueue优先级队列对于自定义的类来说，需要自定义比较器。
• PriorityQueue优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先级队列增加元素的时候，队列大小会自动增加。
• PriorityQueue优先队列不允许空值。
• PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue在多线程环境使用。
• PriorityQueue优先级队列的案例：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

class People
{
    public People(String name, int age)
    {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString()
    {
        return "People{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    String name;
    int age;

    public String getName()
    {
        return name;
    }

    public void setName(String name)
    {
        this.name = name;
    }


    public int getAge()
    {
        return age;
    }

    public void setAge(int age)
    {
        this.age = age;
    }
}

public class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<People> queue = new PriorityQueue<>(11,
                new Comparator<People>()
                {
                    @Override
                    public int compare(People o1, People o2)
                    {
                        return o2.age - o1.age;
                    }
                });

        for (int i = 1; i <= 10; i++)
        {
            queue.add(new People("张" + i, (new Random().nextInt(100))));
        }

        while (!queue.isEmpty())
        {
            System.out.println(queue.poll().toString());
        }
    }
    /*
    * 输出结果
    *   People{name='张2', age=86}
        People{name='张4', age=69}
        People{name='张8', age=66}
        People{name='张5', age=66}
        People{name='张7', age=64}
        People{name='张6', age=52}
        People{name='张3', age=19}
        People{name='张10', age=12}
        People{name='张9', age=7}
        People{name='张1', age=7}
    * */
}

4.4，Queue队列之延时队列

• DelayQueue是一个无界的BlockingQueue，用于放置实现了Delayed接口的对象，其中的对象只能在其到期时才能从队列中取走。这种队列是有序的，即队头对象的延迟到期时间最长。
• 不能将null元素放置到DelayQueue队列中。
• DelayQueue只能添加(offer/put/add)实现了Delayed接口的对象。
• DelayQueue延时队列的案例：

import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

class MyDelayedTask implements Delayed
{
    private long start = System.currentTimeMillis();
    private String name;
    private long time;

    public MyDelayedTask(String name, long time)
    {
        this.name = name;
        this.time = time;
    }

    @Override
    public long getDelay(TimeUnit unit)
    {
        return unit.convert((start + time) -
                System.currentTimeMillis(), TimeUnit.MILLISECONDS);
    }

    @Override
    public int compareTo(Delayed o)
    {
        MyDelayedTask o1 = (MyDelayedTask) o;
        return (int) (this.getDelay(TimeUnit.MILLISECONDS) -
                o.getDelay(TimeUnit.MILLISECONDS));
    }

    public String getName()
    {
        return name;
    }

    public void setName(String name)
    {
        this.name = name;
    }

    public long getTime()
    {
        return time;
    }

    public void setTime(long time)
    {
        this.time = time;
    }
}

public class Test
{
    private static DelayQueue delayQueue = new DelayQueue();

    public static void main(String[] args) throws InterruptedException
    {
        new Thread(new Runnable()
        {
            @Override
            public void run()
            {
                delayQueue.offer(new MyDelayedTask("task1", 10000));
                delayQueue.offer(new MyDelayedTask("task2", 3900));
                delayQueue.offer(new MyDelayedTask("task3", 1900));
                delayQueue.offer(new MyDelayedTask("task4", 5900));
                delayQueue.offer(new MyDelayedTask("task5", 6900));
                delayQueue.offer(new MyDelayedTask("task6", 7900));
                delayQueue.offer(new MyDelayedTask("task7", 4900));
            }
        }).start();

        while (true)
        {
            MyDelayedTask take = (MyDelayedTask) delayQueue.take();
            System.out.println("任务名称：" + take.getName() + "，时间是：" + take.getTime());
        }
    }
    /*
    * 输出结果
    *   任务名称：task3，时间是：1900
        任务名称：task2，时间是：3900
        任务名称：task7，时间是：4900
        任务名称：task4，时间是：5900
        任务名称：task5，时间是：6900
        任务名称：task6，时间是：7900
        任务名称：task1，时间是：10000
    * */
}