Deque 接口和 ArrayDeque 概述

Deque（双端队列）接口是 Java 集合框架中的一个重要接口，代表可以在两端进行插入和删除操作的队列。ArrayDeque 是 Deque 接口的一个高效实现类。

ArrayDeque 的主要特点

1. 双端操作: 支持在队列两端进行插入和删除操作
2. 无容量限制: 可以动态扩容
3. 非线程安全: 不是线程安全的，多线程环境下需要外部同步
4. 高性能: 比 Stack 和 LinkedList 实现栈和队列更高效

ArrayDeque 的主要方法

栈操作方法（LIFO）

• push(E e): 将元素压入双端队列的头部
• pop(): 弹出双端队列头部的元素
• peek(): 获取但不移除双端队列头部的元素

队列操作方法（FIFO）

• addFirst(E e): 在双端队列头部添加元素
• addLast(E e): 在双端队列尾部添加元素
• removeFirst(): 移除并返回双端队列头部元素
• removeLast(): 移除并返回双端队列尾部元素
• getFirst(): 获取但不移除双端队列头部元素
• getLast(): 获取但不移除双端队列尾部元素

通用操作方法

• offerFirst(E e): 在双端队列头部插入元素，成功返回 true
• offerLast(E e): 在双端队列尾部插入元素，成功返回 true
• pollFirst(): 获取并移除双端队列头部元素，队列为空时返回 null
• pollLast(): 获取并移除双端队列尾部元素，队列为空时返回 null
• peekFirst(): 获取但不移除双端队列头部元素，队列为空时返回 null
• peekLast(): 获取但不移除双端队列尾部元素，队列为空时返回 null
• [size()](file://D:\zeekr-dict-server\zeekr-dict-server-infrastructure\src\main\java\com\zeekr\bigdata\dict\infrastructure\integration\redis\RedisTemplateService.java#L308-L308): 返回双端队列中元素的数量
• isEmpty(): 判断双端队列是否为空

ArrayDeque 使用示例

作为栈使用

Deque<Integer> stack = new ArrayDeque<>();

// 压入元素
stack.push(10);
stack.push(20);
stack.push(30);

// 查看栈顶元素
Integer top = stack.peek(); // 返回 30

// 弹出元素
Integer popped = stack.pop(); // 返回并移除 30

// 检查是否为空
boolean isEmpty = stack.isEmpty(); // 返回 false

作为队列使用

Deque<String> queue = new ArrayDeque<>();

// 入队
queue.offerLast("first");
queue.offerLast("second");
queue.offerLast("third");

// 查看队首元素
String first = queue.peekFirst(); // 返回 "first"

// 出队
String removed = queue.pollFirst(); // 返回并移除 "first"

双端操作示例

Deque<Character> deque = new ArrayDeque<>();

// 在两端添加元素
deque.offerFirst('A');
deque.offerLast('Z');
deque.offerFirst('B');
deque.offerLast('Y');

// deque 现在是: B, A, Z, Y

// 从两端移除元素
Character firstChar = deque.pollFirst(); // 返回 'B'
Character lastChar = deque.pollLast();   // 返回 'Y'

使用场景

1. 实现高效的栈结构

public class EfficientStack<E> {
    private Deque<E> deque = new ArrayDeque<>();
    
    public void push(E item) {
        deque.push(item);
    }
    
    public E pop() {
        return deque.pop();
    }
    
    public E peek() {
        return deque.peek();
    }
    
    public boolean isEmpty() {
        return deque.isEmpty();
    }
}

2. 实现队列结构

public class EfficientQueue<E> {
    private Deque<E> deque = new ArrayDeque<>();
    
    public void enqueue(E item) {
        deque.offerLast(item);
    }
    
    public E dequeue() {
        return deque.pollFirst();
    }
    
    public E front() {
        return deque.peekFirst();
    }
    
    public boolean isEmpty() {
        return deque.isEmpty();
    }
}

3. 滑动窗口最大值问题

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0 || k == 0) return new int[0];
    
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];
    int index = 0;
    
    for (int i = 0; i < nums.length; i++) {
        // 移除超出窗口范围的索引
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 移除所有小于当前元素的索引
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        deque.offerLast(i);
        
        // 当窗口形成后开始记录最大值
        if (i >= k - 1) {
            result[index++] = nums[deque.peekFirst()];
        }
    }
    
    return result;
}

4. 回文检查

public boolean isPalindrome(String str) {
    Deque<Character> deque = new ArrayDeque<>();
    
    // 将字符添加到双端队列中
    for (char c : str.toCharArray()) {
        deque.offerLast(c);
    }
    
    // 从两端比较字符
    while (deque.size() > 1) {
        if (!deque.pollFirst().equals(deque.pollLast())) {
            return false;
        }
    }
    
    return true;
}

优势对比

ArrayDeque vs Stack

• ArrayDeque 性能更好，Stack 继承自 Vector 有不必要的同步开销
• ArrayDeque 不会抛出 EmptyStackException，而是返回 null
• ArrayDeque 是 Deque 接口的推荐实现

ArrayDeque vs LinkedList

• ArrayDeque 在大多数操作上比 LinkedList 更快
• ArrayDeque 内存使用更紧凑
• LinkedList 允许 null 元素，而 ArrayDeque 不允许

注意事项

1. ArrayDeque 不允许存储 null 元素
2. 不是线程安全的，在多线程环境中需要外部同步
3. 迭代器是快速失败的（fail-fast）
4. 当用作栈时，ArrayDeque 比传统的 Stack 类更推荐使用

以上部分内容由大模型生成，注意识别！