深入了解Java队列接口

约定不等于承诺〃 2023-10-16 11:46 25阅读 0赞

##### 队列接口 #####

队列接口是 Java 集合框架的一个重要部分，它扩展了 Collection 接口。队列接口表示遵循“先进先出”（FIFO）原则的元素集合。队列允许存储重复值。队列的基本特征是元素按特定顺序存储，类似于等待轮流的人群，主要通过添加元素到队尾（入队）和从队首移除元素（出队）等操作来访问和操作元素。队列在需要按顺序管理元素的场景中非常有用，例如任务调度或按预定顺序处理项目。

##### 队列的常见实现 #####

**LinkedList**：

Java 的 LinkedList 类可用于实现队列，它还实现了 List 接口。它提供了一个双向链表实现，非常适合实现基本的 FIFO 队列。

*  有序集合：它维护元素的顺序并允许重复值，就像其他 List 实现一样。
 *  索引访问：您可以通过索引访问元素，从而有效地检索、修改或删除元素。
 *  列表特定方法：它提供了 List 接口指定的所有方法，包括 add、get、set、remove、indexOf 等。这些方法的操作方式与链表的特性一致。
 *  同步：默认情况下不同步（非线程安全）。
 *  队列特性：它遵循 FIFO（先进先出）原则进行入队（添加）和出队（移除）操作。
 *  双端队列特性：它支持栈式行为（LIFO - 后进先出）和队列式行为，提供了诸如 offer、poll、peek、push、pop 等方法。
 *  队列特定方法：它提供了 Queue 接口指定的所有方法，包括 offer、poll、peek 和 element。

import java.util.LinkedList;
    
    public class Test {
        
        public static void main(String[] args) {
        
            // 创建一个 LinkedList
            LinkedList<String> linkedList = new LinkedList<>();
    
            // 向列表中添加元素
            linkedList.add("Apple"); // 在末尾添加
            linkedList.add("Banana");
            linkedList.add("Cherry");
            linkedList.add("Date");
    
            // 显示列表
            System.out.println("原始 LinkedList: " + linkedList);
    
            // 队列方法：offer、poll、peek
            linkedList.offer("Elderberry"); // 在末尾添加（入队）
            String removedItem = linkedList.poll(); // 从前端移除（出队）
            String frontItem = linkedList.peek(); // 查看前端元素
            System.out.println("在 offer、poll 和 peek 之后: " + linkedList);
            System.out.println("移除的项目: " + removedItem);
            System.out.println("前端项目: " + frontItem);
    
            // 栈方法：push、pop
            linkedList.push("Fig"); // 在前端添加（压栈）
            String poppedItem = linkedList.pop(); // 从前端移除（出栈）
            System.out.println("在 push 和 pop 之后: " + linkedList);
            System.out.println("弹出的项目: " + poppedItem);
    
            // 列表方法：add、get、set、remove、indexOf
            linkedList.add(2, "Grape"); // 在特定索引处插入
            String getItem = linkedList.get(3); // 获取索引 3 处的元素
            linkedList.set(1, "Blueberry"); // 设置索引 1 处的元素
            linkedList.remove(4); // 移除索引 4 处的元素
            int index = linkedList.indexOf("Cherry"); // 查找 "Cherry" 的索引
    
            System.out.println("在列表操作之后: " + linkedList);
            System.out.println("获取索引 3 处的项目: " + getItem);
            System.out.println("'Cherry' 的索引: " + index);        
        }
    }

通过扩展 List 和 Queue，Java 中的 LinkedList 结合了这些接口的特性和底层链表数据结构，为各种用例提供了灵活性和效率。根据您的需求，您可以选择与 LinkedList 一起使用的适当接口。

**ArrayDeque**：

Java 的 ArrayDeque 类提供了一个双端队列实现，也可以用作队列。它提供了从两端添加或删除元素的常数时间（平摊）操作。

ArrayDeque 在内部使用动态数组来存储元素，可以根据需要增长或缩小。

