文章目錄

• 前言
• 一、Queue接口
• • Queue接口的特點(diǎn)：
  • QueueAPI的方法：
• 二、PriorityQueue
• • 構(gòu)造器
  • 擴(kuò)容機(jī)制：
  • 方法：
  • • add()和offer()
    • remove(Object o)和poll()
    • element()和peek()
• 三 、top K問題：
• 總結(jié)

---

前言

---

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

一、Queue接口

數(shù)據(jù)可重復(fù)，保證有序性（基于數(shù)據(jù)類型）、不可以存儲(chǔ)null。

Queue接口的特點(diǎn)：

隊(duì)列的主要特點(diǎn)是在基本的集合方法之外，還提供特殊的插入、獲取和檢驗(yàn)操作。每個(gè)操作都提供兩個(gè)方法，一種返回異常，一種返回null或者false.
隊(duì)列一般滿足先進(jìn)先出規(guī)則（FIFO)，除了優(yōu)先隊(duì)列（priority queue）和棧（stack），但是棧是FILO（先進(jìn)后出規(guī)則），優(yōu)先隊(duì)列自己定義了排序規(guī)則。

QueueAPI的方法：

• add(E e) 插入一個(gè)元素到隊(duì)列中，失敗時(shí)返回IllegalStateException （隊(duì)列容量不夠）
• element() 返回隊(duì)列頭部的元素
• offer(E e) 插入一個(gè)元素到隊(duì)列中，失敗時(shí)返回false
• peek() 返回隊(duì)列頭部的元素，隊(duì)列為空時(shí)返回null
• poll() 返回并移除隊(duì)列的頭部元素，隊(duì)列為空時(shí)返回null
• remove() 返回并移除隊(duì)列的頭部元素

二、PriorityQueue

構(gòu)造器

兩個(gè)參數(shù)的作用：
int initialCapacity, //初始容量
Comparator<? super E> comparator //自定義比較器

