Deque¶

You might have noticed there were many similarities between the stack and the queue. In fact, there are so many sometime we combine the data structures.

A deque is a data structure that has the features of both a queue and a stack. It’s name is pronounced “deck”. It is short for Double-Ended Queue. It is common to include a deque in a library. Instead of coding and testing two data structures, you can make one and let the programmer use it in either way.

The deque can do the following.

Initialize empty deque
Check if empty
Look at first element
Look at last element
Add to front
Add to back
Remove from front
Remove from back

To implement a deque we need a node with two pointers. We need to be able to move forward and backward. This way we can act like it is stack or a queue at any point.

This code it more complex than either of the other data structures, but that extra work in development will get us both data structures and additional features neither has.

We start with a node that as two pointers. We need a next and a previous.

//The Node Data Structure
struct Node struct {
    int value;   //The Value Stored at this node
    Node* next; //Pointer to the next value
    Node* previous; //Pointer to previous value
};

The deque needs a head and a tail, just like a queue.

//A Deque data structure
struct Deque {
    Node* head; //The front
    Node* tail; //The back
};

To create a new deque, both pointers point to the null memory address.

Function newDeque() 
    //Allocate Memory
    Let D be a pointer to a new Deque
    //Set points to Null
    D's head = Null
    D's tail = Null
    //Return pointer to queue
    Return D
End Function

To determine if the deque is empty, we just need to see if the head is nil.

Function isEmpty(Deque* D)
    Return D's head is Null
End Function

We need to be able to look at the front element. This is just whatever head points to. To keep the code simple, we avoid error checking and return a -1 on an empty deque.

Function front(Deque* D)
    If D's head is Null then
        Return -1
    End If
    Return D's head's value
End Function

We also need to look at the back. It is a mirror of the front.

Function back(Deque* D)
    If D's tail is Null then
        Return -1
    End If
    Return D's tail's value
End Function

To add a new element to the front, we create a new node. If the deque is empty, we can make it the only element. Otherwise, we need to update pointers. Notice that we update next and previous. We always need to be ready for the list to be used backwards.

Function pushFront(Deque* D, int v)
    Let newNode be a pointer to a new Node
    newNode's value = v
    newNode's next = Null
    newNode's previous = Null
    //If the head is null, only node
    If D's head is Null then
        D's head = newNode
        D's tail = newNode
        return
    End If
    //Add to front
    newNode's next = D's head
    D's head's previous = newNode
    D's head = newNode
End Function

Adding to the back looks very similar. We basically swapped head and tail and next and previous.

Function pushBack(Deque* D, int v)
    Let newNode be a pointer to a new Node
    newNode's value = v
    newNode's next = Null
    newNode's previous = Null
    //If tail is empty, only node
    If D's tail is Null then
        D's head = newNode
        D's tail = newNode
        return
    End If
    //Add to back
    D's tail's next = newNode
    newNode's previous = D's tail
    D's tail = newNode
End Function

We can also remove elements. Again, both operations are very close in design. We need to check for an empty list. We need to deal with removing the last item in the list. Finally, we need to update pointers. Again, we need to remember to update both next and previous.

Function popFront(Deque* D)
    //Check Empty
    If isEmpty(D) then
        Return
    End If
    temp = D's head
    D's head = temp's next
    delete memory used by temp
    If D's head is null then
        D's tail = null \\The list is empty
    Else
        D's head's previous = null
    EndIf
End Function

Removing from the back looks very similar.

Function popBack(Deque* D)
    //Check Empty
    If isEmpty(D) then
        Return
    End If
    temp = D's tail
    D's tail = temp's previous
    delete memory used by temp
    If D's tail is null then
        D's head = null \\The list is empty
    Else
        D's tail's next = null
    EndIf
End Function

These are all constant time operations. We have one data structure that can act like both a stack and a queue. It can even switch between the two at any time. This gives the program significantly more flexibility when they are designing algorithms.

Operation	Runtime
`newDeque()`	\(O(1)\)
`isEmpty(D)`	\(O(1)\)
`front(D)`	\(O(1)\)
`back(D)`	\(O(1)\)
`pushFront(D, v)`	\(O(1)\)
`pushBack(D, v)`	\(O(1)\)
`popFront(D)`	\(O(1)\)
`popBack(D)`	\(O(1)\)

Algorithmic Foundations of Computer Science

Deque

Deque¶