目錄

1）雙端隊列的介紹

2）雙端隊列用雙鏈表的實現代碼演示

3）雙端隊列用固定數組的實現

代碼演示

---

視頻

【算法講解016【入門】雙端隊列-雙鏈表和固定數組實現】

Leecode

leecode641 設計循環雙端隊列

---

1）雙端隊列的介紹

可以從頭部進，可以從頭部出；也可以從尾部進，可以從尾部出。這種結構叫雙端隊列

雙向鏈表為了跳轉容易，在數外邊設置一個節點包著，前指針，后指針。

比如我之前有個a，頭指空，尾指空。

我現在又加了個b，那么b的頭指針指向a，尾指針指向空，尾巴來到b上

我再加個c，一樣的。我又想在頭部加個d，一樣思路所以頭部加數 尾部加數就會了

頭部彈出 尾部彈出怎么辦？

頭部彈出

頭移到a，a的前指針指向null，c或c++的同學把d釋放掉，java會自己釋放不用管。

同樣方法把a彈出。

想從尾部彈出呢？

尾巴向前跳一個，讓b的next指針指向空。c或c++的同學把d釋放掉，java會自己釋放不用管。

2）雙端隊列用雙鏈表的實現代碼演示

package C16;import java.util.Deque;
import java.util.LinkedList;public class Video_016_Deque {class MyCircularDeque1{//Deque是接口 <Integer>是泛型，相當于Deque<Integer> 的意思就是：“這是一個雙端隊列，并且我給它貼上了**‘只能存放整數 (Integer)’**的標簽。”public Deque<Integer> deque = new LinkedList<>();//“我要聲明 (declare) 一個變量，它的名字叫 deque。這個變量是 public（公開）的，并且它的類型是一個貼著 Integer（整數）標簽的 Deque（雙端隊列功能清單）。”public int size;public int limit;/*** 初始化一個容量為k的雙端隊列* @param k 隊列的容量*/public MyCircularDeque1(int k){//“現在，我要創建一個真正能干活的工人（new LinkedList<>()），這個工人完全遵守了 Deque 的規范，然后讓我的 deque 變量去管理（指向）這個工人。”deque = new LinkedList<>();//初始時，隊列中沒有元素size = 0;//設置容量上限limit = k;}/*** 將一個元素添加到隊首，如果操作成功，返回true*/public boolean insertFront(int value) {//在插入前檢查隊列是否已滿if(isFull()){return false;//滿了，添加失敗}//調用LinkList自帶的方法offerFirst(),它會高效地將元素添加到鏈表頭部deque.offerFirst(value);//元素數量加1size++;//插入成功return true;}/*** 將一個元素添加到隊尾，如果操作成功返回true*/public boolean insertLast(int value){//同樣先檢查隊列是否已經滿了if(isFull()){return false;}//調用自帶的方法offerLast()，它會高效地將元素添加到鏈表尾部deque.offerLast(value);size++;return true;}/*** 從隊首刪除一個元素，如果操作成功返回true*/public boolean deleteFront(){//跟之前一樣的操作if(isEmpty()){return false;}deque.pollFirst();size--;return true;}public boolean deleteLast(){if(isEmpty()){return false;}deque.pollLast();size--;return true;}/*** 從隊首獲取元素，如果隊列為空返回-1*/public  int getFront(){if (isEmpty()) {return -1;}// 調用 LinkedList 自帶的 peekFirst()，它只查看頭部的元素，不移除。return deque.peekFirst();}/*** 獲取隊尾元素。如果隊列為空，返回 -1。* @return 隊尾的元素，或 -1。*/public int getRear() {if (isEmpty()) {return -1;}// 調用 LinkedList 自帶的 peekLast()，它只查看尾部的元素，不移除。return deque.peekLast();}/*** 檢查雙端隊列是否為空。* @return 為空返回 true，否則返回 false。*/public boolean isEmpty() {// 我們自己維護了 size 變量，用它來判斷最簡單。return size == 0;}/*** 檢查雙端隊列是否已滿。* @return 已滿返回 true，否則返回 false。*/public boolean isFull() {// 當 size 達到容量上限時，隊列就滿了。return size == limit;}}
}

3）雙端隊列用固定數組的實現

用固定數組（動態也可以）

size，l，r

有沒有數字或者滿沒滿，size管。如果size等于0，那么l和r等于啥都沒意義。

當加入數字a時，把a放在第零位，l到r位置上放a。即第零位到第零位放a。size變為1。

再加入b，r變為第一位。size再加1。

再加c

再加d。

頭部再加個e。

怎么做？

l已經在第零位了，怎么辦？

加到最后的位置上。

一共不是k位嗎？這道題k是10，所以l來到第k-1位置上，即第9位。所以說總結頭部添加的辦法：當l==0時，放在第k-1位，l=k-1；

當l≠0時，放在第l-1位，l--。

比如再在頭部加個f所以現在從頭部到尾部的就是890123這樣的順序。

如果再在頭部加個g彈出呢？

從頭部彈出，也就是l往右竄。即總結為：頭部加數那么l往左竄，頭部彈數則l往右竄。這就是l的邏輯。

模擬一下全過程

原來是這樣

彈出g

彈出f彈出e..

彈出a

彈出b

?

加入k加入s，加入p，加入l，加入n...

在尾部加入M

所以現在的整個隊列就是cdkspcznm

從尾巴彈出總結一下：

從頭部加入，l向左走，如果l==0，把數放在k-1的位置，然后賦值l=k-1；

如果l≠0，那么把數放在l-1的位置，然后賦值l--；

從頭部出，首先給用戶l位置的數[l]，如果l==k-1，那么賦值l=0；

如果l≠k-1，那么賦值l++；

從尾部入，如果l==k-1，把數放在0的位置，然后賦值r=0；

如果r≠k-1，那么把數放在r+1的位置，然后賦值r++；

從尾出，首先給用戶r位置的數[r]，然后要往左走，所以如果r==0，那么r賦值為k-1，即第k-1位；

如果r≠0呢？從尾出那么就是r--就行了。

這就是所有的邏輯 環形雙端隊列

代碼演示

public class MyCircularDeque2 {//底層的數據容器，一個固定大小的數組public  int[] deque;//l:left/front指針，指向隊頭元素所在的索引//r：right/rear指針，指向隊尾元素所在的索引//size:當前隊列中的元素數量//limit：隊列的容量上限（數組的大小）public int l,r,size,limit;/*** 構造方法：初始化一個容量為k的雙端隊列*/public MyCircularDeque2(int k){//創建一個能容納k個整數的數組deque = new int[k];//初始時，所有指針和計數器都為0（或者一個無效狀態）l = r = size = 0;//設置容量上限limit = k;}/*** 將一個元素添加到隊首*/public boolean insertFront(int value){//先檢查是否已經滿if(isEmpty()){//隊頭和隊尾指針都指向0號位置l = r = 0;//在0號位置放入新元素deque[0] = value;}else{//如果不為空，我們需要l往左移動，但如果它本來就在最左邊，所以我們將它移動到limit-1位置上l = l ==0?(limit - 1):(l - 1);//在計算出的新位置l放入元素deque[1] = value;}//元素數量加1size++;return true;}/*** 將一個元素添加到隊尾。*/public boolean insertLast(int value) {if (isFull()) {return false;}if (isEmpty()) {// 和 insertFront 一樣，第一個元素 l 和 r 都指向 0l = r = 0;deque[0] = value;} else {// 移動 r 指針，為新元素在“后面”騰出位置// 這是另一個“循環”的關鍵！// r == limit - 1 ? 0 : (r + 1)// 意思是：// 如果 r 指針已經在末尾了 (limit - 1)，那么它的“后一個”位置就是環繞到開頭的 0。// 否則，它的后一個位置就是 r + 1。r = r == limit - 1 ? 0 : (r + 1);// 在計算出的新位置 r 放入元素deque[r] = value;}size++;return true;}/*** 從隊首刪除一個元素。*/public boolean deleteFront() {if (isEmpty()) {return false;}// 刪除隊首元素，我們只需要把 l 指針向“后”移動一位即可// 同樣是循環移動// l == limit - 1 ? 0 : (l + 1)// 意思是：如果 l 在末尾，下一個位置是 0；否則是 l + 1l = l == limit - 1 ? 0 : (l + 1);// 元素數量減 1size--;return true;}/*** 從隊尾刪除一個元素。*/public boolean deleteLast() {if (isEmpty()) {return false;}// 刪除隊尾元素，我們只需要把 r 指針向“前”移動一位// 循環移動// r == 0 ? (limit - 1) : (r - 1)// 意思是：如果 r 在開頭，前一個位置是 limit - 1；否則是 r - 1r = r == 0 ? (limit - 1) : (r - 1);size--;return true;}/*** 從隊首獲取元素。*/public int getFront() {if (isEmpty()) {return -1;}// 隊首元素就是 l 指針指向的元素return deque[l];}/*** 獲取隊尾元素。*/public int getRear() {if (isEmpty()) {return -1;}// 隊尾元素就是 r 指針指向的元素return deque[r];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == limit;}}