A dequeue (Double ended queue) is a list in which the elements can be inserted or deleted at either end.
It is also known as a head tail linked list, because elements can be added to or removed from either in front (head) or the back (tail) end.
However, no element can be added and deleted from the middle.
In the computers memory, a dequeue is implemented either using a circular array or a circular doubly linked list.
In a dequeue two pointers are maintained, LEFT and RIGHT , which point to either end of the dequeue.
The elements in a dequeue stretch from the LEFT end to the RIGHT and since it is circular, dequeue [n-1] is followed by dequeue 
Consider the dequeue show in fig.
- Basically, these are two variants of a double ended queue. they includes:
1] Input restricted dequeue:
- In this dequeue, insertions can be done only at one of the dequeue, while deletions can be done from both ends.
2] Output restricted dequeue :
- In this dequeue, deletions can be done only at one of the dequeue, while insertions can be done on both ends.
1] Since dequeue supports both stack and queue operations, it can be used as both.
2] The dequeue data structure supports clock wise and anti clockwise rotations in 0(1) time which can be useful in certain applications.
3] The problems where elements need to be removed and or added both ends can be efficiently solved using dequeue.
eg, int dequeue( )
if (is empty ( ) )
int data = queue [front];
front = front + 1 ;
return data ;