Java基础（十八）集合（5）Queue集合

　　队列是只能在尾部添加元素，同时只能在头部删除元素的数据结构。队列的原则就是“先进先出”。

　　Queue接口是Collection接口的最后一个子接口。

　　Queue接口是队列接口，而Deque接口是Queue接口的子接口，可以用来实现双端队列，让人们有效地在头部和尾部同时添加或删除元素。

　　ArrayDeque和LinkedList都实现了Deque接口。

　　实现了Queue接口的类有两种：ArrayDeque类和PriorityQueue类。

　　队列一般有两种实现方式，数组队列和链表队列。

　　如果需要一个循环数组队列，就可以使用ArrayDeque类；如果需要一个链表队列，就直接使用LinkedList类，这个类实现了Queue接口。

 　　1.ArrayDeque（循环数组队列）

　　创建一个ArrayDeque对象：

ArrayDeque<String> aDeque = new ArrayDeque<>();

　　方法测试：

package queue.jun.iplab;

import java.util.ArrayDeque;
import java.util.Iterator;

public class ArrayDequeTest {

    public static void main(String[] args) {
        
        String a = "A", b = "B", c = "C", d = "D", e = "E";
        ArrayDeque<String> aDeque = new ArrayDeque<>();
        aDeque.add(a);
        aDeque.add(b);
        aDeque.addFirst(c);
        aDeque.addLast(d);
        System.out.println(aDeque.isEmpty()); // 打印：false
        
        Iterator<String> it = aDeque.iterator();
        while (it.hasNext()) {                           // 打印：（队头）C A B D
            String string = (String) it.next();
            System.out.print(string + " ");
        }
        System.out.println();
        
        System.out.println(aDeque.poll());      // 打印：C
        System.out.println(aDeque.peek());   // 打印：A
        System.out.println(aDeque.peekLast());  // 打印：D
        System.out.println(aDeque.pop());          // 打印：A
        
        Iterator<String> it_1 = aDeque.iterator();
        while (it_1.hasNext()) {              // 打印：B D
            String string = (String) it_1.next();
            System.out.print(string + " ");
        }
    }
}

　　2.PriorityQueue（高效删除最小元素队列）

　　优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。

　　优先级队列使用了堆，对二叉树进行添加和删除操作，可以让最小的元素移动到根，而不必花费时间对元素进行排序。

　　与TreeSet一样，一个优先级队列既可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供的Comparator对象。

　　保存在PriorityQueue中的对象必须实现Comparator接口：

public class Person implements Comparable<Object> {
    private String name;
    private long id_card;
}

　　以id_card的大小为排序指标，然后重写compareTo方法

    // 重写compareTo方法，按照id_card的大小进行比较，如果大的返回1，等于返回0，小于返回-1
    @Override
    public int compareTo(Object o) {
        Person person = (Person) o;
        int result = id_card > person.id_card ? 1 : (id_card == person.id_card ? 0 : -1);
        return result;
    }

　　创建一个PriorityQueue对象:

PriorityQueue<Person> pQueue = new PriorityQueue<>();

　　插入五个元素：

        Person person1 = new Person("小一", 13311123);
        Person person2 = new Person("小二", 13223131);
        Person person3 = new Person("小三", 13432412);
        Person person4 = new Person("小四", 13621312);
        Person person5 = new Person("小五", 13531231);
        
        PriorityQueue<Person> pQueue = new PriorityQueue<>();
        pQueue.add(person1);
        pQueue.add(person2);
        pQueue.add(person3);
        pQueue.add(person4);
        pQueue.add(person5);

　　使用迭代器访问时，不是按照元素的排列顺序访问的，而是最先访问最小的元素，然后剩余元素按照插入顺序访问：

        Iterator<Person> it = pQueue.iterator();
        while (it.hasNext()) {
            Person person = (Person) it.next();
            System.out.println(person.getName() + " " + person.getId_card());
        }

输出：
小二 13223131
小一 13311123
小三 13432412
小四 13621312
小五 13531231

　　而执行删除操作时，却总是删除掉剩余元素中优先级最小的那个元素。

        while (!pQueue.isEmpty()) {
            System.out.println(pQueue.remove().getId_card());
        }

输出：
13223131
13311123
13432412
13531231
13621312