Double-Ended Queues
Explore how double-ended queues (deques) work, enabling insertion and deletion at both the front and rear. Understand their implementation in Python using collections.deque, their O(1) time operations, different types of deques, and why they are valuable in solving problems like sliding window maximum and BFS optimization.
A deque stands for a double-ended queue. It is a more flexible version of a queue that allows insertion and deletion from both the front and the rear.
In a normal queue, insertion happens only at the rear and deletion happens only at the front. In a deque, both ends are fully active.
This makes the deque a generalization that can behave like a queue, a stack, or something in between, depending on how it is used.
A deque is useful when a problem needs controlled access to both ends of the structure. It appears in sliding window problems, palindrome checking, scheduling, and caching systems.
Example
To understand how a deque works, consider the following example. If a deque currently contains:
After inserting 88 at the front, the deque becomes:
After inserting 91 at the rear, the deque becomes:
After removing 88 from the front, the deque becomes:
After removing 91 from the rear, the deque becomes:
This two-sided behavior is what makes the deque more versatile than a regular queue. ...