Java Deque是一種結合了普通Queue和Stack的數據結構。您可以在 Deque 的頭部和尾部添加和刪除元素。在“傳統”隊列中,您將元素添加到行的尾部(在最後一個元素之後)並從隊列的頭部移除元素。這一原則稱為先進先出 (FIFO),它的工作方式與現實生活中任何常見的客戶排隊一樣。在 Java 中,隊列是一個接口,是集合框架的一部分。
還有一個重要的數據結構稱為 Stack,這是一個以完全相反的原則處理元素的列表,LIFO——後進先出。它類似於一堆盤子,只能在頂部添加或移除。
“Deque”這個名字的意思是“雙端隊列”。“Deque”的發音就像一副紙牌,你知道嗎?它有點類似於一副真正的紙牌:你可以從這樣一副紙牌的底部或頂部拿一張牌。想在某些線性結構的兩側添加或刪除元素?使用雙端隊列。Java 8 或幾乎任何其他版本都支持它。想像一下典型的樂高積木和由積木製成的單柱“塔”。您可以在塔的頂部或底部添加一塊新磚。您也可以從兩側移除一塊磚。這裡有一個示例:我們將所有黃色磚塊添加到頂部,將所有紅色磚塊添加到底部。我們將很快用 Java 代碼演示這個例子。
因此,您可以從 Java Deque 的兩端入隊和出隊,這意味著您可以將 Deque 用作隊列和堆棧。閱讀 Java 中的堆棧:Java Stack 101:深入研究堆棧類 閱讀 Java 中的隊列:Java 隊列接口及其實現
LinkedList 類在內部使用雙鍊錶來模擬隊列或雙端隊列。ArrayDeque 類將元素內部存儲在數組中。如果元素的數量超過數組的體積,則分配一個新數組,並將所有元素移過去。這意味著 ArrayDeque 根據需要增長。
LinkedList 主要被稱為 List 實現,但該類也實現了 Deque,它允許我們創建一個由包括 null 在內的任何對象組成的雙向隊列。LinkedList 是元素的集合。我們可以在類的代碼源中看到,這次注意字段:這裡我們添加一個例子,但是如果你想了解更多關於LinkedList的知識,歡迎閱讀這篇CodeGym文章。


隊列與雙端隊列
Deque 是一種奇怪的隊列類型:您可以將新元素添加到行的尾部和頭部。刪除的情況相同:您可以從此結構中刪除最後一個或第一個元素。因此,它似乎是 Stack 和 Queue 的混合體。

雙端隊列的特點
- Java 中的 Deque 是一個接口,它的實現提供了對可變大小數組的支持。所以你有一個數組不受限制的容量,你可以根據你的需要添加新的元素。
- Deque 不支持多個線程的當前訪問
- 在沒有外部同步的情況下,雙端隊列不是線程安全的。
- 數組雙端隊列中不允許有 Null 元素。
雙端隊列 Java 接口聲明
public interface Deque<E> extends Queue<E>
Java 雙端隊列方法
java.util.Deque是一個擴展 Java 隊列接口的接口,代表一個雙端隊列。因此,您可以在使用 Deque 時使用所有 Java Queue 方法。儘管 Deque 沒有擴展 Stack 接口,但 Deque 接口定義了一些方法,使您能夠執行典型的堆棧操作,例如push、peek和pop。- boolean add(element)添加一個元素到雙端隊列的尾部。成功時返回 true,如果當前沒有可用空間則拋出 IllegalStateException。
- addFirst(element)將一個元素添加到 Deque 的頭部。
- addLast(element)將一個元素添加到雙端隊列的尾部。
- offer(element)在尾部添加一個元素並返回一個布爾值來說明插入是否成功。
- offerFirst(element)向頭部添加一個元素並返回一個布爾值來說明插入是否成功。
- offerLast(element)在尾部添加一個元素並返回一個布爾值來說明插入是否成功。
- iterator()返回雙端隊列的迭代器。
- descendingIterator()返回一個迭代器,該迭代器具有與此雙端隊列相反的順序。
- push(element)向頭部添加一個元素。
- pop(element)從頭部移除一個元素並返回它。
- removeFirst()刪除頭部的元素。
- removeLast()刪除尾部的元素。
- poll()檢索並移除此雙端隊列所表示的隊列的頭部(換句話說,此雙端隊列的第一個元素),或者如果此雙端隊列為空,則返回 null。
- pollFirst()檢索並刪除此雙端隊列的第一個元素,如果此雙端隊列為空,則返回 null。
- pollLast()檢索並刪除此雙端隊列的最後一個元素,如果此雙端隊列為空,則返回 null。
- peek()檢索但不刪除此雙端隊列所表示的隊列的頭部(換句話說,此雙端隊列的第一個元素),如果此雙端隊列為空,則返回 null。
- peekFirst()檢索但不刪除此雙端隊列的第一個元素,如果此雙端隊列為空,則返回 null。
- peekLast()檢索但不刪除此雙端隊列的最後一個元素,如果此雙端隊列為空,則返回 null。
第一元素(頭) | 最後一個元素(尾巴) | |||
---|---|---|---|---|
手術 | 拋出異常 |
特別值 | 拋出異常 | 特別值 |
插入 | 添加第一(e)/推(e) | 報價第一(e) | 添加最後一個(e) | 最後報價() |
消除 | removeFirst()/彈出() | 輪詢優先() | 移除最後一個() | 輪詢最後() |
檢查 | getFirst() | peekFirst()/偷看() | 獲取最後一個() | peekLast() |
雙端隊列實現
Java Deque 是一個接口,在 Java Collections API 中有實現:- java.util.LinkedList //List和Deque的實現
- java.util.ArrayDeque //雙端隊列實現,Java庫