*  双端：它支持从双端队列的前端和后端添加和删除元素。这使得它适用于各种用例，包括实现栈和队列。
 *  常数时间操作：从双端队列的前端或后端添加或删除元素等常见操作的平均时间复杂度为常数，使得它在动态数据操作方面非常高效。
 *  随机访问：与链表不同，ArrayDeque 使用索引提供常数时间的随机访问元素。
 *  ArrayDeque 允许空元素，这意味着您可以在双端队列中存储空值。
 *  ArrayDeque 没有固定容量。它根据需要动态调整其内部数组的大小以容纳额外的元素。
 *  ArrayDeque 是一种多功能的数据结构，适用于实现各种数据操作任务，例如：
    
     *  实现栈（LIFO）和队列（FIFO）。
     *  有效维护元素的滑动窗口。
     *  存储和管理需要在两端快速插入和删除的元素。
 *  方法：
    
     *  addFirst(E e) 和 addLast(E e)：分别向双端队列的前端和后端添加元素。
     *  offerFirst(E e) 和 offerLast(E e)：类似于 addFirst 和 addLast，但返回表示成功的布尔值。
     *  removeFirst() 和 removeLast()：分别从双端队列的前端和后端移除并返回元素。
     *  pollFirst() 和 pollLast()：类似于 removeFirst 和 removeLast，但如果双端队列为空，则返回 null。
     *  getFirst() 和 getLast()：获取双端队列的第一个和最后一个元素，但不移除它们。
     *  peekFirst() 和 peekLast()：类似于 getFirst 和 getLast，但如果双端队列为空，则返回 null。
     *  size()：返回双端队列中的元素数量。
     *  isEmpty()：如果双端队列为空，则返回 true。
     *  clear()：从双端队列中移除所有元素。
 *  ArrayDeque 默认不是线程安全的，不适用于多线程并发访问。如果需要线程安全，请考虑使用 java.util.concurrent 类，如 ConcurrentLinkedDeque。

import java.util.ArrayDeque;
    import java.util.Deque;
    
    public class Test {
        
        public static void main(String[] args) {
        
            // 创建一个 ArrayDeque
            Deque<String> deque = new ArrayDeque<>();
    
            // 向双端队列的前端和后端添加元素
            deque.addFirst("A"); // 在前端添加 "A"
            deque.addLast("B");  // 在后端添加 "B"
    
            // 使用返回值向前端和后端提供元素
            boolean offeredFront = deque.offerFirst("C"); // 在前端添加 "C"
            boolean offeredRear = deque.offerLast("D");   // 在后端添加 "D"
    
            System.out.println("添加元素后: " + deque);
            System.out.println("向前端提供: " + offeredFront);
            System.out.println("向后端提供: " + offeredRear);
    
            // 从双端队列的前端和后端移除元素
            String removedFront = deque.removeFirst(); // 从前端移除并返回 "C"
            String removedRear = deque.removeLast();   // 从后端移除并返回 "D"
    
            System.out.println("从前端移除: " + removedFront);
            System.out.println("从后端移除: " + removedRear);
            System.out.println("移除后: " + deque);
    
            // 使用可能的空返回值从前端和后端轮询元素
            String polledFront = deque.pollFirst(); // 从前端轮询并返回 "A"
            String polledRear = deque.pollLast();   // 从后端轮询并返回 "B"
    
            System.out.println("从前端轮询: " + polledFront);
            System.out.println("从后端轮询: " + polledRear);
            System.out.println("轮询后: " + deque);
    
            deque.addFirst("A"); // 在前端添加 "A"
            deque.addLast("B");  // 在后端添加 "B"
            // 在不移除的情况下获取双端队列的前端和后端元素
            String frontElement = deque.getFirst(); // 检索但不移除前端元素
            String rearElement = deque.getLast();   // 检索但不移除后端元素
    
            System.out.println("前端元素: " + frontElement);
            System.out.println("后端元素: " + rearElement);
            System.out.println("检索后的双端队列: " + deque);
    
            // 检查双端队列是否为空
            boolean isEmpty = deque.isEmpty(); // 返回 false，因为双端队列中有元素
    
            System.out.println("双端队列是否为空？ " + isEmpty);
    
            // 清除双端队列
            deque.clear(); // 从双端队列中移除所有元素
    
            System.out.println("清除双端队列后: " + deque);
    
            // 检查双端队列是否为空
            isEmpty = deque.isEmpty(); // 返回 false，因为双端队列中有元素
    
            System.out.println("双端队列是否为空？ " + isEmpty);
        }
    }