Double Ended Queue (Deque) is a linear data structure that allows insertion and deletion at both sides. So, it is a combination of both Stack and Queue data structures.
1. Representation
- Front: Front side of the queue
- Rear: Rear side of the queue
- Element: The actual data
2. Types of Deque
- Input Restricted Queue – Insertion is restricted to one end while deletion is allowed at both ends.
- Output Restricted Queue – Deletion is restricted to one end while insertion is allowed at both ends.
3. Implementations of Deque
Double Ended Queues can be implemented using Circular Arrays and Doubly Linked Lists. However, choose the correct implementation based on your requirements.
- See Deque Implementation using Circular Array to work with static or limited data.
- See Deque Implementation using Doubly Linked List for dynamic or large data.
4. Deque Operations and Time Complexity
| Operation | Short Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert Front | Insert a new element at the Front side | O (1) | O (n) |
| Insert Rear | Insert a new element at the Rear side | O (1) | O (n) |
| Delete Front | Delete an element from the Front | O (1) | O (n) |
| Delete Rear | Delete an element from the Rear | O (1) | O (n) |
| Search | Search the element by value | O (n) | O (n) |
5. Advantages and Disadvantages
Advantages
- Deque has the ability to perform both LIFO (Last-In First-Out) and FIFO (First-In First-Out) operations with the same data. So this can be used as a combination of both Stacks and Queues.
- Also, it is efficient to work with both ends in O(1) time complexity.
Disadvantages
- Not suitable for sorting and searching operations.
6. Applications
When to Use Double Ended Queues
Deque is required for the data that requires access/modifications from both ends. Also, it is useful in multithreading to access the data concurrently between threads.
Realtime Applications
- Steal job scheduling algorithm in a multiprocessor system. Each processor has its own Deque and processes the jobs from the Front side. If a processor finishes all of its jobs, then it can steal from the back of another processor’s Deque.
- Web browser’s history is another example of Deque. The new pages are inserted at the Front while the old ones are removed from the Rear. Also, it has the ability to retrieve the last visited pages by retrieving them from the Front.