ArrayDeque 類
ArrayDeque <E>類是一個通用的雙向隊列,繼承了 AbstractCollection 類的功能並使用了 Deque 接口。ArrayDeque 提供了使用 deque 和 resizable-array 的便利。最初,數組的大小初始化為 16。它被實現為一個雙向隊列,它支持兩個指針,即頭和尾。它繼承了AbstractCollection類並實現了Deque接口。關於 ArrayDeque 類的要點是:- 您可以從 ArrayDeque 的尾部和頭部添加或刪除元素
- 不允許空元素
- 在沒有外部同步的情況下,ArrayDeque 不是線程安全的。
- ArrayDeque 沒有容量限制。
ArrayDeque 類構造函數
- ArrayDeque()創建一個空隊列。
- ArrayDeque(Collection <? extends E> collection)創建一個隊列,裡面裝滿了Collection集合元素。
- ArrayDeque(int capacity)創建一個初始容量為capacity的隊列。如果不指定初始容量,則默認容量為 16。
Java 雙端隊列示例——ArrayDeque
還記得文章開頭的樂高塔示例嗎?讓我們創建一個類來構建由樂高積木製成的單柱塔。積木可以是紅色、黃色或藍色。我們的塔樓規則:我們將紅磚放在底部,將黃磚放在頂部。大 Java 雙端隊列示例
//enum with colors
public enum Color {
RED, YELLOW, BLUE;
}
//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
Color color;
boolean isConnected;
public void connect() {
System.out.println("This brick is connected");
this.isConnected = true;
}
public void disconnect() {
System.out.println("Disconnected");
isConnected = false;
}
public LegoBrick(Color color, boolean isConnected) {
this.color = color;
this.isConnected = isConnected;
}
public Color getColor() {
return color;
}
public boolean isConnected() {
return isConnected;
}
@Override
public String toString() {
return "LegoBrick{" +
"color=" + color +
", isConnected=" + isConnected +
'}';
}
}
這是我們的 Tower 類。我們啟動一座塔。啟動塔取決於紅色和黃色的數量。我們可以在塔上添加磚塊或將其移除。如果是黃色,我們將磚塊添加到頂部,如果是紅色,則將其添加到底部。
import java.util.ArrayDeque;
public class LegoTower {
ArrayDeque<LegoBrick> myTower;
int quantityOfReds;
int quantityOfYellows;
public void addBrickToTower(LegoBrick newLegoBrick) {
if (newLegoBrick.getColor() == Color.YELLOW) {
this.myTower.offerLast(newLegoBrick);
quantityOfYellows++;
}
//we can use addFirst(e)/push(e) instead of offerFirst here
if (newLegoBrick.getColor() == Color.RED) {
myTower.offerFirst(newLegoBrick);
quantityOfReds++;
}
}
public void removeBrickFromTower (LegoBrick legoBrick) {
if (legoBrick.getColor() == Color.YELLOW) {
this.myTower.removeLast();
quantityOfYellows--;
}
if (legoBrick.getColor() == Color.RED) {
myTower.removeFirst();
quantityOfReds--;
}
legoBrick.isConnected = false;
}
public LegoTower(int quantityOfReds, int quantityOfYellows) {
myTower = new ArrayDeque<>();
this.quantityOfReds = quantityOfReds;
this.quantityOfYellows = quantityOfYellows;
for (int i = 0; i < quantityOfReds; i++) {
LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
myTower.addFirst(redLegoBrick);
redLegoBrick.isConnected = true;
}
for (int i = 0; i < quantityOfYellows; i++) {
LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
myTower.addLast(yellowLegoBrick);
yellowLegoBrick.isConnected = true;
}
}
public void setMyTower(ArrayDeque<legobrick> myTower) {
this.myTower = myTower;
}
public void setQuantityOfReds(int quantityOfReds) {
this.quantityOfReds = quantityOfReds;
}
public void setQuantityOfYellows(int quantityOfYellows) {
this.quantityOfYellows = quantityOfYellows;
}
@Override
public String toString() {
return "LegoTower{" +
"myTower=" + myTower +
", quantityOfReds=" + quantityOfReds +
", quantityOfYellows=" + quantityOfYellows +
'}';
}
public void drawTower() {
for (LegoBrick i : myTower) {
System.out.println(i.color);
}
}
}
public class Main {
public static void main(String[] args) {
LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
legoBrick1.connect();
System.out.println(legoBrick1.toString());
legoBrick1.disconnect();
System.out.println(legoBrick1.toString());
LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);
LegoTower legoTower = new LegoTower(2, 5);
System.out.println("my Initiated Lego Tower: ");
legoTower.drawTower();
legoTower.addBrickToTower(legoBrick1);
legoTower.addBrickToTower(legoBrick2);
legoTower.addBrickToTower(legoBrick3);
legoTower.addBrickToTower(legoBrick4);
legoTower.addBrickToTower(legoBrick5);
System.out.println("My LegoTower after adding some elements: ");
legoTower.drawTower();
legoTower.removeBrickFromTower(legoBrick1);
legoTower.removeBrickFromTower(legoBrick3);
System.out.println("We removed one red and one yellow brick:");
legoTower.drawTower();
}
}
運行這個程序的結果:
my Initiated LegoTower:
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
Process finished with exit code 0
等等,什麼??為什麼紅色在上面?不,他們沒有。他們只是從第一個(底部)到最後一個(頂部)打印到控制台。所以如果你想看到像上面圖片中的積木一樣的東西,你可以改變 LegoTower 類的 drawTower 方法。這是一項非常容易的任務!
鍊錶
List 接口保持添加項目的順序,並允許通過索引訪問項目。Deque 是一個雙向隊列,它支持從兩側添加和刪除元素。
Java中的鍊錶實現,添加和刪除元素。例子
讓我們在實踐中嘗試這些操作。首先,Java LinkedList 實現:創建一個字符串的 LinkedList,添加 3 個元素。然後去掉一個,再在中間加一個。
public class MyLinkedTest {
public static void main(String[] args) {
String h1 = "my";
String h2 = "favorite";
String h3 = "book";
// LinkedList implementation in Java
LinkedList<string> linkedList = new LinkedList();
linkedList.add(h1);
linkedList.add(h2);
linkedList.add(h3);
System.out.println("my list after adding 3 elements:");
System.out.println(linkedList);
System.out.println("element #2 of my list:");
System.out.println(linkedList.get(2));
linkedList.remove(1);
System.out.println("my list after removing #1:");
System.out.println(linkedList);
linkedList.add(1,"first");
System.out.println("my list after adding an element in the middle");
System.out.println(linkedList);
}
運行這個程序的結果:
my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]
GO TO FULL VERSION