A Double Ended Queue (Deque) is a type of linear data structure that allows elements to be added or removed from both ends, i.e., from the front and rear (or head and tail) of the queue. It is a generalized version of a queue and can be considered as a combination of both a queue and a stack.
In a standard queue, elements can only be added at the rear and removed from the front, following the FIFO (First In, First Out) principle. However, in a double-ended queue, elements can be added or removed from both ends, making it more flexible and useful in certain situations.
Types of Operations on Deque:
Insert at the front (push_front):
Insert an element at the front (left end) of the deque.
Insert at the rear (push_back):
Insert an element at the rear (right end) of the deque.
Remove from the front (pop_front):
Remove an element from the front of the deque.
Remove from the rear (pop_back):
Remove an element from the rear of the deque.
Peek at the front:
View the element at the front of the deque without removing it.
Peek at the rear:
View the element at the rear of the deque without removing it.
Check if empty:
Check whether the deque is empty or not.
Characteristics of a Deque:
Bidirectional: Allows insertion and deletion from both ends.
Dynamic size: The size of the deque can grow and shrink dynamically as elements are added or removed.
FIFO (Front) and LIFO (Rear) properties: The deque can act like a queue when inserting/removing from the rear and can act like a stack when inserting/removing from the front.
Applications of Deque:
Palindrome checking: A deque can be used to check if a given string is a palindrome.
Sliding window problems: In problems like finding the maximum or minimum in a sliding window, a deque is often used to maintain the elements within the window.
Task scheduling: Deques can be used in algorithms where tasks are scheduled from both ends of the queue.
Example of Deque Operations:
Imagine a deque with elements [10, 20, 30] (front to rear).
Push front 5: New deque: [5, 10, 20, 30]
Push back 40: New deque: [5, 10, 20, 30, 40]
Pop front: New deque: [10, 20, 30, 40]
Pop back: New deque: [10, 20, 30]
Time Complexity:
Insertions and deletions (at both ends) are typically O(1).
Accessing elements is O(1) for both ends.
Conclusion:
A Double Ended Queue (Deque) is a versatile data structure that supports operations on both ends, making it useful for scenarios that require flexibility in insertion and deletion. It combines features of both queues and stacks, and its efficient operations make it ideal for use in many algorithmic problems.
