Deque is a type of queue in which insert and deletion can be performed from either front or rear. It does not follow the FIFO rule. It is also known as double-ended queue
Operations on Deque:
Deque consists of mainly the following operations:
- Insert Front
- Insert Rear
- Delete Front
- Delete Rear
1. Insert at the Front: This operation is used to add an element at the front. If the number of elements is not exceeding the size of the deque then only insertion takes place.
2. Insert at the Rear: If the deque is not full then this function inserts the element at the back end of the queue.
3. Delete from the Front: This operation is used to delete an element from the deque. If the deque is not empty then this operation will delete an element from the front end of the deque.
4. Delete from the Rear: This operation is used to delete an element from the back end of the deque if the deque is not empty.
For more details regarding the operation and their implementation using circular array or doubly linked list, follow the articles about “Implementation of Deque using circular array” and “Implementation of Deque using doubly linked list“.
Properties of Deque:
- Deque is a generalized version of the queue which allows us to insert and delete the element at both ends.
- It does not follow FIFO (first in first out) rule.
Applications of Deque:
- It is used in job scheduling algorithms.
- If support both stack and queue operations.
- The clockwise and anti-clockwise rotation operations in deque are performed in O(1) time which is helpful in many problems.
Real-time Application of Deque:
- In a web browser’s history, recently visited URLs are added to the front of the deque and the URL at the back of the deque is removed after some specified number of operations of insertions at the front.
- Storing a software application’s list of undo operations.
Advantages of Deque:
- You are able to add and remove items from the both front and back of the queue.
- Deques are faster in adding and removing the elements to the end or beginning.
- The clockwise and anti-clockwise rotation operations are faster in a deque.
Disadvantages of Deque:
- Deque has no fixed limitations for the number of elements they may contain. This interface supports capacity-restricted deques as well as the deques with no fixed size limit.
- They are less memory efficient than a normal queue.