A deque (double-ended queue, pronounced "deck") is a linear data structure that allows insertion and deletion at both ends—front and rear. It combines the properties of both stacks and queues, providing more flexibility than either structure alone.
Deques provide O(1) time complexity for insertion and deletion at both ends, making them versatile for scenarios requiring efficient operations at multiple access points, such as sliding window problems and palindrome checking.
Add Front: Enter a value and click "Add Front" to insert at the front of the deque.
Add Rear: Enter a value and click "Add Rear" to insert at the rear of the deque.
Remove Front: Click "Remove Front" to remove and see the front element.
Remove Rear: Click "Remove Rear" to remove and see the rear element.
Clear All: Click "Clear" to remove all elements and reset the deque.
Visualization: Watch elements added/removed from both ends to understand double-ended behavior.
Add Front: Insert an element at the front of the deque
Add Rear: Insert an element at the rear of the deque
Remove Front: Remove and return the front element
Remove Rear: Remove and return the rear element
Clear All: Remove all elements from the deque
Add Front: O(1) - Direct insertion at front index (circular array) or head pointer.
Add Rear: O(1) - Direct insertion at rear index or tail pointer.
Remove Front: O(1) - Direct removal and index/pointer update.
Remove Rear: O(1) - Direct removal and index/pointer update.
Peek Front/Rear: O(1) - Direct access to both ends.
Search: O(n) - Linear traversal required; not a standard deque operation.
Space Complexity: O(n) - Circular array implementation avoids wasted space.
vs Stack: Deque allows operations at both ends; stack restricts to one end only (LIFO). Deque can simulate a stack.
vs Queue: Deque allows add/remove at both ends; queue restricts to add-rear/remove-front only (FIFO). Deque can simulate a queue.
vs Doubly Linked List: Deque restricts to end operations; DLL allows insertion/deletion anywhere. DLL often implements deque internally.
vs Array: Deque has O(1) operations at both ends (with circular array); array has O(n) for front operations due to shifting.
Best Use Case: Sliding window problems, palindrome checking, work-stealing algorithms, and when both stack and queue behavior is needed.
Sliding Window Maximum: Deques efficiently solve sliding window problems by maintaining candidates at both ends in O(n) time.
Palindrome Checking: Compare characters from both ends simultaneously using deque's front and back access.
Work-Stealing Schedulers: Thread pools use deques where threads pop from their own end and steal from others' opposite end.
A-Steal Algorithm: Parallel computing uses deques for task distribution, balancing load across multiple processors.
Browser History: Forward and backward navigation can be implemented with a deque tracking visited pages from both directions.
Undo/Redo with Limits: Applications limit undo history by removing oldest actions from front while adding new ones at back.
Train Car Shunting: Railroad systems use deque-like operations to rearrange train cars from either end of a track.
Multi-Queue Systems: Customer service systems where high-priority customers are added to front, others to back.
Sliding Window Maximum: Maintain decreasing deque of indices; front always has max for current window in O(n) total.
Sliding Window Minimum: Same pattern with increasing deque; useful for problems like shortest subarray with sum ≥ k.
0-1 BFS: Use deque for graphs with 0/1 edge weights; add to front for 0-weight edges, back for 1-weight.
Maximum of All Subarrays: Process array once with deque, outputting front element for each window position.
First Negative in Window: Track negative numbers in deque; remove from front when outside window.
Implement Stack & Queue: Deque can simulate both; restrict operations to one end for stack, opposite ends for queue.
Palindrome Checker: Compare and remove from both ends simultaneously; empty or single element means palindrome.
/* Deque using array in C (circular buffer concept) */
#include <stdio.h>
#define CAP 100
int front = 0, rear = 0, size = 0;
int dq[CAP];
void add_front(int v) { if (size < CAP) { front = (front - 1 + CAP) % CAP; dq[front] = v; size++; } }
void add_rear(int v) { if (size < CAP) { dq[rear] = v; rear = (rear + 1) % CAP; size++; } }
int remove_front() { if (size > 0) { int v = dq[front]; front = (front + 1) % CAP; size--; return v; } return -1; }
int remove_rear() { if (size > 0) { rear = (rear - 1 + CAP) % CAP; int v = dq[rear]; size--; return v; } return -1; }
int main(){
add_front(1); add_rear(2); add_front(3);
printf("Removed from front: %d
", remove_front());
printf("Removed from rear: %d
", remove_rear());
return 0;
}