Question

Explain in brief Double ended Queue

Answer 1

It is also known as a head-tail linked list because elements can be added to or
removed from either the front (head) or the back (tail) end.
- However, no element can be addedand deleted from the middle
- In a deue, two pointers are maintained, LEFT and RIGHT, which point to
either endof the deque.
- They include,
Input restricted deque – In this dequeue, insertions can be done only at
one of the ends, while deletions can be done from both ends.
The following operations are possible in an input restricted dequeues.
i) Insertion of an element at the rear end and
ii)Deletion of an element from front end
iii)Deletion of an element from rear end

Output restricted deque- In this dequeue, deletions can be done only at one
of the ends,while insertions can be done on both ends.
i) Deletion of an element at the front end
ii)Insertion of an element from rear end
iii)Insertion of an element from rear end
Operations on a dequeue
i. initialize(): Make the queue empty.
ii. empty(): Determine if queue is empty.
iii. full(): Determine if queue is full.
iv. enqueueF(): Insert at element at the front end of the queue.
v. enqueueR(): Insert at element at the rear end of the queue.
vi. dequeueF(): Delete the front end
vii. dequeueR(): Delete the rear end
viii. print(): print elements of the queue.

There are various methods to implement a dequeue.
- Using a circular array
- Using a linked list
- Using a cicular linked list
- Using a doubly linked list
- Using a doubly cirular linked list