• 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 [0]

• 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.

Applications:

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 ( ) )

return 0,

int data = queue [front];

front = front + 1 ;

return data ;

3