[数据结构与算法]java36-集合进阶-Queue集合-特有方法-LinkedList-PriorityQueue

Queue集合

Queue集合继承自Collection接口，它的常用实现类是LinkedList 和 PriorityQueue 类。
Queue用来存放等待处理元素的集合，这种场景一般用来缓冲、并发访问。

Queue特有方法

注意：

• 大多数实现Queue接口的实现类都具有禁止添加null元素的功能，避免在查询时返回null，比如ArrayBlockingQueue，PriorityBlockQueue；但是还有一些实现类没有实现这样的功能，比如LinkedList。
• 虽然LinkedList没有明确禁止添加null元素，但是Queue的实现都类不允许添加null元素，原因是：poll、peek方法在异常（对队列为空）的时候会返回null，当添加null元素后，会产生歧义（不知道是发生异常还是获取到null元素）

LinkedList

概述

• LinkedList类是双向链表，列表中的每个节点都包含一个对前一个和后一个元素的引用。
• LinkedList可以被当作堆栈、队列或者双端队列进行操作。
• LinkedList实现了Serializable接口，所以可以被序列化，能通过序列化去传输。
• LinkedList是非同步的。
• LinkedList本质是双向链表，包含两个重要成员：header 和 size 。
  • header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量：previous、next、element。其中previous是该节点的上一个，next是该节点的下一个，element是该节点所包含的值。
  • size是双向链表中节点的个数。

构造函数

常用方法

PriorityQueue

概念

队列的核心思想是先进先出，优先级队列有点不一样。
优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列的有序性。（有序：升序或降序）
PriorityQueue是基于优先堆的一个无界队列，队列中的元素排序：默认的自然排序（使用Comparable接口）或比较器排序（使用Comparator接口）。

方法

都是Queue中的方法。add、offer、remove、poll、get、element、peek。
具体方法讲解

• 添加元素 add()/offer()

        System.out.println(que.add(null));
        // 添加null元素，会报NullPointerException
        System.out.println(que.offer(null));
        // 添加null元素，则会报NullPointerException
        System.out.println(que.add(100));
        System.out.println(que.add(10));
        System.out.println(que.add(30));
        System.out.println(que.add(20));
        System.out.println(que);//输出[10, 20,30,100]

• 获取元素 element()/peek()

        System.out.println(que.element());//10
        System.out.println(que.peek());//10
        // 获取元素 默认情况下 每次获取的元素是列表头部元素
        System.out.println(que);//[10, 20, 30, 100]

• 删除元素 remove()/poll()

 System.out.println(que.remove());//10
        System.out.println(que.poll());//20
        // 依次删除头部元素
        System.out.println(que);//[30, 100]

• 判断元素是否存在 contain(E e)

System.out.println(que.contains(30));//true

• 整体代码：

public class QueueDEmo {
    public static void main(String[] args) {
        Queue<Integer> que = new PriorityQueue<Integer>();

//        System.out.println(que.add(null));
        // 添加null元素，会报NullPointerException
//        System.out.println(que.offer(null));
        // 添加null元素，则会报NullPointerException
        System.out.println(que.add(100));
        System.out.println(que.add(10));
        System.out.println(que.add(30));
        System.out.println(que.add(20));
        System.out.println(que);//输出[10, 20,30,100]

        System.out.println("------------");
        System.out.println(que.element());//10
        System.out.println(que.peek());//10
        // 获取元素 默认情况下 每次获取的元素是列表头部元素
        System.out.println(que);

        System.out.println("----------");
        System.out.println(que.remove());//10
        System.out.println(que.poll());//20
        // 依次删除头部元素
        System.out.println(que);//30 ,100


    }
}

案例

案例1
需求：在未排序的数组中，找到第K个未排序的最大值。
解题思路：

思路1：冒泡排序
外层循环控制比较的轮次，for(int i =0;i<array.length;i++)
	内存循环控制每轮比较次数 for(int j = i ;j<array.length;j++)
	当i++ == k的时候退出循环。
思路2：Queue优先级队列实现
方法传入参数int[] array,int k
	创建PriorityQueue队列
	使用增强for循环(数据类型 变量名：数组名)
		使用队列.add(变量名)，给队列添加元素
	判断队列元素>k，则删除队列元素 队列.poll()
	最后返回值是 队列.peek()

代码：冒泡排序

// 330-Test1
public class Test1 {
    // 需求：在未排序的数组中，找到第K个未排序的最大值。
    public static int findKthLargest(int[] array, int K){
        int result = array[0];
        int tep = 0;
        // 使用冒泡排序
        // 外层循环表示程序 比较轮数
        for(int i = 0;i <array.length;i++){
            // 内层循环表示 每轮比较次数
            for(int j = i+1; j<array.length;j++ ){
                if(array[i] > array[j]){
                    tep = array[i];
                    array[i] = array[j];
                    array[j] = tep;
                }
            }
            if(i++ == K){
                result = array[array.length-K];
                break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {10,9,5,24,35};
        int result = findKthLargest(array,3);
        System.out.println(result);
    }
}

代码：优先级队列PriorityQueue

    // 优先级队列实现
    public static int findKthLargestQueue(int[] array,int k){
        Queue<Integer> que = new PriorityQueue<Integer>();
        for(int arr:array){
            que.add(arr);
            if(que.size() > k) que.poll();
        }
        return que.peek();
    }