Deque接口簡介
Deque譯為雙端隊列,在雙向都能作為隊列來使用,同時可用作棧。Deque接口的方法是對稱成比例的。
Deque接口繼承Queue接口,因此具有Queue,Collection,Iterable的方法屬性。
雙端隊列的工作原理
在常規隊列中,元素是從后面添加的,而從前面刪除的。但是,在雙端隊列中,我們可以從前后插入和刪除元素。
實現Deque的類
為了使用Deque接口的功能,我們需要使用實現接口的類:
-
ArrayDeque
-
LinkedList
如何使用Deque?
在Java中,我們必須導入要使用Deque的包 java.util.Deque 。
Deque<String> animal1 = new ArrayDeque<>();Deque<String> animal2 = new LinkedList<>();
在這里,我們分別創建了類ArrayDeque和LinkedList的對象animal1和animal2。 這些對象可以使用Deque接口的功能。
Deque的方法
Deque接口定義了以下方法:
方法 | 描述 |
---|---|
void addFirst(E e) | 將元素插入此deque的開頭 |
void addLast(E e) | 將元素插入此deque的末尾 |
boolean offerFirst(E e) | 在此deque的開頭插入指定元素。 |
boolean offerLast(E e) | 在此deque的末尾插入指定元素。 |
E removeFirst() | 檢索并刪除此deque的第一個元素 |
E removeLast() | 檢索并刪除此deque的最后一個元素 |
E pollFirst() | 檢索并刪除此deque的第一個元素;如果deque為空,則返回null |
E pollLast() | 檢索并刪除此deque的最后一個元素;如果deque為空,則返回null |
E getFirst() | 檢索但不刪除此deque的第一個元素。 |
E getLast() | 檢索但不刪除此deque的最后一個元素。 |
E peekFirst() | 檢索但不刪除此deque的第一個元素;如果deque為空,則返回null |
E peekLast() | 檢索但不刪除此deque的最后一個元素;如果deque為空,則返回null |
boolean removeFirstOccurrence(Object o) | 從deque中刪除第一次出現的指定元素(從頭部到尾部遍歷deque時)。 |
boolean removeLastOccurrence(Object o) | 從deque中刪除最后一次出現的指定元素(從頭部到尾部遍歷deque時)。 |
boolean add(E e) | 將指定元素添加到此deque的末尾。 |
boolean offer(E e) | 將指定元素添加到此deque的末尾。 |
E remove() | 檢索并刪除此deque的頭部。 |
E poll() | 檢索并刪除此deque的頭部;如果deque為空,則返回null。 |
E element() | 檢索但不刪除此deque的頭部。 |
E peek() | 檢索但不刪除此deque的頭部;如果deque為空,則返回null。 |
void push(E e) | 將元素推入此deque的堆棧層次結構中,也就是在deque的頭部插入一個元素。 |
E pop() | 從此deque表示的堆棧處彈出一個元素,也就是把deque的頭部元素移除掉。 |
boolean contains(Object o) | 如果此deque包含指定元素,則返回true。 |
int size() | 返回deque中的元素數。 |
Iterator<E> iterator() | 返回一個按元素插入順序遍歷此deque中元素的迭代器。 |
Iterator<E> descendingIterator() | 返回一個按元素逆序遍歷此deque中元素的迭代器。 |
雙端隊列作為堆棧數據結構
Java Collections框架的Stack類提供了堆棧的實現。
但是,建議Deque用作堆棧而不是Stack類。這是因為Stack的方法是同步的。
以下是Deque接口提供的用于實現堆棧的方法:
-
push() - 在雙端隊列的開頭添加元素
-
pop() - 從雙端隊列的開頭刪除元素
-
peek() - 從雙端隊列的開頭返回一個元素
Deque是可以用作棧或隊列的,具體是哪個取決于使用哪些方法。下面是一些示例代碼,演示了如何使用Deque接口。
1. 使用Deque作為隊列
import java.util.Deque;
import java.util.LinkedList;public class Deque{public static void main(String[] args) {Deque<String> queue = new LinkedList<>();// 添加元素到隊列queue.add("Java");queue.add("C++");queue.add("Python");// 獲取隊列的第一個元素,不刪除System.out.println("First element of queue: " + queue.peek());// 獲取并刪除隊首元素String firstElement = queue.poll();System.out.println("Removed first element of queue: " + firstElement);// 隊列中添加一個新元素queue.offer("JavaScript");// 遍歷隊列中的元素System.out.println("All elements of queue:");for (String element : queue) {System.out.println(element);}}
}
此代碼將Deque用作隊列,使用add方法添加元素,并使用peek獲取第一個元素。然后,使用poll方法刪除并獲取隊列中的第一個元素,并使用offer方法將新元素添加到隊列末尾。最后,使用for-each循環遍歷隊列中的所有元素。
2. 使用Deque作為棧
import java.util.Deque;
import java.util.LinkedList;public class Deque{public static void main(String[] args) {Deque<String> stack = new LinkedList<>();// 將元素推入棧中stack.push("Java");stack.push("C++");stack.push("Python");// 獲取棧頂元素,不刪除System.out.println("Top element of stack: " + stack.peek());// 獲取并刪除棧頂元素String topElement = stack.pop();System.out.println("Removed top element of stack: " + topElement);// 將新元素推入棧中stack.push("JavaScript");// 遍歷棧中的所有元素System.out.println("All elements of stack:");for (String element : stack) {System.out.println(element);}}
}
此代碼演示了如何將Deque用作棧。它使用push方法將元素推入棧中,并使用peek獲取棧頂元素。然后,使用pop方法獲取并刪除棧頂元素,并使用push方法將新元素推入棧頂。最后,使用for-each循環遍歷棧中的所有元素。
創建ArrayDeque
為了創建ArrayDeque雙端隊列,我們必須導入java.util.ArrayDeque包。
這是我們可以用Java創建ArrayDeque雙端隊列的方法:
ArrayDeque<Type> animal = new ArrayDeque<>();
在此,Type表示ArrayDeque雙端隊列的類型。例如,
//創建字符串類型ArrayDeque
ArrayDeque<String> animals = new ArrayDeque<>();//創建整數類型ArrayDeque
ArrayDeque<Integer> age = new ArrayDeque<>();
ArrayDeque方法
ArrayDeque類提供了所有的存在于方法Queue和Deque接口。
將元素插入雙端隊列
1.使用add(),addFirst()和addLast()添加元素
add() - 將指定的元素插入ArrayDeque雙端隊列的末尾
addFirst() -在ArrayDeque雙端隊列的開頭,插入指定的元素
addLast() - 在ArrayDeque雙端隊列的末尾插入指定的內容(等效于add())
注意:如果ArrayDeque雙端隊列已滿,則所有這些方法add(),addFirst()和addLast()都會引發IllegalStateException。
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();//使用add ()animals.add("Dog");//使用addFirst ()animals.addFirst("Cat");//使用addLast()animals.addLast("Horse");System.out.println("ArrayDeque: " + animals);}
}
輸出結果
ArrayDeque: [Cat, Dog, Horse]
2.使用 offer(),offerFirst()和offerLast()插入元素
offer() - 將指定的元素插入ArrayDeque雙端隊列的末尾
offerFirst() - 在ArrayDeque雙端隊列的開始處插入指定的元素
offerLast() - 將指定的元素插入ArrayDeque雙端隊列的末尾
注意: offer(),offerFirst()并offerLast()返回true是否成功插入元素;否則,返回。如果ArrayDeque雙端隊列已滿,則這些方法返回false。
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();//使用offer()animals.offer("Dog");//使用offerFirst()animals.offerFirst("Cat");//使用offerLast()animals.offerLast("Horse");System.out.println("ArrayDeque: " + animals);}
}
輸出結果
ArrayDeque: [Cat, Dog, Horse]
訪問ArrayDeque元素
1.使用getFirst()和getLast()訪問元素
getFirst() - 返回ArrayDeque雙端隊列的第一個元素
getLast() - 返回ArrayDeque雙端隊列的最后一個元素
注:如果ArrayDeque雙端隊列為空,getFirst()和getLast()拋出NoSuchElementException。
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Horse");System.out.println("ArrayDeque: " + animals);// 獲取第一個元素String firstElement = animals.getFirst();System.out.println("第一個元素: " + firstElement);//獲取最后一個元素String lastElement = animals.getLast();System.out.println("最后一個元素: " + lastElement);}
}
輸出結果
ArrayDeque: [Dog, Cat, Horse]
第一個元素: Dog
最后一個元素: Horse
2.使用peek(),peekFirst()和peekLast()方法訪問元素
peek() - 返回ArrayDeque雙端隊列的第一個元素
peekFirst() - 返回ArrayDeque雙端隊列的第一個元素(等效于peek())
peekLast() - 返回ArrayDeque雙端隊列的最后一個元素
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Horse");System.out.println("ArrayDeque: " + animals);//使用peek()String element = animals.peek();System.out.println("頭元素: " + element);//使用peekFirst()String firstElement = animals.peekFirst();System.out.println("第一個元素: " + firstElement);//使用peekLastString lastElement = animals.peekLast();System.out.println("最后一個元素: " + lastElement);}
}
輸出結果
ArrayDeque: [Dog, Cat, Horse]
Head Element: Dog
第一個元素: Dog
最后一個元素: Horse
注意:如果ArrayDeque雙端隊列為空,peek(),peekFirst()和getLast()拋出NoSuchElementException。
刪除 ArrayDeque 元素
1.使用remove(),removeFirst(),removeLast()方法刪除元素
remove() - 返回并從ArrayDeque雙端隊列的第一個元素中刪除一個元素
remove(element) - 返回并從ArrayDeque雙端隊列的頭部刪除指定的元素
removeFirst() - 返回并從ArrayDeque雙端隊列中刪除第一個元素(等效于remove())
removeLast() - 返回并從ArrayDeque雙端隊列中刪除最后一個元素
注意:如果數組雙端隊列為空,則remove(),removeFirst()和removeLast()方法將引發異常。 另外,如果找不到元素,則remove(element)會引發異常。
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Cow");animals.add("Horse");System.out.println("ArrayDeque: " + animals);//使用remove()String element = animals.remove();System.out.println("刪除Element: " + element);System.out.println("新的ArrayDeque: " + animals);//使用removeFirst()String firstElement = animals.removeFirst();System.out.println("刪除第一個元素: " + firstElement);//使用removeLast()String lastElement = animals.removeLast();System.out.println("刪除最后一個元素: " + lastElement);}
}
輸出結果
ArrayDeque: [Dog, Cat, Cow, Horse]
刪除Element: Dog
新的ArrayDeque: [Cat, Cow, Horse]
刪除第一個元素: Cat
刪除最后一個元素: Horse
2.使用poll(),pollFirst()和pollLast()方法刪除元素
poll() - 返回并刪除ArrayDeque雙端隊列的第一個元素
pollFirst() - 返回并刪除ArrayDeque雙端隊列的第一個元素(等效于poll())
pollLast() - 返回并刪除ArrayDeque雙端隊列的最后一個元素
注意:如果ArrayDeque雙端隊列為空,則如果找不到該元素,則poll(),pollFirst()和pollLast()返回null。
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Cow");animals.add("Horse");System.out.println("ArrayDeque: " + animals);//使用poll()String element = animals.poll();System.out.println("刪除Element: " + element);System.out.println("新的ArrayDeque: " + animals);//使用pollFirst()String firstElement = animals.pollFirst();System.out.println("刪除第一個元素: " + firstElement);//使用pollLast()String lastElement = animals.pollLast();System.out.println("刪除最后一個元素: " + lastElement);}
}
輸出結果
ArrayDeque: [Dog, Cat, Cow, Horse]
刪除Element: Dog
新的ArrayDeque: [Cat, Cow, Horse]
刪除第一個元素: Cat
刪除最后一個元素: Horse
3.刪除元素:使用clear()方法
要從ArrayDeque雙端隊列中刪除所有元素,我們使用clear()方法。例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Horse");System.out.println("ArrayDeque: " + animals);//使用clear()animals.clear();System.out.println("新的ArrayDeque: " + animals);}
}
輸出結果
ArrayDeque: [Dog, Cat, Horse]
新的ArrayDeque: []
迭代遍歷ArrayDeque
iterator() - 返回可用于遍歷ArrayDeque雙端隊列的迭代器
descendingIterator() -返回一個迭代器,該迭代器可用于以相反順序遍歷ArrayDeque雙端隊列
為了使用這些方法,我們必須導入java.util.Iterator包。例如:
import java.util.ArrayDeque;
import java.util.Iterator;class Main {public static void main(String[] args) {ArrayDeque<String> animals= new ArrayDeque<>();animals.add("Dog");animals.add("Cat");animals.add("Horse");System.out.print("ArrayDeque: ");//使用iterator()Iterator<String> iterate = animals.iterator();while(iterate.hasNext()) {System.out.print(iterate.next());System.out.print(", ");}System.out.print("\n反向ArrayDeque: ");//使用descendingIterator()Iterator<String> desIterate = animals.descendingIterator();while(desIterate.hasNext()) {System.out.print(desIterate.next());System.out.print(", ");}}
}
輸出結果
ArrayDeque: [Dog, Cat, Horse]
反向ArrayDeque: [Horse, Cat, Dog]
其他方法
方法 | 內容描述 |
---|---|
element() | 從ArrayDeque雙端隊列的頭部返回一個元素。 |
contains(element) | 在ArrayDeque雙端隊列中搜索指定的元素。 如果找到該元素,則返回true,否則返回false。 |
size() | 返回ArrayDeque雙端隊列的長度。 |
toArray() | 將ArrayDeque雙端隊列轉換為數組并返回。 |
clone() | 創建ArrayDeque雙端隊列的副本并返回它。 |
ArrayDeque作為堆棧
要在Java中實現LIFO(后進先出)堆棧,建議在Stack類上使用雙端隊列。該ArrayDeque類比Stack類快。
ArrayDeque 提供了以下可用于實現堆棧的方法。
push() - 在堆棧頂部添加一個元素
peek() - 從堆棧頂部返回一個元素
pop() - 返回并從堆棧頂部刪除元素
例如:
import java.util.ArrayDeque;class Main {public static void main(String[] args) {ArrayDeque<String> stack = new ArrayDeque<>();//將元素添加到stackstack.push("Dog");stack.push("Cat");stack.push("Horse");System.out.println("Stack: " + stack);//從堆棧頂部訪問元素String element = stack.peek();System.out.println("訪問元素: " + element);//從堆棧頂部刪除元素String remElement = stack.pop();System.out.println("刪除element: " + remElement);}
}
輸出結果
Stack: [Horse, Cat, Dog]
訪問元素: Horse
刪除Element: Horse
ArrayDeque與 LinkedList類
ArrayDeque和Java的LinkedList都實現了Deque接口。但是,它們之間存在一些差異。
LinkedList支持空元素,而ArrayDeque不支持。
鏈表中的每個節點都包含到其他節點的鏈接。這就是LinkedList比ArrayDeque需要更多存儲空間的原因。
如果要實現隊列或雙端隊列數據結構,則ArrayDeque可能比LinkedList快。