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

隊列與棧的概念

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

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

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

面試官問我什么是「?！?，我隨手畫了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)缺點

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