怡格网 | 详情

1. Queue接口

Queue是 Java 集合框架中的一个接口，继承自Collection接口。它代表一个先进先出（FIFO）的数据结构，即最先进入队列的元素最先被移除。该接口定义了插入、移除和检查元素的操作，这些操作以两种形式存在：一种在操作失败时抛出异常，另一种返回特殊值（如null或false）。

常用方法

add(E e)：将指定元素插入队列，如果队列已满则抛出IllegalStateException。
offer(E e)：将指定元素插入队列，如果队列已满则返回false。
remove()：移除并返回队列的头部元素，如果队列为空则抛出NoSuchElementException。
poll()：移除并返回队列的头部元素，如果队列为空则返回null。
element()：返回队列的头部元素，但不移除，如果队列为空则抛出NoSuchElementException。
peek()：返回队列的头部元素，但不移除，如果队列为空则返回null。

常用实现类

LinkedList：它是一个双向链表实现的List和Deque接口，同时也实现了Queue接口。它可以作为队列使用，支持高效的插入和删除操作。
PriorityQueue：基于优先级堆实现的无界优先级队列。元素按照自然顺序或者指定的比较器进行排序，优先级最高的元素总是位于队列的头部。

应用场景

任务调度：例如在多线程编程中，使用队列来存储待执行的任务，线程从队列中取出任务并执行。
广度优先搜索（BFS）：在图的遍历算法中，使用队列来存储待访问的节点。

2. Deque接口

Deque是Queue的子接口，代表双端队列（Double Ended Queue）。它允许在队列的两端进行插入、移除和检查元素的操作，因此既可以作为先进先出（FIFO）队列使用，也可以作为后进先出（LIFO）栈使用。

常用方法

除了继承自Queue的方法外，Deque还提供了在队列两端进行操作的方法：

addFirst(E e)：在双端队列的头部插入指定元素。
addLast(E e)：在双端队列的尾部插入指定元素。
offerFirst(E e)：在双端队列的头部插入指定元素，如果成功则返回true。
offerLast(E e)：在双端队列的尾部插入指定元素，如果成功则返回true。
removeFirst()：移除并返回双端队列的第一个元素。
removeLast()：移除并返回双端队列的最后一个元素。
pollFirst()：移除并返回双端队列的第一个元素，如果队列为空则返回null。
pollLast()：移除并返回双端队列的最后一个元素，如果队列为空则返回null。
getFirst()：返回双端队列的第一个元素，但不移除。
getLast()：返回双端队列的最后一个元素，但不移除。
peekFirst()：返回双端队列的第一个元素，但不移除，如果队列为空则返回null。
peekLast()：返回双端队列的最后一个元素，但不移除，如果队列为空则返回null。

常用实现类

LinkedList：同样是Deque接口的一个常用实现，支持在队列两端进行高效的插入和删除操作。
ArrayDeque：基于数组实现的双端队列，不允许存储null元素。它在性能上通常比LinkedList更高效，特别是在作为栈或队列使用时。

应用场景

栈和队列的实现：由于Deque既可以作为栈使用（后进先出），也可以作为队列使用（先进先出），因此可以方便地实现栈和队列的数据结构。
滑动窗口算法：在处理数组或列表时，使用双端队列来维护一个固定大小的窗口，以实现高效的滑动窗口操作。

示例代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;
import java.util.ArrayDeque;

public class QueueDequeExample {
    public static void main(String[] args) {
        // 使用 LinkedList 作为 Queue
        Queue<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

        // 使用 ArrayDeque 作为 Deque
        Deque<String> deque = new ArrayDeque<>();
        deque.offerFirst("X");
        deque.offerLast("Y");
        deque.offerFirst("Z");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }
    }
}

这个示例展示了如何使用LinkedList作为Queue和使用ArrayDeque作为Deque，并进行基本的插入和移除操作。