Deque

Deque is a short form of double-ended queue. Deque defines a data structure where elements can be added or deleted at either the front end or the rear end, but no changes can be made elsewhere in the list.

Deque is a generalization of both a stack and a queue. It supports both stack-like and queue-like capabilities.

Deque can be implemented as either a continuous deque or as a linked deque.

 

The following are the four operations associated with deque:

1. EnqueueFront()—adds elements at the front end of the queue

2. EnqueueRear()—adds elements at the rear end of the queue

3. DequeueFront()—deletes elements from the front end of the queue

4. DequeueRear()—deletes elements from the rear end of the queue

 

Deque is useful where the data to be stored has to be ordered, compact storage is needed, and the retrieval of data elements has to be faster.

 

There are two variations of a deque

1. Input restricted deque - insertions allowed only at one end.

2. Output restricted deque – deletions are allowed only at one end.

 

The functions to operate an output-restricted deque could be as follows:

DequeueFront() , EnqueueFront(), and EnqueueRear()

The functions to operate an input-restricted deque are as follows:

DequeueFront(), DequeueRight(), and EnqueueFront()