關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容

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

作者：李肖遙

隊(duì)列與棧的概念

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

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

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

面試官問我什么是「?！?，我隨手畫了10張圖來解釋

雙端隊(duì)列的概念

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

雙端隊(duì)列的代碼實(shí)現(xiàn)

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

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

代碼如下：

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

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

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


隊(duì)首入隊(duì)

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

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

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

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

???return?true;
}


隊(duì)首出隊(duì)

代碼如下：

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

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

???return?temp;
}


隊(duì)尾入隊(duì)

雙端隊(duì)列是可以在隊(duì)列的兩端進(jìn)行插入和刪除的，tail指針指向元素的下一個(gè)位置，而head指針指向當(dāng)前元素。

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

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

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

????return?true;
}


隊(duì)尾出隊(duì)

和隊(duì)尾入隊(duì)一樣，只要將tail指針逆時(shí)針下移一個(gè)位置即可，代碼如下：

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

????//逆時(shí)針旋轉(zhuǎn)(防止負(fù)數(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ī)律？

從上面的四個(gè)方法可以看出：

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

• 當(dāng)我們只使用Push Tail指針和Pop Head指針的話，那它就是隊(duì)列。

優(yōu)缺點(diǎn)

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

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