下沙网站优化,文汇网站建设,武进网站建设方案,网站服务器 免费的吗1、 Queue与Deque的区别
在研究java集合源码的时候#xff0c;发现了一个很少用但是很有趣的点#xff1a;Queue以及Deque#xff1b; 平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用#xff0c;但是一直都不知道Queue的作用#xff0c;于是就直接官方…1、 Queue与Deque的区别
在研究java集合源码的时候发现了一个很少用但是很有趣的点Queue以及Deque 平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用但是一直都不知道Queue的作用于是就直接官方文档好了。 Queue和Deque Deque是Queue的子接口 从源码中可以得知Queue以及Deque都是继承于CollectionDeque是Queue的子接口。 public interface DequeE extends QueueE {}
Queue——单端队列Deque——双端队列 从Deque的解释中我们可以得知Deque是double ended queue我将其理解成双端队列就是可以在首和尾都进行插入或删除元素。 而Queue的解释中Queue就是简单的FIFO先进先出队列。所以在概念上来说Queue是FIFO的单端队列Deque是双端队列。
Queue常用子类——PriorityQueueDeque常用子类——LinkedList以及ArrayDeque Queue有一个直接子类PriorityQueue。 而Deque中直接子类有两个LinkedList以及ArrayDeque。 PriorityQueue 我觉得重点就在圈定的两个单词无边界的优先级的堆。 从源码中明显看到PriorityQueue的底层数据结构是数组而无边界的形容那么指明了PriorityQueue是自带扩容机制的具体请看PriorityQueue的grow方法。
2 PriorityQueue源码解读
top k算法的经典实现是大顶堆和小顶堆而在JAVA中可以用PriorityQueue实现小顶堆话不多说直接上代码
public static ListInteger getTopMapNum(int[] arr, int k) {QueueInteger priorityQueue new PriorityQueue();ListInteger topKList new ArrayList();if (arr null || k arr.length || k 0) {return topKList;}for (int i : arr) {if (priorityQueue.size() k) {priorityQueue.add(i);} else {if (priorityQueue.peek() i) {priorityQueue.poll();priorityQueue.add(i);}}}while (k-- 0) {topKList.add(priorityQueue.poll());}return topKList;
}
作为程序员只知道简单的如何实现是不够的最好能够深入源码下面我们就来聊一聊PriorityQueue PriorityQueue是优先队列作用是保证每次取出的元素都是队列中权值最小的这里涉及到了大小关系元素大小的评判可以通过元素自身的自然顺序使用默认的比较器也可以通过构造时传入的比较器。
Java中PriorityQueue实现了Queue接口不允许放入null元素其通过堆实现具体说是通过完全二叉树complete binary tree实现的小顶堆任意一个非叶子节点的权值都不大于其左右子节点的权值也就意味着可以通过数组来作为PriorityQueue的底层实现。 上图中我们给每个元素按照层序遍历的方式进行了编号如果你足够细心会发现父节点和子节点的编号是有联系的更确切的说父子节点的编号之间有如下关系 leftNo parentNo*21 rightNo parentNo*22 parentNo (nodeNo-1)/2 通过上述三个公式可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。 PriorityQueue的peek()和element操作是常数时间add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。
方法解析JDK 1.8 add()和offer add()方法内部是调用的offer()所以两个方法没啥区别都是向队列中插入元素 新加入的元素可能会破坏小顶堆的性质所以需要进行调整
/*** The number of times this priority queue has been* istructurally modified/i. See AbstractList for gory details.*队列调整的次数*/
transient int modCount 0; // non-private to simplify nested class access
/*** The number of elements in the priority queue.*队列中元素的个数*/
private int size 0;
public boolean add(E e) {//add方法内部调用的offer方法return offer(e);
}
public boolean offer(E e) {if (e null)throw new NullPointerException();//队列调整的次数modCount;int i size;//如果队列元素个数大于等于队列的长度则需要进行扩容if (i queue.length)grow(i 1);size i 1;//如果是第一个元素直接插入即可if (i 0)queue[0] e;elsesiftUp(i, e);//如果不是第一个元素则需要进行调整return true;
}
/*** Increases the capacity of the array.*队列扩容* param minCapacity the desired minimum capacity*/
private void grow(int minCapacity) {//原始队列容量int oldCapacity queue.length;// Double size if small; else grow by 50%//如果原始队列容量没有超过64则翻倍扩容否则扩容50%int newCapacity oldCapacity ((oldCapacity 64) ?(oldCapacity 2) :(oldCapacity 1));// overflow-conscious code//如果扩容后的队列大小超过了最大队列大小则需要进行特殊处理if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);queue Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // overflowthrow new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
/*** Inserts item x at position k, maintaining heap invariant by* promoting x up the tree until it is greater than or equal to* its parent, or is the root.** To simplify and speed up coercions and comparisons. the* Comparable and Comparator versions are separated into different* methods that are otherwise identical. (Similarly for siftDown.)** param k the position to fill* param x the item to insert* 元素添加*/
private void siftUp(int k, E x) {//使用构造方法传进来的比较器if (comparator ! null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);//使用默认的比较器
}
private void siftUpComparable(int k, E x) {Comparable? super E key (Comparable? super E) x;while (k 0) {//获取父节点的下标int parent (k - 1) 1;//父节点的元素值Object e queue[parent];//如果新插入的元素比父节点的元素值大循环结束新插入节点直接插入最后即可if (key.compareTo((E) e) 0)break;//否则需要把父节点元素值放到新插入节点的下标可以理解为父节点与新插入元素调换位置queue[k] e;//重复进行知道父节点比子节点小k parent;}//新插入元素放入排序后的下标queue[k] key;
}
poll 类似poll 从上往下进行然后将左右进行比较将小的一个和 父节点交换
3 LinkedList以及ArrayDeque
从官方解释来看ArrayDeque是无初始容量的双端队列LinkedList则是双向链表。 而我们还能看到ArrayDeque作为队列时的效率比LinkedList要高。 而在栈的使用场景下无疑具有尾结点不需判空的LinkedList更为高效。 演示ArrayDeque作为队列以及LinkedList作为栈的使用
private static void usingAsQueue() {DequeInteger queuenew ArrayDeque();System.out.println(队列为空:queue.isEmpty()); //判断队列是否为空queue.addLast(12); //添加元素System.out.println(queue.peekFirst()); //获取队列首部元素System.out.println(queue.pollFirst()); //获取并移除栈顶元素}private static void usingAsStack() {//作为栈使用DequeInteger stacknew LinkedList();System.out.println(栈为空:stack.isEmpty()); //判断栈是否为空stack.addFirst(12);//添加元素System.out.println(stack.peekFirst()); //获取栈顶元素System.out.println(stack.pollFirst()); //获取并移除栈顶元素}
小提示 在Deque中获取并移除元素的方法有两个分别是removeXxx以及peekXxx。 存在元素时两者的处理都是一样的。 但是当Deque内为空时removeXxx会直接抛出NoSuchElementException 而peekXxx则会返回null。 所以无论在实际开发或者算法时推荐使用peekXxx方法。 其实ArrayDeque和LinkedList都可以作为栈以及队列使用但是从执行效率来说ArrayDeque作为队列以及LinkedList作为栈使用会是更好的选择。
注意 ArrayDeque 是 Deque 接口的一种具体实现是依赖于可变数组来实现的。ArrayDeque 没有容量限制可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用效率要高于 Stack。ArrayDeque 也可以作为队列来使用效率相较于基于双向链表的 LinkedList 也要更好一些。注意ArrayDeque 不支持为 null 的元素。之后再说为什么建议使用ArrayDeque而不是LinkedList: 链表比数组花费更多空间 链表的随机访问性质比数组差虽然这个对栈来说问题不大 链表的每次插入和删除都涉及到一个节点对象的创建和弃用非常低效和浪费空间而动态数组几乎是0花费的(数组充满时重新拷贝除外) 链表是非连续的访问时候不能充分利用cpu cache
所以无论是栈还是队列JDK都是建议使用ArrayDeque而不是LinkedList实现ArrayDeque比较复杂的一点就是需要指定初始大小当然你不指定也行。但是它的效率确实是比LinkedList高的
小结 PriorityQueue可以作为堆使用而且可以根据传入的Comparator实现大小的调整会是一个很好的选择。 ArrayDeque可以作为栈或队列使用但是栈的效率不如LinkedList高通常作为队列使用。 LinkedList可以作为栈或队列使用但是队列的效率不如ArrayQueue高通常作为栈使用。
Queue和Deque的方法区别 在java中Queue被定义成单端队列使用Deque被定义成双端队列使用。 而由于双端队列的定义Deque可以作为栈或者队列使用 而Queue只能作为队列或者依赖于子类的实现作为堆使用。 方法上的区别如下 add offer add 底层调用offer 无区别 remove 无元素 抛出异常 poll 返回null 删除元素 peek element 不删除元素 element 无元素 抛出异常peek 返回null
LinkedList与ArrayDeque在栈与队列中的使用
LinkedList
增加 add(E e)在链表后添加一个元素 通用方法 addLast(E e)在链表尾部添加一个元素 特有方法 offer(E e)在链表尾部插入一个元素 offerLast(E e)JDK1.6本之后在尾部添加 特有方法
特点add 与 addLast 一个有返回值 boolean一个无 offer 与 add 与 offerLast 一样
addFirst(E e)在链表头部插入一个元素 特有方法 offerFirst(E e)JDK1.6版本之后在头部添加 特有方法
特点offerFirst 有返回值 addFirst无 add(int index, E element)在指定位置插入一个元素。
删除 remove() 移除链表中第一个元素; 通用方法 removeFirst() 移除第一个元素 pollFirst()删除头 特有方法 pop()和removeFirst方法一致删除头。 poll()查询并移除第一个元素 特有方法
特点remove 抛异常poll 返回null pop 与 removeFirst remove一致 remove(E e)移除指定元素 通用方法 removeFirst(E e)删除头获取元素并删除 特有方法 removeLast(E e)删除尾 特有方法
pollLast()删除尾 特有方法
查 poll()查询并移除第一个元素 特有方法 pollFirst()查询并删除头 特有方法 getFirst()获取第一个元素 特有方法 peek()获取第一个元素但是不移除 特有方法 peekFirst()获取第一个元素但是不移除
特点poll 弹出数据无数据返回null getFirst 无数据 抛出异常, peek 返回数据无数据返回null getLast()获取最后一个元素 特有方法 peekLast()获取最后一个元素但是不移除 pollLast()删除尾 特有方法 get(int index)按照下标获取元素 通用方法
ArrayDeque 特点 ArrayDeque实现了Deque接口。可当作栈来用效率高于stack。也可当作队列来用效率高于LinkedList。 底层用可变数组实现无容量限制。 ArrayDeque是不安全的。
增加: addFirst(E e)在数组前面添加元素 addLast(E e)在数组后面添加元素 offerFirst(E e)在数组前面添加元素并返回是否添加成功 offerLast(E e)在数组后添加元素并返回是否添加成功 push(E e)与addFirst方法一致 offer(E e)在链表尾部插入一个元素
删除 removeFirst()删除第一个元素并返回删除元素的值如果为null将抛出异常 removeLast()删除最后一个元素并返回删除元素的值如果为null,将抛出异常 pollFirst()删除第一个元素并返回删除元素的值如果为null将返回null pollLast()删除最后一个元素并返回删除元素的值如果为null,将返回null
pop()和removeFirst方法一致删除头。 poll()查询并移除第一个元素 特有方法
查 getFirst()获取第一个元素如果为null将抛出异常 getLast()获取最后一个元素如果为null将抛出异常 peek()获取第一个元素但是不移除 特有方法
注意 add() 和 offer()的区别 在容量已满的情况下add() 方法会抛出IllegalStateException异常offer() 方法只会返回 false remove方法和poll方法都是删除队列的头元素remove方法队列为空的情况下将抛异常而poll方法将返回null element和peek方法都是返回队列的头元素但是不删除头元素区别在与element方法在队列为空的情况下将抛异常而peek方法将返回null。
