「java实现双端队列」编写算法实现双端队列
本篇文章给大家谈谈java实现双端队列，以及编写算法实现双端队列对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
到底什么是消息队列？Java中如何实现消息队列
“消息队列”是在消息的传输过程中保存消息的容器。和我们学过的LinkedHashMap，TreeSet等一样，都是容器。既然是容器，就有有自己的特性，就像LinkedHashMap是以键值对存储。存取顺序不变。而消息队列，看到队列就可以知道。这个容器里面的消息是站好队的，一般遵从先进先出原则。
java中已经为我们封装好了很多的消息队列。在java 1.5版本时推出的java.util.concurrent中有很多现成的队列供我们使用。特性繁多，种类齐全。是你居家旅游开发必备QAQ。
下面简单列举这个包中的消息队列
:阻塞队列 BlockingQueue
数组阻塞队列 ArrayBlockingQueue
延迟队列 DelayQueue
链阻塞队列 LinkedBlockingQueue
具有优先级的阻塞队列 PriorityBlockingQueue
同步队列 SynchronousQueue
阻塞双端队列 BlockingDeque
链阻塞双端队列 LinkedBlockingDeque
不同的队列不同的特性决定了队列使用的时机，感兴趣的话你可以详细了解。具体的使用方式我就不赘述了
Java：双端队列插入节点，关于队列为空时插入节点的疑问
队列为空的情况下 在首部添加新节点的时候，其实firstNode和lastNode相同都是newNode
，但是无论队列是否为空 方法的最后都会设置firstNode=newNode， 所以为空的时候会设置lastNode=newNode； 在尾部添加新节点的道理也是这样；
ArrayDeque
写cs61b题目时惊叹为什么会有这种东西，于是搜索了一番，发现这容器还是很有意思的，于是搬运了一下。
参考： ArrayDeque - (jianshu.com)
Java ArrayDeque - Java教程 - 菜鸟教程 (cainiaojc.com)
在ArrayDeque类实现这两个接口：Java Queue和Java Deque
使用了数组来存储数据，同时用两个int值 head 和 tail 来表示头部和尾部。不过需要注意的是 tail 并不是尾部元素的索引，而是尾部元素的 下一位 ，即下一个将要被加入的元素的索引。
ArrayDeque 有三个构造函数来初始化，除了无参的构造函数使用了默认容量，其它两个构造函数会通过 allocateElements 函数来计算初始容量
数组的大小很特殊，大小必为2的n次方（2^n）。下面我们看看 allocateElements 方法
(1)对于一个小于2^30的值，经过五次右移和位或操作后，可以得到一个 2^k - 1 的值。最后再将这个值 +1 ，得到 2^k 。通过这个方法，可以将一个任意的初始值转化为2^n的值.
(2)不过有一点不足在于，如果本身传进来的值就是 2^n 的值，那么经过转化会变成 2^(n+1) ，所以我们在不用刻意去传入 2^n 的值。
(3)如果传入的值大于等于 2^30 ，那么经过转化会变成负值，即 0，此时会把初始值设置为 2^30 ，即最大的容量只有 2^30
在ArrayDeque中，数组是作为环形来使用的，正常情况下在末尾添加元素后，tail=tail+1是要判断是否越界，如果越界，会变为从索引0开始。参考如下图片，当H添加到索引7后，tail值会+1,此时tail=8，但是越界了，所以应该将tail设置为0。
我们看看 tail = (tail + 1) (elements.length - 1) 的正确性：
所以当 tail+1 = length - 1 ，此时数组并没有越界， (tail + 1) (elements.length - 1) 后得到的还是 tail+1 。如果 tail + 1 = length ，此时数组越界了， (tail + 1) (elements.length - 1) 后得到0。
所以通过 (tail + 1) (elements.length - 1) 可以跳过条件判断在环形数组中获取正确的索引值，然后再判断新的 tail 是否等于 head ，如果结果为 true ，那么数组已经满了，需要扩容，即 doubleCapacity() 。
原理和addLast相同
无论是从头部还是从尾部添加元素，都会判断 tail==head ，如果两个索引相遇，说明数组空间已满，需要扩容操作.
ArrayDeque支持从头尾两端移除元素
在上文中，我们讲了怎么去实现一个ArrayDeque，但Java标准库中已经为我们准备好了，我们只需按规则使用就行
add() - 将指定的元素插入ArrayDeque双端队列的 末尾
addFirst() -在ArrayDeque双端队列的 开头 ，插入指定的元素
addLast() - 在ArrayDeque双端队列的 末尾 插入指定的内容（等效于 add() ）
注意：如果ArrayDeque双端队列已满，则所有这些方法 add() ， addFirst() 和 addLast() 都会引发IllegalStateException
offer() - 将指定的元素插入ArrayDeque双端队列的 末尾
offerFirst() - 在ArrayDeque双端队列的 开始处 插入指定的元素
offerLast() - 将指定的元素插入ArrayDeque双端队列的 末尾
注意： offer()，offerFirst()并offerLast()返回true是否成功插入元素；否则，返回。如果ArrayDeque双端队列已满，则这些方法返回false。
getFirst() - 返回ArrayDeque双端队列的 第一个元素
getLast() - 返回ArrayDeque双端队列的 最后一个元素
注：如果ArrayDeque双端队列为空，getFirst()和getLast()抛出NoSuchElementException。
peek() - 返回ArrayDeque双端队列的 第一个 元素
peekFirst() - 返回ArrayDeque双端队列的 第一个 元素（等效于 peek() ）
peekLast() - 返回ArrayDeque双端队列的 最后一个 元素
注：如果ArrayDeque双端队列为空，peek()，peekFirst()和getLast()抛出 NoSuchElementException
remove() - 返回并从ArrayDeque双端队列的 第一个 元素中删除一个元素
remove(element) - 返回并从ArrayDeque双端队列的 头部 删除指定的元素
removeFirst() - 返回并从ArrayDeque双端队列中删除 第一个 元素（等效于remove()）
removeLast() - 返回并从ArrayDeque双端队列中删除 最后一个元素
注意：如果数组双端队列为空，则remove()，removeFirst()和removeLast()方法将引发异常。 另外，如果找不到元素，则remove(element)会引发异常。
poll() - 返回并删除ArrayDeque双端队列的 第一个 元素
pollFirst() - 返回并删除ArrayDeque双端队列的 第一个 元素（等效于poll()）
pollLast() - 返回并删除ArrayDeque双端队列的 最后一个 元素
注意：如果ArrayDeque双端队列为空，则如果找不到该元素，则poll()，pollFirst()和pollLast()返回null。
删除所有元素
iterator() - 返回可用于遍历ArrayDeque双端队列的 迭代器
descendingIterator() -返回一个迭代器，该迭代器可用于以 相反顺序 遍历ArrayDeque双端队列
注：为了使用这些方法，我们必须导入java.util.Iterator包。
使用迭代器的方法如下
element() -从ArrayDeque双端队列的头部返回一个元素。
contains(element) -在ArrayDeque双端队列中搜索指定的元素。如果找到该元素，则返回true，否则返回false。
size() -返回ArrayDeque双端队列的长度。
toArray() -将ArrayDeque双端队列转换为数组并返回。
clone() -创建ArrayDeque双端队列的副本并返回它。
push() - 在堆栈顶部添加一个元素
peek() - 从堆栈顶部返回一个元素
pop() - 返回并从堆栈顶部删除元素
java实现双端队列的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于编写算法实现双端队列、java实现双端队列的信息别忘了在本站进行查找喔。
发布于：2022-11-23，除非注明，否则均为原创文章，转载请注明出处。