目錄
- 1.Deque的概念
- 2.雙端佇列操作
- 3.雙端佇列演示示例
- 4.雙端佇列典型應用（滑動視窗/單調堆疊問題）
1.Deque的概念
雙向佇列：支持在首尾插入和洗掉元素的線性集合，它具有既具有FIFO(先進先出)特點又具有LIFO(后進先出)的特點，即是佇列又是堆疊；
java官方檔案推薦用deque實作堆疊（stack），
在Java中，Queue的實作類一般都是用LinkedList，
特點：
- 1.插入、洗掉、獲取操作支持兩種形式：快速失敗和回傳null或true/false
- 2.既具有FIFO特點又具有LIFO特點，即是佇列又是堆疊
- 3.不推薦插入null元素，null作為特定回傳值表示佇列為空
- 4.未定義基于元素相等的equals和hashCode
2.雙端佇列操作
插入元素
| 方法名 | 描述 |
|---|---|
| addFirst() | 向隊頭插入元素，如果元素為空，則發生空指標例外 |
| addLast() | 向隊尾插入元素，如果為空，則發生空指標例外 |
| offerFirst() | 向隊頭插入元素，如果插入成功回傳true，否則回傳false |
| addLast() | 向隊尾插入元素，如果插入成功回傳true，否則回傳false |
洗掉元素
| 方法名 | 描述 |
|---|---|
| removeFirst() | 回傳并移除隊頭元素，如果該元素是null，則發生NoSuchElementException |
| removeLast() | 回傳并移除隊尾元素，如果該元素是null，則發生NoSuchElementException |
| offerFirst() | 回傳并移除隊頭元素，如果佇列無元素，則回傳null |
| pollLast() | 回傳并移除隊尾元素，如果佇列無元素，則回傳null |
獲取元素
| 方法名 | 描述 |
|---|---|
| getFirst() | 獲取隊頭元素但不移除，如果佇列無元素，則發生NoSuchElementException |
| getLast() | 獲取隊尾元素但不移除，如果佇列無元素，則發生NoSuchElementException |
| peekFirst() | 獲取隊頭元素但不移除，如果佇列無元素，則回傳null |
| peekLast() | 獲取隊尾元素但不移除，如果佇列無元素，則回傳null |
堆疊操作
| 方法名 | 描述 |
|---|---|
| pop() | 彈出堆疊中元素，也就是回傳并移除隊頭元素，等價于removeFirst()，如果佇列無元素，則發生NoSuchElementException |
| push() | 向堆疊中壓入元素，也就是向隊頭增加元素，等價于addFirst()，如果元素為null，則發生NPE，如果堆疊空間受到限制，則發生IllegalStateException |
判斷為空條件
| 方法名 | 描述 |
|---|---|
| isEmpty() | 于檢查此雙端佇列是“空”還是“非空”,不會引發例外 |
主要實作類:
ArrayDeque: 基于陣列實作的線性雙向佇列
LinkedList: 基于鏈表實作的鏈式雙向佇列
3.雙端佇列演示示例
public static void main(String[] args) {
Deque<Integer> deque=new LinkedList<Integer>();
deque.offerLast(10);
deque.offerLast(15);
deque.offerLast(20);
deque.offerFirst(5);
System.out.println("彈出隊首元素"+deque.pollFirst());
System.out.println("彈出隊尾元素"+deque.pollLast());
System.out.println("查看此時隊尾元素"+deque.peekLast());
System.out.println("判斷佇列是否為空"+deque.isEmpty());
}
4.雙端佇列典型應用（滑動視窗/單調堆疊問題）
單調佇列問題
劍指 Offer 59 - I. 滑動視窗的最大值
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/260041.html
標籤：java
下一篇：Web全堆疊~33.執行緒的中斷