Question: Double ended queue.
0
  • 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.

enter image description here

  • 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

renu • 20 views
ADD COMMENTlink
modified 4 weeks ago  • written 4 weeks ago by gravatar for RB RB100
Please log in to add an answer.