Java Deque 如何实现高效双端操作

Java中的Deque（双端队列）接口提供了高效的双端操作。它允许你在队列的两端添加和删除元素。Deque的实现类有很多，如ArrayDeque和LinkedList等。这里我们将讨论如何使用ArrayDeque实现高效双端操作。

1. 添加元素：

   • addFirst(E e): 在队列的开头添加一个元素。时间复杂度为O(1)。
   • addLast(E e): 在队列的末尾添加一个元素。时间复杂度为O(1)。
   • offerFirst(E e): 在队列的开头添加一个元素，如果队列已满，则返回false。时间复杂度为O(1)。
   • offerLast(E e): 在队列的末尾添加一个元素，如果队列已满，则返回false。时间复杂度为O(1)。

2. 删除元素：

   • removeFirst(): 删除并返回队列的第一个元素。时间复杂度为O(1)。
   • removeLast(): 删除并返回队列的最后一个元素。时间复杂度为O(1)。
   • pollFirst(): 删除并返回队列的第一个元素，如果队列为空，则返回null。时间复杂度为O(1)。
   • pollLast(): 删除并返回队列的最后一个元素，如果队列为空，则返回null。时间复杂度为O(1)。

3. 查看元素：

   • peekFirst(): 返回队列的第一个元素，但不移除它。如果队列为空，则返回null。时间复杂度为O(1)。
   • peekLast(): 返回队列的最后一个元素，但不移除它。如果队列为空，则返回null。时间复杂度为O(1)。

4. 检查队列是否为空：

   • isEmpty(): 如果队列为空，则返回true，否则返回false。时间复杂度为O(1)。

5. 获取队列的大小：

   • size(): 返回队列中的元素数量。时间复杂度为O(1)。

使用ArrayDeque实现高效双端操作示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // 添加元素
        deque.addFirst(1);
        deque.addLast(2);
        deque.offerFirst(3);
        deque.offerLast(4);

        // 查看元素
        System.out.println("Peek first: " + deque.peekFirst()); // 输出：Peek first: 3
        System.out.println("Peek last: " + deque.peekLast()); // 输出：Peek last: 4

        // 删除元素
        deque.removeFirst();
        deque.removeLast();

        // 查看元素
        System.out.println("Peek first: " + deque.peekFirst()); // 输出：Peek first: 1
        System.out.println("Peek last: " + deque.peekLast()); // 输出：Peek last: 2

        // 检查队列是否为空
        System.out.println("Is empty: " + deque.isEmpty()); // 输出：Is empty: false

        // 获取队列的大小
        System.out.println("Size: " + deque.size()); // 输出：Size: 2
    }
}

ArrayDeque实现了高效的双端操作，因为它基于数组实现，支持在两端进行快速的插入和删除操作。