手寫各種隊列，一文搞定

微信搜一搜【bigsai】更多精彩

的帥哥美女祝你們越學越猛

@TOC

前言

棧和隊列是一對好兄弟，前面我們介紹過一篇棧的文章(棧，不就后進先出)，棧的機制相對簡單，后入先出，就像進入一個狹小的山洞，山洞只有一個出入口，只能后進先出(在外面的先出去，堵在里面先進去的就有點倒霉)。而隊列就好比是一個隧道，后面的人跟著前面走，前面人先出去(先入先出)。日常的排隊就是隊列運轉形式的一個描述！

棧是一種喜新厭舊的數據結構，來了新的就會處理新的把老的先停滯在這(我們找人、約人辦事最討厭這種人)，隊列就是大公無私的一種數據結構，排隊先來先得，講究順序性，所以這種數據結構在程序設計、中間件等都非常廣泛的應用，例如消息隊列、FIFO磁盤調度、二叉樹層序遍歷、BFS寬度優先搜索等等。

隊列的核心理念就是：先進先出！

隊列的概念：隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

同時，閱讀本篇文章最好先弄懂順序表的基本操作和棧的數據結構！學習效果更佳！

隊列介紹

我們設計隊列時候可以選擇一個標準，這里就拿力扣622設計循環隊列作為隊列設計的標準。

**隊頭front：**刪除數據的一端。

隊尾rear 插入數據的一端。

對于數組，從數組后面插入更容易，數組前面插入較困難，所以一般用數組實現的隊列隊頭在數組前面，隊尾在數組后面；而對于鏈表，插入刪除在兩頭分別進行那么頭部(前面)刪除尾部插入最方便的選擇。

實現方法：

MyCircularQueue(k): 構造器，設置隊列長度為 k 。

Front: 從隊首獲取元素。如果隊列為空，返回 -1 。

Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。

enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。

deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。

isEmpty(): 檢查循環隊列是否為空。

isFull(): 檢查循環隊列是否已滿。

普通隊列

按照上述的介紹，我們很容易知道數組實現的方式。用數組模擬表示隊列。要考慮初始化，插入，問題。

在這個普通隊列一些操作需要注意的有：

初始化：數組的front和rear都指向0. (front和rear下標相等的時候說明隊列為空)

入隊：隊不滿，數組不越界，先隊尾位置傳值，再隊尾下標+1(隊尾rear實際上超前一位，為了區分空隊列情況)

出隊：隊不空，先取隊頭位置元素，在隊頭+1。

但是很容易發現問題，每個空間域只能利用一次，造成空間極度浪費，非常容易越界！

循環隊列(數組實現)

針對上述的問題。有個較好的解決方法！就是對已經申請的(數組)內存重復利用。這就是我們所說的循環隊列。循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。

數組實現的循環隊列就是在邏輯上作修改。因為我們隊列中只需要front和rear兩個指針。rear在邏輯上在后面，front在邏輯上是在前面的，但實際上它們不一定誰在前誰在后，在計算距離的時候需要給rear先補上數組長度減去front，然后求余即可。

初始化：數組的front和rear都指向0. 這里需要注意的是：front和rear位于同一個位置時候，證明隊列里面是空的。還有在這里我具體實現時候將數組申請大了一個位置空出來，防止隊列滿的情況又造成front和rear在同一個位置。

入隊：隊不滿，先隊尾位置傳值，再rear=(rear + 1) % maxsize;

出隊：隊不空，先取隊頭位置元素，front=(front + 1)% maxsize;

這里出隊入隊指標相加如果遇到最后需要轉到頭位置，這里直接+1求余找到位置(相比判斷是否在最后更加簡潔)，其中maxsize是數組實際大小。

是否為空：return rear == front;

大小：return (rear+maxsize-front)%maxsize; 這里很容易理解，一張圖就能解釋清楚，無論是front實際在前在后都能滿足要求。

這里面有幾個大家需要注意的，就是指標相加如果遇到最后需要轉到頭的話。可以判斷是否到數組末尾位置。也可以直接+1求余。其中maxsize是數組實際大小。

具體實現：

