在 Java 中，Deque（雙端隊列）是一個支持在兩端插入和刪除的隊列。它是 Java Collections Framework 的一部分，通過接口和實現(xiàn)類提供了高效的雙端操作能力。

Deque 基礎(chǔ)概念

• Deque 是 雙端隊列，支持在隊列的 頭部 和 尾部 添加、刪除、訪問元素。
• 它繼承自 Queue 接口，是一種更加通用的數(shù)據(jù)結(jié)構(gòu)。
• 既可以用作 隊列（FIFO），也可以用作 棧（LIFO）。

接口定義

Deque 是一個接口，常用實現(xiàn)類有：

• ArrayDeque：基于動態(tài)數(shù)組的雙端隊列實現(xiàn)。
• LinkedList：基于雙向鏈表的雙端隊列實現(xiàn)。

常見操作分類

• 頭部操作：addFirst、removeFirst、getFirst
• 尾部操作：addLast、removeLast、getLast
• ???????通用隊列操作：offer、poll、peek

Deque 的方法詳解

1. 添加元素

在頭部添加：

• void addFirst(E e)：在隊列頭部插入元素，若隊列滿則拋出異常。
• boolean offerFirst(E e)：在隊列頭部插入元素，若隊列滿返回 false。

在尾部添加：

• void addLast(E e)：在隊列尾部插入元素，若隊列滿則拋出異常。
• boolean offerLast(E e)：在隊列尾部插入元素，若隊列滿返回 false。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 在頭部添加
deque.addLast(2);  // 在尾部添加
System.out.println(deque); // 輸出：[1, 2]

2. 刪除元素

從頭部刪除：

• E removeFirst()：刪除并返回頭部元素，若隊列為空則拋出異常。
• E pollFirst()：刪除并返回頭部元素，若隊列為空返回 null。

從尾部刪除：

• E removeLast()：刪除并返回尾部元素，若隊列為空則拋出異常。
• E pollLast()：刪除并返回尾部元素，若隊列為空返回 null。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst(); // 刪除頭部元素
deque.removeLast();  // 刪除尾部元素
System.out.println(deque); // 輸出：[]

3. 訪問元素

訪問頭部元素：

• E getFirst()：獲取但不刪除頭部元素，若隊列為空則拋出異常。
• E peekFirst()：獲取但不刪除頭部元素，若隊列為空返回 null。

訪問尾部元素：

• E getLast()：獲取但不刪除尾部元素，若隊列為空則拋出異常。
• E peekLast()：獲取但不刪除尾部元素，若隊列為空返回 null。 示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.getFirst()); // 輸出：1
System.out.println(deque.getLast());  // 輸出：2

4. 棧操作（LIFO）

• void push(E e)：將元素壓入棧頂（相當(dāng)于 addFirst）。
• E pop()：移除并返回棧頂元素（相當(dāng)于 removeFirst）。

示例：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 壓入棧頂
stack.push(2);
System.out.println(stack.pop()); // 彈出棧頂元素，輸出：2
System.out.println(stack.pop()); // 輸出：1

5. 隊列操作（FIFO）

• boolean offer(E e)：將元素添加到隊列尾部（相當(dāng)于 offerLast）。
• E poll()：移除并返回隊列頭部元素（相當(dāng)于 pollFirst）。
• E peek()：獲取但不刪除隊列頭部元素（相當(dāng)于 peekFirst）。

示例：

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 添加到尾部
queue.offer(2);
System.out.println(queue.poll()); // 移除頭部元素，輸出：1
System.out.println(queue.peek()); // 獲取頭部元素，輸出：2

6. 刪除所有元素

• void clear()：清空隊列。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.add(1);
deque.add(2);
deque.clear(); // 清空隊列
System.out.println(deque.isEmpty()); // 輸出：true

7. 檢查隊列狀態(tài)

• boolean isEmpty()：檢查隊列是否為空。
• int size()：返回隊列中元素的數(shù)量。

Deque 的實現(xiàn)類

1. ArrayDeque

• 基于動態(tài)數(shù)組實現(xiàn)。
• 特點(diǎn)：
  • 適合用作棧和隊列。
  • 線程不安全，但效率較高。
  • 不允許存儲 null 元素。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque); // 輸出：[1, 2]

2. LinkedList

• 基于雙向鏈表實現(xiàn)。
• 特點(diǎn)：
  • 支持隊列和棧操作。
  • 允許存儲 null 元素。
  • 適合頻繁插入和刪除操作的場景。

示例：

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque); // 輸出：[1, 2]

常見應(yīng)用場景

1. 棧實現(xiàn)（LIFO 模式）

Deque 提供了 push 和 pop 方法，可以方便地模擬棧。

示例：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 輸出：2
System.out.println(stack.pop()); // 輸出：1

2. 隊列實現(xiàn)（FIFO 模式）

Deque 提供了 offer 和 poll 方法，可以模擬隊列操作。

示例：

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll()); // 輸出：1
System.out.println(queue.poll()); // 輸出：2

3. 滑動窗口

Deque 可以用作維護(hù)滑動窗口的數(shù)據(jù)結(jié)構(gòu)，例如最大值或最小值的計算。

4. 雙端處理

Deque 支持從兩端同時處理數(shù)據(jù)，例如支持同時從頭尾訪問元素的算法（如回文檢查）。

總結(jié)

推薦使用場景

• 對于簡單的?；蜿犃胁僮?，使用 ArrayDeque。
• 對于需要頻繁插入、刪除或允許存儲 null 的場景，選擇 LinkedList。

Deque 是一個功能強(qiáng)大的雙端數(shù)據(jù)結(jié)構(gòu)，在隊列和棧操作中非常靈活。根據(jù)實際需求選擇實現(xiàn)類即可。

到此這篇關(guān)于java Deque 詳解的文章就介紹到這了,更多相關(guān)java Deque 詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論