抛砖引玉 | 图解双端队列Deque

双端队列的概念

双端队列又名double ended queue，简称deque，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队。

双端队列的代码实现

定义结构体

通常队列的内部采用数组来实现，为了充分利用数组空间，使用%来实现逻辑上的循环数组，如下图所示。

代码如下：

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

    public int size;//统计队列是否为满或者队列是否为空
    public T[] list;

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

队首入队

如上图所示，从head端来说，push数据时是head指针逆时针旋转，head指针是指向当前元素。

这里注意要防止负数产生，代码如下：

/// 队首入队
public bool Push_Head(T t)
{
    //判断队列是否已满
    if (myQueue.size == myQueue.list.Length)
       return false;

   //逆时针旋转(防止负数产生)
   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);
   //顺时针旋转
   myQueue.head = (myQueue.head + 1) % myQueue.maxSize;
   myQueue.size--;

   return temp;
}

队尾入队

双端队列是可以在队列的两端进行插入和删除的，tail指针指向元素的下一个位置，而head指针指向当前元素。

如上图所示，从tail端push数据的时候顺时针下移一个位置即可，代码如下：

/// 队尾入队
public bool Push_Tail(T t)
{
    //判断队列是否已满
    if (myQueue.size == myQueue.list.Length)
       return false;

    myQueue.list[myQueue.tail] = t;
    //顺时针旋转
    myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize;
    myQueue.size++;

    return true;
}

队尾出队

和队尾入队一样，只要将tail指针逆时针下移一个位置即可，代码如下：

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

    //逆时针旋转(防止负数)
    myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
    var temp = myQueue.list[myQueue.tail];
    //赋予空值
    myQueue.list[myQueue.tail] = default(T);
    myQueue.size--;

    return temp;
}

有什么规律？

从上面的四个方法可以看出：

• 当我们只使用Push Tail指针和Pop Tail指针的话，那它就是栈。

• 当我们只使用Push Tail指针和Pop Head指针的话，那它就是队列。

优缺点

双端队列其实和队列差不多的，只是更加灵活了，队头和队尾均可进行入队和出队操作，但实际上在应用程序中远不及栈和队列有用。本文就起个抛砖引玉的作用，帮助大家了解一下双端队列，具体应用见。