集合——Queue:可重复
执键写春秋 499 8

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()返回堆内最小值。
评论区

索引目录