Double-Ended Queue - Have I over-engineered it again?
I would make it so that you only have one sentanal.

Then the list is empty when head and tail point at the same object.

DeQueue::DeQueue()
    // set up the sentinels
    : head(new QueueItem())   // prefer to use initialize list.
    , tail(head)              // Make sure your declarations are in the correct order.
{

    head-&gt;next = head;        // Circular linked list.
    head-&gt;last = head;

    head-&gt;data = NULL;        // No data in the fake node.
}


Your delete loop does not actually move:

while(current-&gt;next != head)
{
    delete current-&gt;next;  // your deleting the element
                           // But not moving the the current item
                           // So the loop will not exit.
}


DeQueue::~DeQueue()
{
    // Delete from the head.
    // Just slowly loop over the nodes deleting them as you go
    while(head != tail)
    {
         QueueItem* old = head;
         head           = head-&gt;next;

         delete old;
    }
    // Delete the sentanal object created in the constructor.
    delete tail;
}

// Simplify empty.
bool DeQueue::Empty()
{
    return tail == head;
}