.net作业做网站/山东今日头条新闻

队列的实现

首先尝试动手写一个类实现Queue接口，发现要实现的方法太多了，麻烦。所幸，JDK为我们提供了一个骨架实现类AbstractQueue，最大限度地减少了实现Queue接口所需的工作。

AbstractQueue

/*** 该骨架对于允许null元素的实现来讲是不合适的，其方法add 、 remove和element分别基于offer 、 poll和peek来实现。*  所以继承该类的队列实现必须提供一个不允许插入null元素的offer方法*/
public abstract class AbstractQueue<E>extends AbstractCollection<E>implements Queue<E> {protected AbstractQueue() {}public boolean add(E e) {if (offer(e))return true;elsethrow new IllegalStateException("Queue full");}public E remove() {E x = poll();if (x != null)return x;elsethrow new NoSuchElementException();}public E element() {E x = peek();if (x != null)return x;elsethrow new NoSuchElementException();}public void clear() {while (poll() != null);}public boolean addAll(Collection<? extends E> c) {if (c == null)throw new NullPointerException();if (c == this)throw new IllegalArgumentException();boolean modified = false;for (E e : c)if (add(e))modified = true;return modified;}

再找一个基于AbstractQueue的实现PriorityQueue来学习一波。

PriorityQueue

二叉堆实现，理解了二叉堆，这个就实在没什么好讲的了，本质是个最小堆，参考文章https://www.jianshu.com/p/6d3a12fe2d04

但是有几点需要拎出来单独分析一下

	/*** 从队列中移除第 i 个元素。 与常规数组的移除不同，堆的移除操作，首先将最后一个元素e替换到位置i上，同时还要进行下沉或上浮操作以维持堆结构。* 如果在执行上浮或下沉时，元素e恰好都未移位，即最后一个元素替换到i位置上，刚好完美契合堆结构，即此队列的前i-1（包括 i-1）位的元素皆不受影响。在这些情况下，它返回 null。 * 假如在上浮或下沉过程中，元素e与早于 i 的元素（前i-1位）发生了交换。即元素e不在预料的i位置上，而是前i-1的某个位置上。在这些情况下，它返回元素e。 *  这个事实被 iterator.remove 使用，以避免丢失遍历元素。（介绍迭代时会解释）*/private E removeAt(int i) {// assert i >= 0 && i < size;modCount++;int s = --size;if (s == i) // removed last elementqueue[i] = null;else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);// 说明并未下沉移位if (queue[i] == moved) {siftUp(i, moved);// 说明发生了上浮移位if (queue[i] != moved)return moved;}}return null;}

我这里提供一个简单例子体会一下：
一个最大堆[8,4,6,2,3,5,1]移除下标1的元素4，这里会发生下沉
一个最大堆[8,4,6,2,5,1,5]移除下标4的元素3，这里会发生上浮
（注意PriorityQueue是个最小堆，如果要测试，注意提供额外的比较器）

package test;import org.junit.Test;import java.util.Iterator;
import java.util.PriorityQueue;public class Client {@Testpublic void testUp() {PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> -a.compareTo(b));queue.add(8);queue.add(4);queue.add(6);queue.add(2);queue.add(3);queue.add(5);queue.add(1);queue.remove(4);StringBuilder sb = new StringBuilder();for (int i : queue) {sb.append(i).append(",");}System.out.println(sb);}@Testpublic void testDown() {PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> -a.compareTo(b));queue.add(8);queue.add(4);queue.add(6);queue.add(2);queue.add(3);queue.add(1);queue.add(5);queue.remove(3);StringBuilder sb = new StringBuilder();for (int i : queue) {sb.append(i).append(",");}System.out.println(sb);}@Testpublic void testItr() {PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> -a.compareTo(b));queue.add(8);queue.add(4);queue.add(6);queue.add(2);queue.add(3);queue.add(1);queue.add(5);StringBuilder sb = new StringBuilder();Iterator<Integer> iterator = queue.iterator();while (iterator.hasNext()) {Integer next = iterator.next();if (next == 3) {iterator.remove();}sb.append(next).append(",");}System.out.println(sb);}}

迭代器的实现（偷个懒，懒得写分析了）

    private final class Itr implements Iterator<E> {/*** Index (into queue array) of element to be returned by* subsequent call to next.*/private int cursor = 0;/*** Index of element returned by most recent call to next,* unless that element came from the forgetMeNot list.* Set to -1 if element is deleted by a call to remove.*/private int lastRet = -1;/*** A queue of elements that were moved from the unvisited portion of* the heap into the visited portion as a result of "unlucky" element* removals during the iteration.  (Unlucky element removals are those* that require a siftup instead of a siftdown.)  We must visit all of* the elements in this list to complete the iteration.  We do this* after we've completed the "normal" iteration.** We expect that most iterations, even those involving removals,* will not need to store elements in this field.*/private ArrayDeque<E> forgetMeNot = null;/*** Element returned by the most recent call to next iff that* element was drawn from the forgetMeNot list.*/private E lastRetElt = null;/*** The modCount value that the iterator believes that the backing* Queue should have.  If this expectation is violated, the iterator* has detected concurrent modification.*/private int expectedModCount = modCount;public boolean hasNext() {return cursor < size ||(forgetMeNot != null && !forgetMeNot.isEmpty());}@SuppressWarnings("unchecked")public E next() {if (expectedModCount != modCount)throw new ConcurrentModificationException();if (cursor < size)return (E) queue[lastRet = cursor++];if (forgetMeNot != null) {lastRet = -1;lastRetElt = forgetMeNot.poll();if (lastRetElt != null)return lastRetElt;}throw new NoSuchElementException();}public void remove() {if (expectedModCount != modCount)throw new ConcurrentModificationException();if (lastRet != -1) {E moved = PriorityQueue.this.removeAt(lastRet);lastRet = -1;if (moved == null)cursor--;else {if (forgetMeNot == null)forgetMeNot = new ArrayDeque<>();forgetMeNot.add(moved);}} else if (lastRetElt != null) {PriorityQueue.this.removeEq(lastRetElt);lastRetElt = null;} else {throw new IllegalStateException();}expectedModCount = modCount;}}