Java集合Queue-ArrayDeque有什么作用

# Java集合Queue-ArrayDeque有什么作用

## 一、ArrayDeque概述

`ArrayDeque`是Java集合框架中一個重要的雙端隊列（Deque）實現，自Java 6引入。它基于**循環數組**數據結構實現，既可作為先進先出（FIFO）的隊列使用，也可作為后進先出（LIFO）的棧使用。

### 核心特性
- **動態擴容**：初始容量16，按需自動擴容為2的冪次方
- **非線程安全**：需外部同步保證線程安全
- **Null值禁止**：禁止插入null元素
- **高性能**：O(1)時間復雜度的頭尾操作

## 二、核心應用場景

### 1. 替代傳統Stack實現
```java
// 作為棧使用（推薦替代Stack類）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // 入棧
stack.pop();    // 出棧

優勢對比：

2. 高效隊列實現

// 作為隊列使用（替代LinkedList）
Queue<String> queue = new ArrayDeque<>();
queue.offer("A");  // 入隊
queue.poll();      // 出隊

性能對比（百萬次操作）： - 入隊操作：ArrayDeque比LinkedList快約30% - 內存占用：ArrayDeque節省約40%內存

3. 滑動窗口算法

// 實現滑動窗口最大值（LeetCode 239）
public int[] maxSlidingWindow(int[] nums, int k) {
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    int[] res = new int[nums.length - k + 1];
    // ... 具體實現邏輯
}

三、底層實現原理

1. 數據結構設計

transient Object[] elements;  // 存儲元素的數組
transient int head;          // 頭指針
transient int tail;          // 尾指針

2. 循環數組機制

• 頭尾指針到達數組末尾時自動折返到0位置
• 關鍵計算公式：

  
  // 計算下一個插入位置
  tail = (tail + 1) & (elements.length - 1)  // 利用位運算代替取模
  

3. 擴容策略

private void doubleCapacity() {
    int newCapacity = elements.length << 1;  // 雙倍擴容
    Object[] a = new Object[newCapacity];
    // 分兩段復制元素
    System.arraycopy(elements, head, a, 0, elements.length - head);
    System.arraycopy(elements, 0, a, elements.length - head, head);
}

四、性能優化建議

1. 初始化容量：預估最大元素數量，避免頻繁擴容

   new ArrayDeque<>(100);  // 指定初始容量
   

2. 批量操作：優先使用addAll/removeAll方法

3. 遍歷優化：

   // 使用迭代器比for-each更高效
   Iterator<String> it = deque.iterator();
   while(it.hasNext()) {
      String item = it.next();
   }
   

五、與其他隊列對比

六、典型使用案例

1. 工作竊取算法

// 實現簡單的任務隊列
ArrayDeque<Runnable> taskQueue = new ArrayDeque<>();
// 生產者線程
taskQueue.offer(() -> System.out.println("Task1"));
// 消費者線程
Runnable task = taskQueue.poll();
if(task != null) task.run();

2. 撤銷操作實現

// 實現文檔編輯的撤銷/重做功能
ArrayDeque<Action> undoStack = new ArrayDeque<>();
ArrayDeque<Action> redoStack = new ArrayDeque<>();

void performAction(Action action) {
    action.execute();
    undoStack.push(action);
    redoStack.clear();
}

七、總結

ArrayDeque作為Java集合框架中的高效雙端隊列實現，在需要頻繁進行隊列頭尾操作的場景下展現出顯著優勢。其設計巧妙結合了數組的隨機訪問特性和循環數組的空間復用機制，是替代傳統Stack和LinkedList的理想選擇。開發者應根據具體業務場景，合理選擇初始化參數和使用模式，以充分發揮其性能優勢。 “`