• Java 集合之 Queue 和 Deque

    目录

    1、在Java中有哪些常见的队列？

    2、Queue 接口分析

    3、Deque 接口分析

    4、PriorityQueue 的实现原理详解

    5、使用Java数组实现队列的简单示例

    1、在Java中有哪些常见的队列？

            在Java中，有一些常见的队列实现。下面是其中一些的列举：//队列也是一种线性的数据结构

    1. ArrayList：ArrayList可以被用作队列，通过在列表末尾添加元素，并使用remove(0)方法从列表的开头删除元素。但是，由于在列表的开头删除元素会导致后续元素的移动，因此对于大量的插入和删除操作来说，ArrayList的性能可能不是最佳选择。
    2. LinkedList：LinkedList也可以用作队列。LinkedList实现了Queue接口，可以使用offer()方法在队列的末尾添加元素，使用poll()方法从队列的开头删除并返回元素。LinkedList对于插入和删除操作具有较好的性能，因为它使用了指针来链接元素，而不需要移动其他元素。
    3. ArrayBlockingQueue：ArrayBlockingQueue是一个有界阻塞队列，底层使用数组实现。它有一个固定的容量，并且在插入或删除元素时可能会阻塞线程，直到满足特定的条件。
    4. LinkedBlockingQueue：LinkedBlockingQueue是一个可选有界或无界的阻塞队列，底层使用链表实现。它具有类似于ArrayBlockingQueue的功能，但在内部实现上略有不同。
    5. PriorityBlockingQueue：PriorityBlockingQueue是一个支持优先级的无界阻塞队列。元素按照它们的优先级顺序被插入和删除。
    6. ConcurrentLinkedQueue：ConcurrentLinkedQueue是一个非阻塞无界队列，它适用于多线程环境。它使用链表实现，并且提供了高效的并发操作。

            以上是Java中的一些常见队列实现。具体选择哪种队列取决于你的需求和使用场景。

    2、Queue 接口分析

            Queue接口是Java集合框架中定义的一个接口，它代表了一个先进先出（FIFO）的队列。Queue接口继承自Collection接口，它定义了一组方法来操作队列中的元素。下面是Queue接口的一些主要方法和特性的详细解释：

    （1）添加元素：

    1. boolean add(E element): 将指定的元素添加到队列的末尾，如果成功则返回true，如果队列已满则抛出异常。
    2. boolean offer(E element): 将指定的元素添加到队列的末尾，如果成功则返回true，如果队列已满则返回false。

    （2）移除元素：

    1. E remove(): 移除并返回队列头部的元素，如果队列为空则抛出异常。
    2. E poll(): 移除并返回队列头部的元素，如果队列为空则返回null。

    （3）获取头部元素：

    1. E element(): 获取队列头部的元素，但不移除它，如果队列为空则抛出异常。
    2. E peek(): 获取队列头部的元素，但不移除它，如果队列为空则返回null。

    （4）队列大小：

    1. int size(): 返回队列中的元素个数。
    2. boolean isEmpty(): 判断队列是否为空。

            Queue接口还有一些其他方法，如clear()用于清空队列中的所有元素，contains(Object o)用于判断队列是否包含指定元素等。

            Queue接口的常见实现类包括LinkedList、ArrayDeque和PriorityQueue等。LinkedList实现了Queue接口，并且还可以作为栈使用，它是一个双向链表。ArrayDeque是一个双端队列，它同时实现了Queue和Deque接口。PriorityQueue是一个基于优先级的队列，它允许元素按照优先级顺序被插入和删除。

            通过使用Queue接口，我们可以方便地进行队列操作，如入队、出队、查看队列头部元素等。它在处理任务调度、消息传递等场景中非常有用。

            Java Queue接口使用示例：

            当使用Java中的Queue接口时，我们需要选择具体的实现类来创建一个队列对象。下面是一个使用Queue接口的示例，以LinkedList实现类为例：

    1. import java.util.Queue;
    2. import java.util.LinkedList;
    3.  
    4. public class QueueExample {
    5.     public static void main(String[] args) {
    6.         // 创建一个Queue对象
    7.         Queue<String> queue = new LinkedList<>();
    8.  
    9.         // 添加元素到队列
    10.         queue.add("Apple");
    11.         queue.add("Banana");
    12.         queue.add("Orange");
    13.  
    14.         // 获取队列头部元素
    15.         String head = queue.peek();
    16.         System.out.println("头部元素：" + head);
    17.  
    18.         // 遍历队列并输出元素
    19.         System.out.println("队列元素：");
    20.         for (String element : queue) {
    21.             System.out.println(element);
    22.         }
    23.  
    24.         // 移除队列头部元素
    25.         String removedElement = queue.remove();
    26.         System.out.println("移除的元素：" + removedElement);
    27.  
    28.         // 队列大小
    29.         int size = queue.size();
    30.         System.out.println("队列大小：" + size);
    31.  
    32.         // 判断队列是否为空
    33.         boolean isEmpty = queue.isEmpty();
    34.         System.out.println("队列是否为空：" + isEmpty);
    35.     }
    36. }

            在这个示例中，我们使用LinkedList作为实现类创建了一个Queue对象。我们向队列中添加了三个元素："Apple"，"Banana"和"Orange"。然后，我们使用peek()方法获取队列的头部元素，并使用for-each循环遍历队列并输出每个元素。

            接下来，我们使用remove()方法移除队列的头部元素，并使用size()方法获取队列的大小。最后，我们使用isEmpty()方法判断队列是否为空。

    3、Deque 接口分析

            Deque接口是Java集合框架中定义的一个接口，它代表了一个双端队列（Double Ended Queue）。Deque是"双端队列"的缩写。Deque接口继承自Queue接口，并在其基础上提供了在队列两端进行添加、删除和检索元素的操作。Deque可以在队列的头部和尾部同时进行元素的插入和删除，因此可以作为队列、栈或双向队列使用。

            Deque接口定义了以下主要方法和特性：

    （1）添加元素：

    1. void addFirst(E element): 将指定元素添加到双端队列的头部。
    2. void addLast(E element): 将指定元素添加到双端队列的尾部。
    3. boolean offerFirst(E element): 将指定元素添加到双端队列的头部，如果成功则返回true，如果队列已满则返回false。
    4. boolean offerLast(E element): 将指定元素添加到双端队列的尾部，如果成功则返回true，如果队列已满则返回false。

    （2）移除元素：

    1. E removeFirst(): 移除并返回双端队列的头部元素，如果队列为空则抛出异常。
    2. E removeLast(): 移除并返回双端队列的尾部元素，如果队列为空则抛出异常。
    3. E pollFirst(): 移除并返回双端队列的头部元素，如果队列为空则返回null。
    4. E pollLast(): 移除并返回双端队列的尾部元素，如果队列为空则返回null。

    （3）获取头部和尾部元素：

    1. E getFirst(): 获取双端队列的头部元素，但不移除它，如果队列为空则抛出异常。
    2. E getLast(): 获取双端队列的尾部元素，但不移除它，如果队列为空则抛出异常。
    3. E peekFirst(): 获取双端队列的头部元素，但不移除它，如果队列为空则返回null。
    4. E peekLast(): 获取双端队列的尾部元素，但不移除它，如果队列为空则返回null。

            Deque接口还提供了一些其他方法，如size()用于返回双端队列中的元素个数，isEmpty()用于判断双端队列是否为空，clear()用于清空双端队列中的所有元素等。

            Deque接口的常见实现类包括ArrayDeque和LinkedList。ArrayDeque是一个基于数组实现的双端队列，支持高效的随机访问和动态扩展。LinkedList是一个基于链表实现的双端队列，支持高效的插入和删除操作。

            通过使用Deque接口，我们可以方便地进行双端队列操作，如在队列的头部和尾部插入和删除元素，获取头部和尾部元素，以及判断队列是否为空。Deque在许多场景下都很有用，比如实现LRU缓存、实现任务调度等。

            另外，需要注意的是，Deque接口还可以用作栈（LIFO）的数据结构。通过在队列头部执行插入和删除操作，可以实现栈的功能。常见的栈操作可以使用Deque接口中的以下方法来实现：

    1. void push(E element): 将元素推入栈顶，等同于addFirst(E element)。
    2. E pop(): 弹出并返回栈顶元素，等同于removeFirst()。
    3. E peek(): 获取栈顶元素，等同于peekFirst()。

            所以，Deque接口是一个非常有用的接口，提供了双端队列的功能，既可以在队列的头部进行操作，也可以在尾部进行操作。它是Queue接口的扩展，可以方便地实现队列、栈和双向队列的功能，并提供了丰富的方法来操作和访问队列中的元素。

            Java Deque 接口使用示例

            当使用Java中的Deque接口时，我们同样需要选择具体的实现类来创建一个双端队列对象。下面是一个使用Deque接口的示例，以ArrayDeque实现类为例：

    1. import java.util.Deque;
    2. import java.util.ArrayDeque;
    3.  
    4. public class DequeExample {
    5.     public static void main(String[] args) {
    6.         // 创建一个Deque对象
    7.         Deque<String> deque = new ArrayDeque<>();
    8.  
    9.         // 添加元素到双端队列
    10.         deque.addFirst("Apple");
    11.         deque.addLast("Banana");
    12.         deque.addLast("Orange");
    13.  
    14.         // 获取双端队列头部和尾部元素
    15.         String first = deque.getFirst();
    16.         String last = deque.getLast();
    17.         System.out.println("头部元素：" + first);
    18.         System.out.println("尾部元素：" + last);
    19.  
    20.         // 遍历双端队列并输出元素
    21.         System.out.println("双端队列元素（从头到尾）：");
    22.         for (String element : deque) {
    23.             System.out.println(element);
    24.         }
    25.  
    26.         // 移除双端队列头部和尾部元素
    27.         String removedFirst = deque.removeFirst();
    28.         String removedLast = deque.removeLast();
    29.         System.out.println("移除的头部元素：" + removedFirst);
    30.         System.out.println("移除的尾部元素：" + removedLast);
    31.  
    32.         // 双端队列大小
    33.         int size = deque.size();
    34.         System.out.println("双端队列大小：" + size);
    35.  
    36.         // 判断双端队列是否为空
    37.         boolean isEmpty = deque.isEmpty();
    38.         System.out.println("双端队列是否为空：" + isEmpty);
    39.     }
    40. }

            在这个示例中，我们使用ArrayDeque作为实现类创建了一个Deque对象。我们向双端队列中添加了三个元素："Apple"、"Banana"和"Orange"。然后，我们使用getFirst()和getLast()方法分别获取双端队列的头部和尾部元素，并使用for-each循环遍历双端队列并输出每个元素。

            接下来，我们使用removeFirst()和removeLast()方法移除双端队列的头部和尾部元素，并使用size()方法获取双端队列的大小。最后，我们使用isEmpty()方法判断双端队列是否为空。

    4、PriorityQueue 的实现原理详解

            PriorityQueue的实现原理是基于二叉堆（Binary Heap），它是一种特殊的完全二叉树结构，具有以下性质：

    • 最小堆性质：在最小堆中，每个节点的值都小于或等于其子节点的值。也就是说，堆的根节点是最小的元素。

            PriorityQueue使用一个数组来存储元素，并通过二叉堆的形式来组织这些元素。数组中的元素按照特定的顺序排列，满足最小堆的性质。在数组中，根节点位于索引0处，而对于任意位置i的节点，它的左子节点位于索引2i+1处，右子节点位于索引2i+2处。

            当元素被添加到PriorityQueue时，它会被放置在数组的末尾，并按照以下步骤进行调整，以维护最小堆的性质：

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

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

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

            通过上述的上滤和下滤操作，PriorityQueue可以保持最小堆的性质，使得具有最高优先级的元素总是位于队列的头部。

            PriorityQueue的插入和删除操作的时间复杂度都是O(logN)，其中N是队列中的元素个数。这是因为这些操作涉及到堆的调整，需要按照树的高度来进行操作。同时，PriorityQueue还支持高效的查找具有最高优先级的元素，时间复杂度为O(1)。

            需要注意的是，PriorityQueue允许元素具有相同的优先级，但它们的顺序不一定是确定的。在这种情况下，PriorityQueue的行为是不保证的，具有相同优先级的元素可能会以任意顺序被取出。

            优先队列(PriorityQueue)的使用示例：

    1.     public static void main(String[] args) {
    2.         //默认采用的是最小堆实现的
    3.         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(10, new Comparator<Integer>() {
    4.             public int compare(Integer a, Integer b) {
    5.                 return a - b; //if a>b 则交换，so这是递增序列
    6.             }
    7.         });
    8.         queue.offer(13);
    9.         queue.offer(9);
    10.         int len = queue.size();
    11.         for (int i = 0; i < len; i++) {
    12.             System.out.println(queue.poll());
    13.         }
    14.         //输出 9  13
    15.         //默认采用的是最小堆实现的
    16.         PriorityQueue<Integer> queue2 = new PriorityQueue<>(10);
    17.         queue2.offer(11);
    18.         queue2.offer(9);
    19.         len = queue2.size();
    20.         for (int i = 0; i < len; i++) {
    21.             System.out.println(queue2.poll());
    22.         }
    23.         //输出 9， 11
    24.     }

    5、使用Java数组实现队列的简单示例

            下面是使用Java数组实现队列的简单示例代码：

    1. public class ArrayQueue {
    2.     private int[] queue;  // 内部数组
    3.     private int front;    // 队列头部指针
    4.     private int rear;     // 队列尾部指针
    5.     private int size;     // 队列当前元素个数
    6.     private int capacity; // 队列容量
    7.  
    8.     public ArrayQueue(int capacity) {
    9.         this.capacity = capacity;
    10.         queue = new int[capacity];
    11.         front = 0;
    12.         rear = -1;
    13.         size = 0;
    14.     }
    15.  
    16.     public boolean isEmpty() {
    17.         return size == 0;
    18.     }
    19.  
    20.     public boolean isFull() {
    21.         return size == capacity;
    22.     }
    23.  
    24.     public int size() {
    25.         return size;
    26.     }
    27.  
    28.     public void enqueue(int item) {
    29.         if (isFull()) {
    30.             System.out.println("Queue is full. Cannot enqueue.");
    31.             return;
    32.         }
    33.         rear = (rear + 1) % capacity; // 循环队列，计算新的尾部位置
    34.         queue[rear] = item;
    35.         size++;
    36.         System.out.println("Enqueued: " + item);
    37.     }
    38.  
    39.     public int dequeue() {
    40.         if (isEmpty()) {
    41.             System.out.println("Queue is empty. Cannot dequeue.");
    42.             return -1;
    43.         }
    44.         int item = queue[front];
    45.         front = (front + 1) % capacity; // 循环队列，计算新的头部位置
    46.         size--;
    47.         System.out.println("Dequeued: " + item);
    48.         return item;
    49.     }
    50.  
    51.     public int peek() {
    52.         if (isEmpty()) {
    53.             System.out.println("Queue is empty.");
    54.             return -1;
    55.         }
    56.         return queue[front];
    57.     }
    58.  
    59.     public void display() {
    60.         if (isEmpty()) {
    61.             System.out.println("Queue is empty.");
    62.             return;
    63.         }
    64.         System.out.print("Queue: ");
    65.         int index = front;
    66.         for (int i = 0; i < size; i++) {
    67.             System.out.print(queue[index] + " ");
    68.             index = (index + 1) % capacity; // 循环遍历队列
    69.         }
    70.         System.out.println();
    71.     }
    72.  
    73.     public static void main(String[] args) {
    74.         ArrayQueue queue = new ArrayQueue(5);
    75.         queue.enqueue(10);
    76.         queue.enqueue(20);
    77.         queue.enqueue(30);
    78.         queue.display(); // Queue: 10 20 30
    79.         queue.dequeue();
    80.         queue.display(); // Queue: 20 30
    81.         queue.enqueue(40);
    82.         queue.enqueue(50);
    83.         queue.display(); // Queue: 20 30 40 50
    84.         queue.dequeue();
    85.         queue.dequeue();
    86.         queue.display(); // Queue: 40 50
    87.     }
    88. }

            以上示例演示了使用Java数组实现的简单队列（循环队列）。通过enqueue()方法将元素入队，dequeue()方法将元素出队，peek()方法返回队列头部元素，size()方法返回队列当前元素个数，isEmpty()方法和isFull()方法检查队列是否为空或已满。display()方法用于打印队列中的元素。

            上述循环队列实现的具体步骤总结如下：

    （1）入队操作（enqueue）：

    1. 首先，检查队列是否已满（isFull()方法）。如果已满，则无法入队，并输出相应的提示信息。
    2. 否则，计算新的尾部位置（rear = (rear + 1) % capacity），并将新元素存储到该位置。
    3. 增加队列的元素个数（size++）。
    4. 输出入队的元素信息。

    （2）出队操作（dequeue）：

    1. 首先，检查队列是否为空（isEmpty()方法）。如果为空，则无法出队，并输出相应的提示信息。
    2. 否则，获取头部元素（queue[front]）并保存到临时变量中。
    3. 计算新的头部位置（front = (front + 1) % capacity）。
    4. 减少队列的元素个数（size--）。
    5. 输出出队的元素信息，并返回该元素的值。

    （3）查看头部元素（peek）：

    1. 首先，检查队列是否为空（isEmpty()方法）。如果为空，则输出相应的提示信息并返回特定的值（如-1）。
    2. 否则，返回头部元素（queue[front]）的值。

    （4）判断队列是否为空（isEmpty）：

    • 根据队列的元素个数（size）是否为0来判断队列是否为空。

    （5）判断队列是否已满（isFull）：

    • 根据队列的元素个数（size）是否等于队列的容量（capacity）来判断队列是否已满。

    （6）遍历打印队列中的元素（display）：

    1. 首先，检查队列是否为空（isEmpty()方法）。如果为空，则输出相应的提示信息。
    2. 否则，从头部位置（front）开始循环遍历队列中的元素，依次输出每个元素。
    3. 注意使用循环变量（index）进行索引，并通过取余运算实现循环遍历。

            这样，通过以上实现，我们可以使用Java数组来创建一个简单的队列，并进行入队、出队、查看头部元素以及遍历打印等操作。这种基于数组的实现方式可以满足队列的基本需求，并且具有较好的性能。但需要注意的是，由于数组的容量是固定的，当队列已满时，无法再添加新的元素，除非进行元素的出队操作。

  • 相关阅读:
    漏洞情报｜Jackson-databind反序列化漏洞风险通告（CVE-2020-35490，CVE-2020-35491)
    #循循渐进学51单片机#IIC总线与EEPROM#not.13
    指针数组，指针与函数，二维指针
    字节跳动面试题汇总 -- C++后端（含答案）
    平台工程: 用Backstage构建开发者门户 - 2
    记录一次网卡问题
    mfc入门基础（五）控件中添加消息处理函数
    C++ 内存池
    为了搞明白统计套利，从两组序列之间的关系说起
    PHP实现斐波纳契数列
  • 原文地址：https://blog.csdn.net/swadian2008/article/details/126783574