拋磚引玉 | 圖解雙端隊列Deque

關(guān)注、星標公眾號，直達精彩內(nèi)容

來源：技術(shù)讓夢想更偉大

作者：李肖遙

隊列與棧的概念

隊列（queue）是限定在表的一端進行插入，表的另一端進行刪除的數(shù)據(jù)結(jié)構(gòu)

真香！20張圖揭開「隊列」的迷霧，一目了然

棧（stack）是限定僅在表的一端進行操作的數(shù)據(jù)結(jié)構(gòu)，且棧是一種先進后出(FIFO)的數(shù)據(jù)結(jié)構(gòu)

面試官問我什么是「?！梗译S手畫了10張圖來解釋

雙端隊列的概念

雙端隊列又名double ended queue，簡稱deque，雙端隊列沒有隊列和棧這樣的限制級，它允許兩端進行入隊和出隊操作，也就是說元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

雙端隊列的代碼實現(xiàn)

定義結(jié)構(gòu)體

通常隊列的內(nèi)部采用數(shù)組來實現(xiàn)，為了充分利用數(shù)組空間，使用%來實現(xiàn)邏輯上的循環(huán)數(shù)組，如下圖所示。

代碼如下：

public?class?MyQueue
{
????public?int?head;
????public?int?tail;
????public?int?maxSize;

????public?int?size;//統(tǒng)計隊列是否為滿或者隊列是否為空
????public?T[]?list;

????public?MyQueue()
????{
????????head?=?tail?=?size?=?0;
????????maxSize?=?3;
????????list?=?new?T[maxSize];
????}
??}


隊首入隊

如上圖所示，從head端來說，push數(shù)據(jù)時是head指針逆時針旋轉(zhuǎn)，head指針是指向當前元素。

這里注意要防止負數(shù)產(chǎn)生，代碼如下：

///?隊首入隊
public?bool?Push_Head(T?t)
{
????//判斷隊列是否已滿
????if?(myQueue.size?==?myQueue.list.Length)
???????return?false;

???//逆時針旋轉(zhuǎn)(防止負數(shù)產(chǎn)生)
???myQueue.head?=?(--myQueue.head? ?myQueue.maxSize)?%?myQueue.maxSize;
???//賦予元素
???myQueue.list[myQueue.head]?=?t;
???myQueue.size ;

???return?true;
}


隊首出隊

代碼如下：

//?隊首出隊
public?T?Pop_Head()
{
????//判斷隊列是否已空
????if?(myQueue.size?==?0)
???????return?default(T);

???//獲取隊首元素
???var?temp?=?myQueue.list[myQueue.head];
???//原來單位的值賦默認值
???myQueue.list[myQueue.head]?=?default(T);
???//順時針旋轉(zhuǎn)
???myQueue.head?=?(myQueue.head? ?1)?%?myQueue.maxSize;
???myQueue.size--;

???return?temp;
}


隊尾入隊

雙端隊列是可以在隊列的兩端進行插入和刪除的，tail指針指向元素的下一個位置，而head指針指向當前元素。

如上圖所示，從tail端push數(shù)據(jù)的時候順時針下移一個位置即可，代碼如下：

///?隊尾入隊
public?bool?Push_Tail(T?t)
{
????//判斷隊列是否已滿
????if?(myQueue.size?==?myQueue.list.Length)
???????return?false;

????myQueue.list[myQueue.tail]?=?t;
????//順時針旋轉(zhuǎn)
????myQueue.tail?=?(myQueue.tail? ?1)?%?myQueue.maxSize;
????myQueue.size ;

????return?true;
}


隊尾出隊

和隊尾入隊一樣，只要將tail指針逆時針下移一個位置即可，代碼如下：

///?隊尾出隊
public?T?Pop_Tail()
{
????//判斷隊列是否已空
????if?(myQueue.size?==?0)
????????return?default(T);

????//逆時針旋轉(zhuǎn)(防止負數(shù))
????myQueue.tail?=?(--myQueue.tail? ?myQueue.maxSize)?%?myQueue.maxSize;
????var?temp?=?myQueue.list[myQueue.tail];
????//賦予空值
????myQueue.list[myQueue.tail]?=?default(T);
????myQueue.size--;

????return?temp;
}


有什么規(guī)律？

從上面的四個方法可以看出：

• 當我們只使用Push Tail指針和Pop Tail指針的話，那它就是棧。

• 當我們只使用Push Tail指針和Pop Head指針的話，那它就是隊列。

優(yōu)缺點

雙端隊列其實和隊列差不多的，只是更加靈活了，隊頭和隊尾均可進行入隊和出隊操作，但實際上在應(yīng)用程序中遠不及棧和隊列有用。本文就起個拋磚引玉的作用，幫助大家了解一下雙端隊列，具體應(yīng)用見。

???????????????? ?END ?????????????????