ArrayDeque简介

ArrayDeque简介

`ArrayDeque`是Java中的一个双端队列(Double-ended Queue)实现
   它允许在队列的两端进行元素的插入和删除操作
    `ArrayDeque`是`Deque`接口的一个具体实现，不是线程安全的。

ArrayDeque主要特点

1.基本特性
 -动态数组实现:
    底层使用循环数组实现
 -无容量限制:
    可以根据需要动态扩容
 -非线程安全:
    不提供并发访问保护
 -不允许null元素:
    插入null会抛出 NullPointerException
 -高效性能:
    大多数操作的时间复杂度为 O(1)

2.与Linkedlist比较

// ArrayDeque vs LinkedList 作为 Deque 使用
public class DequeComparison {
    public void comparePerformance() {
        // ArrayDeque - 基于数组，内存局部性好
        Deque<String> arrayDeque = new ArrayDeque<>();
        
        // LinkedList - 基于链表，每个节点需要额外内存
        Deque<String> linkedList = new LinkedList<>();
        
        // ArrayDeque 在大多数操作上性能更好
    }
}

ArrayDeque示例

 1.作为普通队列使用（FIFO）
 
import java.util.ArrayDeque;
import java.util.Deque;

public class QueueExample {
    public void queueOperations() {
        Deque<String> queue = new ArrayDeque<>();
        
        // 入队操作
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");
        
        // 查看队首元素（不移除）
        System.out.println("队首元素: " + queue.peek()); // 输出: first
        
        // 出队操作
        System.out.println("出队: " + queue.poll()); // 输出: first
        System.out.println("出队: " + queue.poll()); // 输出: second
        
        System.out.println("剩余元素数量: " + queue.size()); // 输出: 1
    }
}
 
 2. 作为栈使用（LIFO） 
public class StackExample {
    public void stackOperations() {
        Deque<String> stack = new ArrayDeque<>();
        
        // 入栈操作
        stack.push("first");
        stack.push("second");
        stack.push("third");
        
        // 查看栈顶元素（不移除）
        System.out.println("栈顶元素: " + stack.peek()); // 输出: third
        
        // 出栈操作
        System.out.println("出栈: " + stack.pop()); // 输出: third
        System.out.println("出栈: " + stack.pop()); // 输出: second
        
        System.out.println("剩余元素数量: " + stack.size()); // 输出: 1
    }
}
 
 3.双端操作 
public class DequeOperations {
    public void dequeOperations() {
        ArrayDeque<String> deque = new ArrayDeque<>();
        
        // 从队尾添加
        deque.addLast("tail");
        deque.offerLast("tail2");
        
        // 从队首添加
        deque.addFirst("head");
        deque.offerFirst("head2");
        
        System.out.println("deque: " + deque); // [head2, head, tail, tail2]
        
        // 从队首移除
        System.out.println("移除队首: " + deque.removeFirst()); // head2
        System.out.println("移除队首: " + deque.pollFirst());   // head
        
        // 从队尾移除
        System.out.println("移除队尾: " + deque.removeLast());  // tail2
        System.out.println("移除队尾: " + deque.pollLast());    // tail
    }
}

ArrayDeque内部实现原理

 1. 循环数组结构 
public class ArrayDequeInternal {
    // 简化的内部结构示意
    private Object[] elements;  // 存储元素的数组
    private int head;           // 队首索引
    private int tail;           // 队尾索引
    
    // 当 head == tail 时，队列为空
    // 当 (tail + 1) % elements.length == head 时，队列满（预留一个空位）
}
 
 2. 扩容机制 
public class ResizeExample {
    public void demonstrateResize() {
        ArrayDeque<Integer> deque = new ArrayDeque<>(4); // 初始容量4
        
        // 添加元素触发扩容
        for (int i = 0; i < 10; i++) {
            deque.add(i);
        }
        
        // ArrayDeque 扩容时容量变为原来的2倍
        System.out.println("元素数量: " + deque.size()); // 10
    }
}