public class MyCircularQueue { private int data[];// 數組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長度 public MyCircularQueue(int k) { data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } public boolean enQueue(int value) { if (isFull()) return false; else { data[rear] = value; rear=(rear + 1) % maxsize; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } public int Front() { if(isEmpty()) return -1; return data[front]; } public int Rear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % maxsize == front; } }

循環隊列(鏈表實現)

對于鏈表實現的隊列，要根據先進先出的規則考慮頭和尾的位置

我們知道隊列是先進先出的，對于鏈表，我們能采用單鏈表盡量采用單鏈表，能方便盡量方便，同時還要兼顧效率。使用鏈表大概有兩個實現方案：

方案一 如果隊列頭設在鏈表尾，隊列尾設在鏈表頭。那么隊尾進隊插入在鏈表頭部插入沒問題，容易實現，但是如果隊頭刪除在鏈表尾部進行，如果不設置尾指針要遍歷到隊尾，但是設置尾指針刪除需要將它前驅節點需要雙向鏈表，都挺麻煩的。

方案二如果隊列頭設在鏈表頭，隊列尾設在鏈表尾，那么隊尾進隊插入在鏈表尾部插入沒問題(用尾指針可以直接指向next)，容易實現，如果隊頭刪除在鏈表頭部進行也很容易，就是我們前面常說的頭節點刪除節點。

所以我們最終采取的是方案2的帶頭節點、帶尾指針的單鏈表!

主要操作為：

初始化：設立一個頭結點，是front和rear都先指向它。

入隊：rear.next=va;rear=va;（va為被插入節點）

出隊：隊不空，front.next=front.next.next;經典帶頭節點刪除，但是如果僅有一個節點刪除時候，需要多加一個rear=front，不然rear就失聯啦。

是否為空：return rear == front; 或者自定義維護len判斷return len==0

大小：節點front遍歷到rear的個數，或者自定義維護len直接返回(這里并沒實現)。

實現代碼：

public class MyCircularQueue{ class node { int data;// 節點的結果 node next;// 下一個連接的節點 public node() {} public node(int data) { this.data = data; } } node front;//相當于head 帶頭節點的 node rear;//相當于tail/end int maxsize;//最大長度 int len=0; public MyCircularQueue(int k) { front=new node(0); rear=front; maxsize=k; len=0; } public boolean enQueue(int value) { if (isFull()) return false; else { node va=new node(value); rear.next=va; rear=va; len++; } return true; } public boolean deQueue() { if (isEmpty()) return false; else { front.next=front.next.next; len--; //注意 如果被刪完 需要將rear指向front if(len==0) rear=front; } return true; } public int Front() { if(isEmpty()) return -1; return front.next.data; } public int Rear() { if(isEmpty()) return -1; return rear.data; } public boolean isEmpty() { return len==0; //return rear == front; } public boolean isFull() { return len==maxsize; } }

雙向隊列(加餐)

設計實現雙端隊列，其實你經常使用的ArrayDeque就是一個經典的雙向隊列，其基于數組實現，效率非常高。我們這里實現的雙向隊列模板基于力扣641 設計循環雙端隊列 。

你的實現需要支持以下操作：

MyCircularDeque(k)：構造函數,雙端隊列的大小為k。

insertFront()：將一個元素添加到雙端隊列頭部。 如果操作成功返回 true。

insertLast()：將一個元素添加到雙端隊列尾部。如果操作成功返回 true。

deleteFront()：從雙端隊列頭部刪除一個元素。 如果操作成功返回 true。

deleteLast()：從雙端隊列尾部刪除一個元素。如果操作成功返回 true。

getFront()：從雙端隊列頭部獲得一個元素。如果雙端隊列為空，返回 -1。

getRear()：獲得雙端隊列的最后一個元素。 如果雙端隊列為空，返回 -1。

isEmpty()：檢查雙端隊列是否為空。

isFull()：檢查雙端隊列是否滿了。

其實有了上面的基礎，實現一個雙端隊列非常容易，有很多操作和單端的循環隊列是一致的，只有多了一個隊頭插入和隊尾刪除的操作，兩個操作分別簡單的分析一下：

隊頭插入：隊友front下標位置本身是有值的，所以要將front退后一位然后再賦值，不過要考慮是否為滿或者數組越界情況。

隊尾刪除：只需要rear位置減1，同時也要考慮是否為空和越界情況。

具體實現代碼：

public class MyCircularDeque { private int data[];// 數組容器 private int front;// 頭 private int rear;// 尾 private int maxsize;// 最大長度 /*初始化 最大大小為k */ public MyCircularDeque(int k) { data = new int[k+1]; front = 0; rear = 0; maxsize = k+1; } /** 頭部插入 */ public boolean insertFront(int value) { if(isFull()) return false; else { front=(front+maxsize-1)%maxsize; data[front]=value; } return true; } /** 尾部插入 */ public boolean insertLast(int value) { if(isFull()) return false; else{ data[rear]=value; rear=(rear+1)%maxsize; } return true; } /** 正常頭部刪除 */ public boolean deleteFront() { if (isEmpty()) return false; else { front=(front+1)%maxsize; } return true; } /** 尾部刪除 */ public boolean deleteLast() { if(isEmpty()) return false; else { rear=(rear+maxsize-1)%maxsize; } return true; } /** Get the front item */ public int getFront() { if(isEmpty()) return -1; return data[front]; } /** Get the last item from the deque. */ public int getRear() { if(isEmpty()) return -1; return data[(rear-1+maxsize)%maxsize]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty() { return front==rear; } /** Checks whether the circular deque is full or not. */ public boolean isFull() { return (rear+1)%maxsize==front; } }

總結

對于隊列來說數據結構相比棧復雜一些，但是也不是很難，搞懂先進先出然后用數組或者鏈表實現即可。

對于數組，隊尾tail指向的位置是空的，而鏈表的front（head一樣）為頭指針為空的，所以在不同結構實現相同效果的方法需要注意一下。

數組實現的循環隊列能夠很大程度利用數組空間，而雙向隊列則是既能當隊列又能當棧的一種高效數據結構，掌握還是很有必要的。

最后，筆者水平有限，如果有紕漏和不足之處還請指出。另外，如果感覺不錯可以點個贊，關注個人公眾號：bigsai 更多經常與你分享，關注回復bigsai獲取精心準備的學習資料一份！

Java 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。