Java集合篇之深度解析Queue，单端队列、双端队列、优先级队列、阻塞队列

JavaBuild

发布于 2024-05-27 14:18:41

1020

发布于 2024-05-27 14:18:41

文章被收录于专栏：JavaBuild888JavaBuild888

写在开头

队列是Java中的一个集合接口，之前的文章已经讲解了List和Set，那么今天就来唠一唠它吧。队列的特点：存储的元素是有序的、可重复的。

队列的两大接口Queue vs Deque

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
删除队首	removeFirst()	pollFirst()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

ArrayDeque

作为双端队列的实现类，是基于可变长的数组和双指针来实现，常常被用于实现栈功能，以此来替代曾经那个笨拙的Stack。

【代码示例1】

 // 创建一个ArrayDeque
        ArrayDeque<String> deque = new ArrayDeque<>();

        // 添加元素
        deque.add("a");
        deque.add("b");
        deque.add("c");

        // 删除元素
        deque.remove("b");

        // 修改元素
        deque.remove("b");
        deque.add("bb");

        // 查找队首元素
        System.out.println(deque.getFirst());
        //查找队尾元素
        System.out.println(deque.getLast());
        //遍历队列
        for (String s : deque) {
            System.out.print(s);
        }

输出：

a
bb
acbb

PriorityQueue

作为Queue的子类，它的特点是元素出队顺序是与优先级相关，利用二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据，默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

【代码示例2】

public class Test {
    public static void main(String[] args) {
        // 创建 PriorityQueue 对象
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        // 添加元素到 PriorityQueue
        priorityQueue.offer(3);
        priorityQueue.offer(2);
        priorityQueue.offer(1);
        priorityQueue.offer(4);
        priorityQueue.offer(5);
        priorityQueue.offer(6);

        // 打印 PriorityQueue 中的元素
        System.out.println("PriorityQueue 中的元素：");
        while (!priorityQueue.isEmpty()) {
            System.out.print(priorityQueue.poll() + " ");
        }
    }
}

输出：

PriorityQueue 中的元素：
1 2 3 4 5 6

因为队列中的元素是通过小顶堆方式来确定优先级的，而小顶堆是一个完全二叉树，这就导致的队列输出为排序后的结果。等我们学到了数据结构时再详细说一下哈。

BlockingQueue

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。应用场景：生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。