当前位置：首页 > article >正文

Java队列详细解释

article 2024/11/15 8:41:01

队列

一、什么是队列（Queue）

    ```java
    队列是一种线性数据结构，它的特点是先进先出。在队列中，元素的添加（入队）操作在队尾进行，而元素的移除（出队）操作则在队头进行。因此，队列可以被简单地描述为一个“先进先出”的容器。在Java中，队列接口继承自Collection接口，并提供了丰富的方法来操作队列中的元素
    ```

Java 的队列主要通过 java.util.Queue 接口及其子接口和实现类来定义和使用。根据不同的特性和用途，队列可以分为以下几类：

普通队列（FIFO 队列）
双端队列（Deque）
优先级队列（Priority Queue）

阻塞队列（Blocking Queue）

提供阻塞操作，当队列为空时，获取元素的线程会等待；当队列已满时，添加元素的线程会等待。
常用于生产者-消费者模式。

同步队列（Synchronous Queue）

SynchronousQueue 本质上是一个没有容量的队列，每个插入操作必须等待一个对应的移除操作，反之亦然。它常用于线程之间的直接交换数据。
不存储元素:
每个 put 必须等待一个 take，每个 take 必须等待一个 put。

如下：普通队列

在这里插入图片描述

在 Java 中，Queue 是 java.util 包下的一个接口，继承自 Collection 接口。Queue 定义了基本的队列操作方法，如添加、删除和查看元素。Queue 接口不能被直接实例化，但 Java 提供了多个实现类，例如 LinkedList、PriorityQueue、ArrayDeque 等。

在这里插入图片描述

从上面类的继承关系图可以看到Queue是一个接口，它的内部主要定义了以下几个方法：

二、常用方法

在这里插入图片描述

1.offer( )和add( )方法的区别

Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.offer("B");
// 队列中的元素：[A, B]

对于offer()：往队列添加元素。在不违反容量限制的情况下立即执行，将指定的元素插入到队列中。如果队列已满直接返回false，队列未满则直接插入并返回true；
对于add()：如果队列已满，抛出异常IllegalStateException。

2.poll( )和remove( )方法的区别

Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
String headElement = queue.remove();
// headElement 的值为 "A"，队列中的元素：[B]

对于poll()：检索并删除此队列的头，如果此队列为空，则返回 null ；
对于remove()：检索并删除此队列的头。此方法与poll不同之处在于，如果此队列为空，它将抛出异常。

3.peek()和element( )方法的区别

Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
String headElement = queue.element();
// headElement 的值为 "A"，队列中的元素：[A, B]

对于peek()：检索但不删除此队列的头部，如果此队列为空，则返回 null ;
对于element()：检索但不删除这个队列的头。此方法与peek的不同之处在于，如果此队列为空，它将抛出异常。

三、Java 中队列的实现类

Java 提供了多个 Queue 接口的实现，每种实现类都有不同的特点和应用场景。

1. `LinkedList`

LinkedList 类实现了 Queue 接口，并且可以作为队列使用。它是一个双向链表，支持队列的基本操作。LinkedList 适合频繁的插入和删除操作。

特点：
- 动态大小，插入和删除操作性能较好。
代码示例：

import java.util.LinkedList;
import java.util.Queue;

public class LinkedListQueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();//多态
        // 添加元素
        queue.add("A");
        queue.add("B");
        queue.add("C");
        // 查看队列头部元素
        
        System.out.println("Queue head: " + queue.peek());
        // 移除元素
        
        System.out.println("Removed: " + queue.remove());

        // 查看队列内容
        System.out.println("Queue content: " + queue);
    }
}

输出：

Queue head: A
Removed: A
Queue content: [B, C]

2. `PriorityQueue` 优先级队列

PriorityQueue 是一个基于堆的优先队列实现，它不会遵循普通的先进先出（FIFO）规则，而是根据元素的 优先级 来确定出队顺序。默认情况下，它是最小堆，即每次移除的是队列中的最小元素。

