本文主要是介绍Java 队列Queue从原理到实战指南，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
《Java队列Queue从原理到实战指南》本文介绍了Java中队列（Queue）的底层实现、常见方法及其区别,通过LinkedList和ArrayDeque的实现,以及循环队列的概念,展示了如何高效...
一、队列的认识
队列的底层与集合框架
在 Java 中，队列（Queue）是集合框架的一部分，属于 java.util 包下的接口。
从底层实现来看，不同的队列实现类底层数据结构不同。但是主要是由链表和数组实现的.LinkedList 实现了 Queue 接口，它底层基于双向链表，通过节点的链接来维护队列的先进先出（FIFO）特性，插入和删除元素时效率较高.ArrayDeque 则底层基于数组，利用数组的索引操作来模拟队列，在首尾操作元素时也能有较好的性能。
集合框架为队列提供了统一的接口规范，让开发者能方便地使用队列的各种操作，如入队（offer）、出队（poll）、查看队首元素（peek）等，同时也能结合集合框架中的其他类和接口，实现更复杂的数据结构和算法操作。
java集合框架
常见的队列方法
- queue(栈)中在java中常见的方法有add,offer .remove,poll .element , peek.他们两两一组,又有不同的次重点.
- 这几个方法都是Java中
Queue接口定义的方法，它们的不同点主要体现在操作失败时的表现以及方法用途侧重方面：
插入元python素方法对比（add和offer）
add(E e)：- 操作失败时的表现：如果试图将元素添加到一个容量固定且已满的队列中，会抛出
IllegalStateException异常。例如，当使用ArrayDeque创建一个固定大小的队列，并且队列已经达到最大容量时，调用add方法添加元素就会触发异常。 - 用途侧重：适用于在程序中能明确保证队列不会满的场景，或者希望在队列满时以异常形式来中断程序流程，从而进行错误处理的情况。
- 操作失败时的表现：如果试图将元素添加到一个容量固定且已满的队列中，会抛出
offer(E e)：- 操作失败时的表现：当尝试将元素添加到已满的队列中，不会抛出异常，而是返回
false。比如在实现一个任务队列，当队列满时，不希望程序因为添加任务失败而崩溃，此时可以使用offer方法，通过返回值来判断任务是否成功添加。 - 用途侧重：更适合在日常开发中，不确定队列是否已满的场景，通过返回值来灵活处理添加操作的结果。
- 操作失败时的表现：当尝试将元素添加到已满的队列中，不会抛出异常，而是返回
移除元素方法对比（remove和poll）
remove()：- 操作失败时的表现：如果从空队列中移除元素，会抛出
NoSuchElementException异常 。比如在编写一个处理消息队列的程序时，没有提前检查队列是否为空就直接调用remove方法，当队列为空时就会引发异常。 - 用途侧重：适用于能确保队列非空的场景，或者希望以异常的方式来处理空队列情况，提醒开发者进行相应的错误处理。
- 操作失败时的表现：如果从空队列中移除元素，会抛出
poll()：- 操作失败时的表现：从空队列中移除元素时，不会抛出异常，而是返回
null。例如，在循环处理队列元素时，可以使用poll方法，通过判断返回值是否为null来确定是否已经处理完所有元素，进而结束循环。 - 用途侧重：在不确定队列是否为空的情况下使用更方便，通过返回值就能轻松判断操作结果，避免了繁琐的异常处理代码。
- 操作失败时的表现：从空队列中移除元素时，不会抛出异常，而是返回
查看队首元素方法对比（element和peek）
element()：- 操作失败时的表现：当试图从空队列中获取队首元素时，会抛出
NoSuchElementException异常 。例如，在一个多线程操作队列的场景中，没有做好同步控制，在队列为空时调用element方法就会出现异常。 - 用途侧重：适用于确定队列非空的场景，用于获取队首元素进行后续操作，并且希望以异常形式来处理空队列的情况。
- 操作失败时的表现：当试图从空队列中获取队首元素时，会抛出
peek()：- 操作失败时的表现：从空队列中获取队首元素时，不会抛出异常，而是返回
null。比如在一个定时检查队列头部元素的任务中，使用peek方法可以在不抛出异常的情况下，简单判断队列是否为空以及获取队首元素。 - 用途侧重：在不确定队列是否为空，又需要获取队首元素信息时，使用
peek方法更为合适，方便根据返回值进行后续逻辑处理。
- 操作失败时的表现：从空队列中获取队首元素时，不会抛出异常，而是返回
简单说就是
二、方法简单实现
Linkedlist实现
- 框架搭建
public class MyQueue {
// 使用LinkedList实现的队列，存储整数类型元素
// LinkedList实现了Queue接口，提供了队列的基本操作 向上转型
Queue<Integer> queue = new LinkedList<>();
//静态内部类
static class ListNode{
public int val;
public ListNode prev; //链表中的两个重要指向
public ListNode next;
public ListNode(int val){
//构造方法 用于实例化对象
this.val = val;
}
}
public ListNode first;
public ListNode last;
}- 工具代码
public boolean isEmpty(){
return first == null && last ==null;
}
public int size(){
int count = 0;
ListNode cur = first;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}- 尾差offer
public void offer(int val){
ListNode node = new ListNode(val);
if (isEmpty()){
first = last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
- 头删poll
public int poll(){
int val = first.val;
if (isEmpty()){
return -1;
}
if (first == last){
first = null;
last = null;
}else {
first = first.next;
first.prev = null;
}
return val;
}- 取顶pop
public int pop(){
if (isEmpty()){
return -1;
}
else {
return first.val;
}
}
- 核心思想
这里方法核心思想就是链表中指向的修改问题,在定义的first,last cur三个指向的修改思想.比如:
数组实现遇到的问题
- 数组的结构不像链表那样灵活,尤其是头删,我们的指针会不断的向后面进行,导致前面的内存浪费.
- 比如说;假设我们有一个固定大小的数组来模拟队列，设置队首指针 front 和队尾指针 rear，初始时都指向数组起始位置。当进行入队操作时，rear 不断后移；出队操作时，front 也不断后移。可这样一来，随着操作的进行，队列前面会逐渐出现空闲的空间，但因为 rear 已经到达数组末尾，我们却无法再利用这些前面的空闲空间，就好像队列 “假满” 了一样，明明数组还有空间，却无法继续入队新元素。
- 其次，当队列中的元素都出队后，front 和 rear 都指向了数组后面的位置，此时队列实际为空，但从指针位置看，却好像还有元素存在，这就给我们判断队列是否为空带来了困难。
- 为了解决这些问题，循环队列的概念就被引入了。循环队列把数组的首尾连接起来，形成一个环形的结构，让队首和队尾指针可以循环移动，从而充分利用数组的空间，也能更方便、准确地判断队列的空满状态。
三、引入循环队列
两个问题
从上面的图可以看出有两个棘手的问题
- 1.当入队的时候,rear不断向后,传统的思想就是每次有新的元素进队,我们使rear+1即可,但是当rear一个单位相邻front时候,我们再让下边+1就不是front(默认下表0)的下标了,头删问题同上.
- 2.我们应当如何判断队列是不是满的,而不是不同的覆盖添加.
如何正确表示下边(从尾部到头部)?
公式法(r + 偏移量) %http://www.chinasem.cn len(f + 偏移量) % len
如何判断队列满不满?
标记法
在rear = front (起始时) tip = !isFull标记一下,当下一次出现rear = front时, tip = isFull.不再进行插入
预留空间法
在循环队列中让rear的下一位就是front,即(reChina编程ar+1)http://www.chinasem.cn%len = front
预留空间法实现
代码示例
public class MyCircularQueue {
//预留空间法
//初始变量的定义
public int [] elem;
public int rear ;
public int front;
//构造方法进行初始化
public MyCircularQueue(int k){
this.elem = new int [k];
}
/****
* 入队
*/
public boolean enQueue(int val) {
//判满
if (isFull()) {
return false;
}
elem[rear] = val;
rear = (rear + 1) % elem.length;
return true;
}
//出队
public boolean deQueue (){
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
return true;
}
/****
* 返回头
* @return
*/
public int getFront(){
if (isEmpty()){
return -1;
}
return elem[front];
}
/****
* 返回尾
* @return
*/
public int getRear(){
if (isEmpty()){
return -1;
}
if (rear == 0)
return elem[elem.length-1];
//处理边界问题
}else {
return elem[rear-1];
}
}
public boolean isFull(){
//r的下一个是f
return (rear+1)%elem.length == front;
}
public boolean isEmpty(){
return front == rear;
}
}标记法实现
代码示例
public class MyCircularQueue {
//标记法
//初始变量的定义
public int [] elem;
public int rear ;
public int front;
//构造方法进行初始化
public MyCircularQueue(int k){
this.elem = new int [k];
}
private boolean isFull0 = false;
public boolean isFull2(){
//r的下一个是f
return isFull0;
}
public boolean isEmpty2(){
return front == rear && !isFull0;
}
//标记法
public boolean enQueue2(int val) {
//判满
if (isFull2()) { //一开始进不来
return false;
}
elem[rear] = val;
rear = (rear + 1) % elem.length;
//入队后判断是不是满了
if (rear == front) {
isFull0 = true;
}
return true;
}
//出队
public boolean deQueue2 (){
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
isFull0 = false;
return true;
}
}四、实战应用(见<历练场>)
队列实现栈
栈实现队列
总结
好啦,到这里我们队列的知识就分享到这里了，谢谢大家的阅读。如有问题请直接指出。
到此这篇关于Java 队列Queue从原理到实战指南的文章就介绍到这了,更多相关java 队列queue内容请搜索编程China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持China编程(www.chinasem.cn)！
这篇关于Java 队列Queue从原理到实战指南的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
