java基础队列



1. 什么是队列？

• 具有“先进先出”特性的线性结构；

• 基本操作：判空、判满、添加（队尾）、删除（队头）、获取队头元素、获取队列大小；

• 双端队列（即可在两端分别进行添加删除操作）；

• 优先队列（按优先级排列，增删操作也基于优先级）。

2. Java中常见的队列实现

(1). ArrayList：将列表作为队列使用，add()在队尾添加元素，remove(0)删除队头，但会导致后续大量元素的移动，对于有许多增删操作的情况性能较差，适用于查找和修改需求大的情况。

(2). LinkedList：实现了Queue接口、Deque接口、List接口，offer()在队尾添加元素，poll()删除队头并返回，使用指针链接元素，对增删操作有较好的性能，无需移动元素。

 (3). ArrayBlockingQueue：有界阻塞队列，有固定容量，创建时需要指定队列的大小，底层基于数组实现，在增删元素时可能会阻塞线程，直到满足特定的条件。

阻塞队列继承Queue接口,与（1）、（2）中的普通队列的不同之处在于：阻塞添加和阻塞删除方法。

• 阻塞添加：当阻塞队列元素已满时，队列会阻塞加入元素的线程，将线程放入notFull等待队列中，直到队列元素不满时才重新唤醒线程执行元素加入操作。

put(E e)：将元素插入队列的尾部，如果该队列已满，则一直阻塞

• 阻塞删除：当阻塞队列元素为空时，删除队列元素的线程将被阻塞，直到队列不为空再执行删除操作(通常会返回被删除的元素)。

take()：获取并删除队头元素，若队列为空，则一直阻塞；

(4). LinkedBlockingQueue：可选有界/无界阻塞队列，底层基于链表实现。

(5). PriorityBlockingQueue：支持优先级的无界阻塞队列，元素按照其优先级顺序被增加和删除，内部使用堆算法保证每次出队都是优先级最高的元素。

(6). ConcurrentLinkedQueue：无界非阻塞队列，适用于多线程，提供了高效的并发操作，底层基于链表实现。

3. Queue接口

继承自Collection接口，代表一个先进先出的队列。Queue接口的常见实现类包括LinkedList、ArrayDeque和PriorityQueue等。

(1). 添加元素：

• boolean add(E e): 将指定元素添加到队列的尾，若成功则返回true，若队列已满则抛出 IllegalStateException 异常。
• boolean offer(E e): 将指定元素添加到队列末尾，若成功则返回true，若队列已满则返回false。

(2). 删除元素：

• E remove(): 删除并返回队头元素，若成功返回true，队列为空失败返回false。
• E poll(): 删除并返回队头元素，若队列为空则返回null。

(3). 获取队头元素：

• E element(): 获取队头元素，但不移除，若队列为空则抛出 NoSuchElementException 异常。
• E peek(): 获取队头元素，但不移除，若队列为空则返回null。

(4). 队列大小：

• int size(): 返回队列中的元素个数。

(5). 队列判空：

• boolean isEmpty(): 判断队列是否为空。

(6). 清空队列：

• clear()：清空队列中的所有元素

(7). 是否包含某个元素：

• contains(Object o)：判断队列中是否包含指定元素。

4. Deque接口：

双端队列，继承自Queue接口，在其基础上提供了在队列两端添加、删除和检索元素的操作。也可以作为栈使用（push()、pop()、peek()）。

Deque接口的常见实现类包括ArrayDeque和LinkedList。

(1). 添加元素：

• void addFirst(E element): 将指定元素添加到队头。
• void addLast(E element): 将指定元素添加到队尾。
• boolean offerFirst(E element): 将指定元素添加到队头，成功返回true，若队列已满返回false。
• boolean offerLast(E element): 将指定元素添加到队尾，成功返回true，若队列已满返回false。

(2). 删除元素：

• E removeFirst(): 删除并返回队头元素，若队列为空则抛出 NoSuchElementException 异常。
• E removeLast(): 删除并返回队尾元素，若队列为空则抛出 NoSuchElementException 异常。
• E pollFirst(): 删除并返回队头元素，若队列为空则返回null。
• E pollLast(): 删除并返回队尾元素，若队列为空则返回null。

(3). 获取队头元素：

• E getFirst(): 获取队头元素，但不移除，若队列为空则抛出 NoSuchElementException 异常。
• E getLast(): 获取队尾元素，但不移除，若队列为空则抛出 NoSuchElementException 异常。
• E peekFirst(): 获取队头元素，但不移除，若队列为空则返回null。
• E peekLast(): 获取队尾元素，但不移除，若队列为空则返回null。

(4). 队列大小：

• int size(): 返回队列中的元素个数。

(5). 队列判空：

• boolean isEmpty(): 判断队列是否为空。

(6). 清空队列：

• clear()：清空队列中的所有元素

(7). 是否包含某个元素：

• contains(Object o)：判断队列中是否包含指定元素。

 5. 优先队列

PriorityQueue基于二叉堆实现，是特殊的完全二叉树，具有最小堆性质（每个节点值均小于其孩子节点值，根节点最小）。

PriorityQueue使用数组存储元素，按照优先级排列，根节点索引下标为0，任意结点的索引为i，它的左孩子节点索引为2i+1，右孩子索引2i+2，父节点索引(i - 1) / 2。

        1. 当元素被添加到PriorityQueue时，它会被放置在数组的末尾，并按照以下步骤进行调整，以维护最小堆的性质，使得具有最高优先级的元素总是位于队列的头部：

• 上滤（Up-Heap）操作：新插入的元素与其父节点比较。如果新插入的元素的优先级比父节点的优先级高，则它会与父节点进行交换，直到满足最小堆的性质。

        2. 当从PriorityQueue中删除元素时，队列头部的元素被移除，并将数组的最后一个元素移动到头部位置。然后，这个元素会与其子节点进行比较，以保持最小堆的性质。

• 下滤（Down-Heap）操作：被移动到头部位置的元素与其子节点比较。如果它的优先级比其中一个或两个子节点的优先级低，则它会与其中较小的子节点进行交换。这个过程会递归地向下进行，直到满足最小堆的性质。

PriorityQueue允许元素具有相同java基础队列的优先级，但它们的顺序不一定确定，可能会以任意顺序被取出。

PriorityQueue的插入和删除操作的时间复杂度都是O(logN)，N为队列中的元素个数。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/25337.html