特点：
- 不保证元素的顺序，插入元素根据优先级调整。
- 插入元素时间复杂度为 O(log n)，移除元素时间复杂度为 O(log n)。
代码示例：

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>();

        // 添加元素
        queue.add(5);
        queue.add(2);
        queue.add(8);
        queue.add(1);

        // 移除并查看元素
        while (!queue.isEmpty()) {
            System.out.println("Removed: " + queue.poll());
        }
    }
}

输出：

Removed: 1
Removed: 2
Removed: 5
Removed: 8

优先级案例

public class Task implements Comparable<Task> {
    private String name;
    private int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() {
        return name;
    }

    public int getPriority() {
        return priority;
    }

    @Override
    public int compareTo(Task other) {
        return other.getPriority() - this.getPriority();
    }
}

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Task> queue = new PriorityQueue<>();
        queue.add(new Task("Task 1", 5));
        queue.add(new Task("Task 2", 3));
        queue.add(new Task("Task 3", 10));
        queue.add(new Task("Task 4", 15));
        queue.add(new Task("Task 5", 1));
        while (!queue.isEmpty()) {
            Task task = queue.poll();
            String name = task.getName();
            System.out.println("Executing task: " + name);
        }
    }

}

添加元素时调用 compareTo 的原因
PriorityQueue 内部使用了 堆排序，通常是二叉堆，这是一种可以快速找到最大值或最小值的数据结构。在向堆中添加元素时，堆需要重新排序，以保持其“堆性质”。为了决定新元素应该放在什么位置，它必须和其他元素进行比较，而这个比较就是通过 compareTo 方法来完成的。

hashCode() 和 equals() 通常一起重写，以确保两个相等的对象有相同的哈希码。如果对象被放入某些数据结构，如 HashSet 或作为键在 HashMap 中时，Java 会先调用 hashCode() 来确定它们的位置，然后通过 equals() 来判断对象的相等性。尽管 PriorityQueue 本身不使用 hashCode()，但如果你在这些数据结构中存储 Task 对象，hashCode() 将会被调用。

3. `ArrayDeque`

ArrayDeque 是 Deque 接口的实现类，可以用作双端队列或栈。作为队列时，它比 LinkedList 更加高效。ArrayDeque 使用动态数组来存储元素，能够支持双端的插入和删除操作。

特点：

无大小限制的双端队列，能够从两端插入和删除元素。

1. 作为栈使用（后进先出 - LIFO）

使用 ArrayDeque 可以模拟栈的操作，常见的方法包括：

push(E e)：将元素压入栈顶。
pop()：弹出栈顶元素。
peek()：查看栈顶元素但不移除。

import java.util.ArrayDeque;

public class StackExample {
    public static void main(String[] args) {
        ArrayDeque<String> stack = new ArrayDeque<>();

        // 模拟栈操作
        stack.push("Element 1");
        stack.push("Element 2");
        stack.push("Element 3");

        // 查看栈顶元素
        System.out.println("Top of the stack: " + stack.peek());  
        // 输出 "Element 3"
        // 弹出栈顶元素
        System.out.println("Popped: " + stack.pop()); 
        // 输出 "Element 3"
        System.out.println("Popped: " + stack.pop());  
        // 输出 "Element 2"

        // 再次查看栈顶
        System.out.println("Top of the stack: " + stack.peek()); 
        // 输出 "Element 1"
    }
}

2.作为队列使用（先进先出 - FIFO）

offer(E e)：将元素添加到队列尾部。

poll()：移除并返回队列头部的元素。

peek()：查看队列头部的元素但不移除。

代码示例：

import java.util.ArrayDeque;

public class QueueExample {
    public static void main(String[] args) {
        ArrayDeque<String> queue = new ArrayDeque<>();

        // 模拟队列操作
        queue.offer("Element 1");
        queue.offer("Element 2");
        queue.offer("Element 3");

        // 查看队列头部元素
        System.out.println("Front of the queue: " + queue.peek());  
        // 输出 "Element 1"

        // 移除队列头部元素
        System.out.println("Removed: " + queue.poll());  
        // 输出 "Element 1"
        System.out.println("Removed: " + queue.poll()); 
        // 输出 "Element 2"

        // 再次查看队列头部
        System.out.println("Front of the queue: " + queue.peek()); 
        // 输出 "Element 3"
    }
}

3.双端队列操作(简称Deque)

