Double-Ended Queues
Explore double-ended queues or deques to understand their dual-end insertion and deletion operations. Learn to implement deques in Java using ArrayDeque, perform efficient O(1) operations, and see how deques solve problems like sliding windows and BFS optimizations.
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 ...
