此賬号為華為雲開發者社區官方運營賬号，提供全面深入的雲計算前景分析、豐富的技術幹貨、程序樣例，分享華為雲前沿資訊動态
本文分享自華為雲社區《手寫各種隊列，一文搞定》，原文作者：bigsai 。
前言棧和隊列是一對好兄弟，棧的機制相對簡單，後入先出，就像進入一個狹小的山洞，山洞隻有一個出入口，隻能後進先出(在外面的先出去，堵在裡面先進去的就有點倒黴)。而隊列就好比是一個隧道，後面的人跟着前面走，前面人先出去(先入先出)。日常的排隊就是隊列運轉形式的一個描述！
棧是一種喜新厭舊的數據結構，來了新的就會處理新的把老的先停滞在這(我們找人、約人辦事最讨厭這種人)，隊列就是大公無私的一種數據結構，排隊先來先得，講究順序性，所以這種數據結構在程序設計、中間件等都非常廣泛的應用，例如消息隊列、FIFO 磁盤調度、二叉樹層序遍曆、BFS 寬度優先搜索等等。
隊列的核心理念就是：先進先出！
隊列的概念：隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。
我們設計隊列時候可以選擇一個标準，這裡就拿力扣 622 設計循環隊列作為隊列設計的标準。
隊頭 front：删除數據的一端。
隊尾 rear ：插入數據的一端。
對于數組，從數組後面插入更容易，數組前面插入較困難，所以一般用數組實現的隊列隊頭在數組前面，隊尾在數組後面；而對于鍊表，插入删除在兩頭分别進行那麼頭部(前面)删除尾部插入最方便的選擇。
實現方法：
按照上述的介紹，我們很容易知道數組實現的方式。用數組模拟表示隊列。要考慮初始化，插入，問題。
在這個普通隊列一些操作需要注意的有：
初始化：數組的 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 是數組實際大小。
是否為空：returnrear == 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 就失聯啦。
是否為空：returnrear == front;或者自定義維護 len 判斷 returnlen==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 設計循環雙端隊列 。
你的實現需要支持以下操作：
其實有了上面的基礎，實現一個雙端隊列非常容易，有很多操作和單端的循環隊列是一緻的，隻有多了一個隊頭插入和隊尾删除的操作，兩個操作分别簡單的分析一下：
隊頭插入：隊友 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 一樣）為頭指針為空的，所以在不同結構實現相同效果的方法需要注意一下。
數組實現的循環隊列能夠很大程度利用數組空間，而雙向隊列則是既能當隊列又能當棧的一種高效數據結構，掌握還是很有必要的。
點擊關注，第一時間了解華為雲新鮮技術~
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
