Queue的使用、priority_queue优先队列

1、Queue的使用（FIFO）（使用LinkedList实现）

• Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。
• 它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。
• 如果要使用前端而不移出该元素，使用element()或者peek()方法。

• 注意：LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

import java.util.Queue;  
import java.util.LinkedList;  
public class TestQueue {  
    public static void main(String[] args) {  
        Queue<String> queue = new LinkedList<String>();  
        queue.offer("Hello");  
        queue.offer("World!");  
        queue.offer("你好！");  
        System.out.println(queue.size());  
        String str;  
        while((str=queue.poll())!=null){  
            System.out.print(str);  
        }  
        System.out.println();  
        System.out.println(queue.size());  
    }  
} 

java中queue的使用

• Queue接口与List，Set同一级别，都是继承了Collection接口。
• LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue继承了Queue接口。

队列是一种数据结构，它有两个基本操作：在队列尾部加入一个元素，和从队列头部移除一个元素。就是说，队列以一种先进先出的方式管理数据，如果你试图向一个已经满了的阻塞队列中添加一个元素或者从一个空的阻塞队列中移除一个元素，将导致线程阻塞。在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可以定期地把中间结果存到阻塞队列中，而其他工作者线程把中间结果取出并将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。

2、priority_queue优先队列（非FIFO，小顶堆升序，使用数组顺序实现）

• 优先队列是队列的一种，优先队列中元素默认排列顺序是升序排列，不过它可以按照自定义的一种方式（数据的优先级）来对队列中的数据进行动态的排序，需要自己定义比较器
• 每次的push和pop操作，队列都会动态的调整，以达到我们预期的方式来存储。
• 例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高
  所以我们无论按照什么顺序push一堆数，最终在队列里总是top出最大的元素。（默认使用小顶堆实现）

比较器升降序说明

Comparator<Object> cmp = new Comparator<Object>() {
        public int compare(Object o1, Object o2) {
            //升序
            return o1-o2;
            //降序
            return o2-o1;
        }
    };

自定义降序

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() { 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

或者

//自定义比较器，降序排列
static Comparator<Integer> cmp = new Comparator<Integer>() {
      public int compare(Integer e1, Integer e2) {
        return e2 - e1;
      }
    };
public static void main(String[] args) {
        //不用比较器，默认升序排列
        Queue<Integer> q = new PriorityQueue<>();
        q.add(3);
        q.add(2);
        q.add(4);
        while(!q.isEmpty())
        {
            System.out.print(q.poll()+" ");
        }
        /**
         * 输出结果
         * 2 3 4 
         */
        //使用自定义比较器，降序排列
        Queue<Integer> qq = new PriorityQueue<>(cmp);//此处使用cmp比较器说明
        qq.add(3);
        qq.add(2);
        qq.add(4);
        while(!qq.isEmpty())
        {
            System.out.print(qq.poll()+" ");
        }
        /**
         * 输出结果
         * 4 3 2 
         */
}

小表显示jdk1.5中的阻塞队列的操作：