public PriorityQueue() {//private static final int DEFAULT_INITIAL_CAPACITY = 11;//默認(rèn)初始容量：this(DEFAULT_INITIAL_CAPACITY, null);}public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {if (initialCapacity < 1)//參數(shù)合法性檢驗(yàn)throw new IllegalArgumentException();//自定義初始容量//底層默認(rèn)this.queue = new Object[initialCapacity];this.comparator = comparator;}

擴(kuò)容機(jī)制：

原來隊(duì)列長度小于64 2倍+2擴(kuò)容大于64 1.5倍擴(kuò)容

private void grow(int minCapacity) {int oldCapacity = queue.length;// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// overflow-conscious code//最大擴(kuò)容量比較//如果新擴(kuò)容大于最大擴(kuò)容量邊界 用原數(shù)組長度和擴(kuò)容邊界比較，如果大于最大擴(kuò)容量邊界返回int最大值，如果小于返回最大擴(kuò)容邊界if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);//數(shù)據(jù)拷貝}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow 容量越界throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

方法：

add()和offer()

從源碼上看PriorityQueue的入列操作沒有對(duì)所有加入的元素進(jìn)行優(yōu)先級(jí)排序。而是只保證數(shù)組父節(jié)點(diǎn)數(shù)據(jù)小于子節(jié)點(diǎn)數(shù)據(jù)。

public boolean add(E e) {return offer(e);} public boolean offer(E e) {if (e == null)//PriorityQueue不能存儲(chǔ)nullthrow new NullPointerException();modCount++;int i = size;if (i >= queue.length) //數(shù)組擴(kuò)容grow(i + 1);//擴(kuò)容參數(shù)為i+1siftUp(i, e);size = i + 1;return true;}private void siftUp(int k, E x) {if (comparator != null) //判斷是否使用類部比較器類型siftUpUsingComparator(k, x, queue, comparator);elsesiftUpComparable(k, x, queue);}//PriorityQueue默認(rèn)的比較器實(shí)現(xiàn)了小根堆private static <T> void siftUpComparable(int k, T x, Object[] es) {Comparable<? super T> key = (Comparable<? super T>) x;while (k > 0) {int parent = (k - 1) >>> 1; //找出父節(jié)點(diǎn)Object e = es[parent];if (key.compareTo((T) e) >= 0)//傳入值和父節(jié)點(diǎn)比較如果大于父節(jié)點(diǎn)將數(shù)據(jù)存入到當(dāng)前的位置，否則父節(jié)點(diǎn)數(shù)據(jù)下移繼續(xù)向上查詢break;es[k] = e;k = parent;}es[k] = key;//key賦值}

remove(Object o)和poll()

原理：取出頭部數(shù)據(jù)，將末尾數(shù)據(jù)從頭部向下檢驗(yàn)知道找到合適他的位置

public E poll() {final Object[] es;final E result;if ((result = (E) ((es = queue)[0])) != null) { //根節(jié)點(diǎn)有數(shù)據(jù)modCount++;final int n;final E x = (E) es[(n = --size)];//最后一共數(shù)據(jù)es[n] = null;//末尾設(shè)置為null方便垃圾回收if (n > 0) {final Comparator<? super E> cmp;//判斷是否為使用默認(rèn)比較強(qiáng)if ((cmp = comparator) == null)siftDownComparable(0, x, es, n);elsesiftDownUsingComparator(0, x, es, n, cmp);}}return result;}public boolean remove(Object o) {int i = indexOf(o); //查找此數(shù)據(jù)是否存在存在返回該數(shù)據(jù)所在位置，不存在返回-1if (i == -1)return false;//數(shù)據(jù)不存在返回falseelse {removeAt(i);return true;}}E removeAt(int i) {// assert i >= 0 && i < size;final Object[] es = queue;modCount++;int s = --size;//size-1if (s == i) // 此數(shù)據(jù)正好是末尾數(shù)據(jù)es[i] = null;//數(shù)據(jù)覆蓋，方便垃圾回收else {E moved = (E) es[s];//取出末尾數(shù)據(jù)es[s] = null;//末尾設(shè)置為null方便垃圾回收siftDown(i, moved);if (es[i] == moved) {siftUp(i, moved);if (es[i] != moved)return moved;}}return null;}

element()和peek()

public E element() {//如果存在返回該值不存在拋出異常E x = peek();if (x != null)return x;elsethrow new NoSuchElementException();}public E peek() {//如果存在返回該值不存在返回nullreturn (E) queue[0];}

三 、top K問題：

查找指定數(shù)據(jù)中出現(xiàn)次數(shù)最多的前K個(gè)數(shù)據(jù)：
比如：求前K個(gè)最大數(shù)據(jù)，我們創(chuàng)建一個(gè)容量為K的底層為小根堆的隊(duì)列每次插入數(shù)據(jù)只需要與根數(shù)據(jù)比較決定是否插入即可，相反求最小數(shù)據(jù)就創(chuàng)建一個(gè)大跟堆。

public static void BufferedReaderEx(String str) {//指定文件目錄File file = new File(str); //file實(shí)例FileReader reader = null;//讀取數(shù)據(jù)并存儲(chǔ)在list集合中try {reader = new FileReader(file);BufferedReader bufferedReader = new BufferedReader(reader);String tmp;ArrayList<String> list = new ArrayList<>();while ((tmp = bufferedReader.readLine()) != null) {String[] split = tmp.split(",");for (String s:split){list.add(s);}}HashMap<String,Integer> map = HashMapEx(list);PriorityQueue<Map.Entry<String, Integer>> queue = QueueEx(map,5);while (!queue.isEmpty()){Map.Entry<String, Integer> remove = queue.remove();System.out.println("數(shù)字：" + remove.getKey() + ",出現(xiàn)：" +remove.getValue() + "次");}} catch (IOException e) {e.printStackTrace();}}public static HashMap<String,Integer> HashMapEx(ArrayList<String> list){//將數(shù)據(jù)存儲(chǔ)到HashMap中用來統(tǒng)計(jì)一個(gè)數(shù)組出現(xiàn)的次數(shù) key為數(shù)據(jù) value為出現(xiàn)次數(shù)HashMap<String, Integer> map = new HashMap<>();while (!list.isEmpty()){String index = list.remove(0);if (map.containsKey(index)) {map.put(index, map.get(index) + 1);} else {map.put(index, 1);}}return map;}public static PriorityQueue<Map.Entry<String, Integer>> QueueEx(HashMap<String,Integer> map,int num){//將Map中的Entry存儲(chǔ)到PriorityQueue隊(duì)列中并提供一個(gè)關(guān)于Entry.value的比較器并將隊(duì)列的容量設(shè)置為KPriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(num, new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {return (Integer) o1.getValue() - (Integer) o2.getValue();}});Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();while (iterator.hasNext()){//遍歷Map集合 如果隊(duì)列容量小于K直接插入數(shù)據(jù)否則與queue頂部數(shù)據(jù)進(jìn)行Value計(jì)較如果大于頂部數(shù)據(jù)插入到queue中Map.Entry<String, Integer> next = iterator.next();if(queue.size()<num){queue.add(next);}else {if(next.getValue()>queue.peek().getValue()){queue.remove();queue.add(next);}}}return queue;}

總結(jié)

Queue接口保證數(shù)據(jù)有序性（基于數(shù)據(jù)類型）、不可以存儲(chǔ)nullPriorityQueue介紹可以自定義比較器用來實(shí)現(xiàn)自己想要的底層結(jié)構(gòu)方便我們最值問題和topK問題的求解。

總結(jié)

以上是生活随笔為你收集整理的Queue接口及是实现类PriorityQueue介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。