Queue

Queue接口是Collection的子接口，表示的是队列操作接口，采用FIFO（先进先出）的方式操作，这就好像一队人排队那样，队列中有对头与队列，对头永远指向新加入的对象。队列有两种：分别是单队列和循环队列。通常，队列不容许随机访问队列中的元素，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList，因为LinkedList进行插入、删除操作效率较高

这里说明一下先进先出（First Input First Output，FIFO）：先进先出指的是在一个集合中，会按照顺序增加内容，在输出时先进入的数据会首先输出。与之对应的还有另外一种先进后出，指的是先进入的数据最后取出，而后进入的数据最先取出，先进后出的操作会出现在栈（Stack）中。

1.Queue定义了以下几个方法

• 通过size()方法获取队列长度。
• 通过add()/offer()方法将元素添加到队尾。
• 通过remove()/poll()从队首获取元素并删除。
• 通过element()/peek()从队首获取元素但不删除。

  public interface Queue<E> extends Collection<E> {
      //集合中插入元素
      boolean add(E e);
      //队列中插入元素
      boolean offer(E e);
      //移除元素，当集合为空，抛出异常
      E remove();
      //移除队列头部元素并返回，如果为空，返回null
      E poll();
      //查询集合第一个元素，如果为空，抛出异常
      E element();
      //查询队列中第一个元素，如果为空，返回null
      E peek();
  }

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

2. 案例一：LinkedList

用LinkedList实现,将数据1-5依次入队并打印,然后查看队首元素并打印,然后将队列中所有数据依次出队并打印。

package person.xsc.datamanage;

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

public class QueueDemo {
    public static void main(String[] args) {
        //1.准备一个Queue集合并打印
        Queue<Integer> queue = new LinkedList<Integer>();
        int queueLength=queue.size();//size()方法获取队列长度。
        if(queueLength==0) {
            System.out.println("此时的队列为空！ ");
        }else{
            System.out.println("队列中的元素有: " + queue);
        }
        System.out.println("******************************");
        //2.将数据依次入队并打印
        for (int i = 1; i <= 5; i++) {
            queue.offer(i);//offer()方法将元素添加到队尾。
            System.out.println("队列中的元素有: " + queue);
        }
        System.out.println("******************************");
        //3.查看队首元素并打印
        System.out.println("队首元素是: " + queue.peek());//peek()从队首获取元素但不删除。
        System.out.println("此时队列中的元素有: " + queue);
        System.out.println("******************************");
        //4.将队列中所有数据依次出队并打印
        int len = queue.size();
        for (int i = 0; i < len; i++) {
            System.out.println("出队的元素是: " + queue.poll());//poll()从队首获取元素并删除。
            if(queue.size()>0) {
                System.out.println("此时的队列中的元素还有: " + queue);
            }else {
                System.out.println("队列中的元素已经全部出队!");
            }

        }
    }
}

3. 案例二：PriorityQueue

用PriorityQueue实现，存入People对象，People有姓名属性和年龄属性，排序要求：年龄由低到高，如果年龄相等则按照姓名字母顺序有前到后。提示：PriorityQueue有自动排序功能，但对于自定义数据类型需要覆写compareTo（）方法。

package person.xsc.datamanage;

import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;
import java.util.PriorityQueue;
import java.util.Queue;

class People implements Comparator<String>,Comparable<People>{
    private String name;
    private int age;
    public People() {

    }
    public People(String name, int age){
        this.name = name;
        this.age = 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;
    }
    @Override
    public int compareTo(People per) {//排序要求 年龄由低到高  年龄相等则按姓名字母的顺序有前到后
        // TODO Auto-generated method stub
        if(this.age>per.age) {  
            return 1;  
        }else if(this.age<per.age) {
            return -1;
        }else {
            return this.compare(this.name, per.name);//调用String中的compareTo()方法，用来比较两个字符串的字典顺序。
        }
    }
    @Override
    public int compare(String perName1, String perName2) {
        // TODO Auto-generated method stub
        Collator instance = Collator.getInstance(Locale.CHINA);
        return instance.compare(perName1, perName2);
    }
}
public class PriorityQueueDemo{
    public static void main(String[] args) {
        Queue<People> priorityQueue =new PriorityQueue<People>();
        priorityQueue.offer(new People("赵三",29));     ////offer()方法添加元素，依据compareTo方法根据年龄排序。
        priorityQueue.offer(new People("王三",25));
        priorityQueue.offer(new People("唐三",49));
        priorityQueue.offer(new People("爱三",49));
        priorityQueue.offer(new People("比三",49));
        priorityQueue.offer(new People("张三",49));
        priorityQueue.offer(new People("张三四",49));
        priorityQueue.offer(new People("张三二",49));
        priorityQueue.offer(new People("李三",49));
        priorityQueue.offer(new People("徐三",19));
        priorityQueue.offer(new People("刘三",19));
        while(true){
            People people = priorityQueue.poll();//poll()从队首获取元素并删除。
            if(people == null) {
                break;
            }else {
                System.out.println(people.getName()+"的年龄为 " + people.getAge());
            }
        }
    }
}

4. 关于Queue面试的问题

• poll()方法和 remove()方法的区别？ Queue队列中，poll() 和 remove() 都是从队列中取出一个元素，在队列元素为空的情况下，remove() 方法会抛出异常，poll() 方法只会返回 null 。
• 什么是Java优先级队列(PriorityQueue)？ 优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序。优先队列中元素默认排列顺序是升序排列，但对于自己定义的类来说，需要自己定义比较器。

1. 定义方法：peek()//返回队首元素；poll()//返回队首元素，队首元素出队列；add()//添加元素；size()//返回队列元素个数；isEmpty()//判断队列是否为空，为空返回true,不空返回false。
2. 特点：基于优先级堆；不允许null值；线程不安全；出入队时间复杂度O(log(n))；调用remove()返回堆内最小值。