ArrayDeque 允许你在队列的两端进行操作，可以在头部或尾部添加和删除元素。

addFirst(E e) / addLast(E e)：在头部或尾部添加元素。

removeFirst() / removeLast()：移除并返回头部或尾部的元素。

import java.util.ArrayDeque;

public class DequeExample {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();

        // 在头部和尾部添加元素
        deque.addFirst("Element 1");
        deque.addLast("Element 2");
        deque.addFirst("Element 0");

        // 输出双端队列的内容
        System.out.println(deque);  
        // 输出 "[Element 0, Element 1, Element 2]"

        // 移除头部和尾部元素
        System.out.println("Removed from head: " + deque.removeFirst());  			// 输出 "Element 0"
        System.out.println("Removed from tail: " + deque.removeLast());  			// 输出 "Element 2"

        // 最终的队列状态
        System.out.println(deque);  // 输出 "[Element 1]"
    }
}

栈操作：push()、pop()、peek()。

队列操作：offer()、poll()、peek()。

双端队列操作：addFirst()、addLast()、removeFirst()、removeLast()。

四、阻塞队列（Blocking Queue）

常见实现类：
ArrayBlockingQueue
LinkedBlockingQueue
PriorityBlockingQueue
SynchronousQueue
DelayQueue
    
    
常用方法
    put(E e)	将元素 e 插入队列，若队列满则阻塞等待。
    take()	移除并返回队列头部元素，若队列为空则阻塞等待。	阻塞方法
    offer(E e)	尝试将元素 e 插入队列，若队列满则返回 false。

1.ArrayBlockingQueue

一个有界的阻塞队列，基于数组实现，按照 FIFO 顺序排列元素。

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ArrayBlockingQueueExample {
    public static void main(String[] args) throws InterruptedException {
     BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(3);
 3表示 阻塞队列的容量上限。也就是说，这个 LinkedBlockingQueue 最多只能存储 3 个元素。
        // 添加元素，使用 put 方法会阻塞直到有空间
        blockingQueue.put("Task 1");
        blockingQueue.put("Task 2");
        blockingQueue.put("Task 3");
        // blockingQueue.put("Task 4");  // 会阻塞，直到有空间

        // 查看队列内容
        System.out.println("Queue: " + blockingQueue);

        // 移除元素，使用 take 方法会阻塞直到有元素
        System.out.println("Taken: " + blockingQueue.take());  
        // 移除 "Task 1"
        System.out.println("Taken: " + blockingQueue.take()); 
        // 移除 "Task 2"

        // 添加新的元素
        blockingQueue.put("Task 4");

        // 最终队列内容
        System.out.println("Queue: " + blockingQueue);
    }
}

2.`LinkedBlockingQueue`

一个基于链表的阻塞队列，可以选择有界或无界。

import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class LinkedBlockingQueueExample {
    public static void main(String[] args) throws InterruptedException {
     BlockingQueue<String> blockingQueue = new LinkedBlockingQueue<>(5);

        // 添加元素
        blockingQueue.offer("Task A");
        blockingQueue.offer("Task B");
        blockingQueue.offer("Task C");

        // 查看队列内容
        System.out.println("Queue: " + blockingQueue);

        // 移除元素
        System.out.println("Removed: " + blockingQueue.poll()); 
        // 移除 "Task A"

        // 添加新元素
        blockingQueue.offer("Task D");

        // 最终队列内容
        System.out.println("Queue: " + blockingQueue);
    }
}

3.`PriorityBlockingQueue`

一个支持优先级排序的无界阻塞队列。

import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class PriorityBlockingQueueExample {
    public static void main(String[] args) throws InterruptedException {
BlockingQueue<Integer> priorityBlockingQueue =newPriorityBlockingQueue<>();

        // 添加元素
        priorityBlockingQueue.put(20);
        priorityBlockingQueue.put(10);
        priorityBlockingQueue.put(30);
        priorityBlockingQueue.put(5);

        // 按优先级顺序移除元素
        while (!priorityBlockingQueue.isEmpty()) {
            System.out.println(priorityBlockingQueue.take());
            // 输出顺序: 5, 10, 20, 30
        }
    }
}