拋磚引玉 | 圖解雙端隊(duì)列Deque

雙端隊(duì)列的概念

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

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

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

通常隊(duì)列的內(nèi)部采用數(shù)組來(lái)實(shí)現(xiàn)，為了充分利用數(shù)組空間，使用%來(lái)實(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ì)列是否為滿(mǎn)或者隊(duì)列是否為空
    public T[] list;

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

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

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

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

/// 隊(duì)首入隊(duì)
public bool Push_Head(T t)
{
    //判斷隊(duì)列是否已滿(mǎn)
    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];
   //原來(lái)單位的值賦默認(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ì)列是否已滿(mǎn)
    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指針的話(huà)，那它就是棧。

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

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

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