DOUBLE ENDED QUEUE

A deque is a linear list in which elements can be added or removed at either end but not in the middle. The items can be added or deleted from the front or rear end, but no changes can be made elsewhere in the list.

There are two varieties of a deque an Input restricted deque and an Output restricted deque which are intermediate between deque and a regular queue.

Specifically, An input restricted deque is a deque which allows insertions at only one end of the list, but allows deletions at both ends of the list.

An output restricted deque is a deque which allows deletions at only one end of the list but allows insertions at both ends of the list.

The two possibilities that must be considered while inserting or deleting elements into the queue are:

• When an attempt is made to insert an element into a deque which is already full, an overflow occurs.

• When an attempt is made to delete an element from a deque which is empty, underflow occurs.