Deque (Double-Ended Queue): Insert and Remove from Both Ends

Deque (Double-Ended Queue)

A deque (pronounced "deck") is a generalization of both stacks and queues. It allows insertion and removal at both the front and the rear.

Operations

Operation	Description	Complexity
pushFront(x)	Insert at front	O(1)
pushBack(x)	Insert at rear	O(1)
popFront()	Remove from front	O(1)
popBack()	Remove from rear	O(1)
peekFront()	View front element	O(1)
peekBack()	View rear element	O(1)

Deque as Stack and Queue

A deque can simulate both:

• Stack: Use pushBack and popBack (or pushFront and popFront).
• Queue: Use pushBack and popFront.

This makes deques the most flexible linear data structure.

Implementation

Circular array (most common): Similar to a circular queue but with bidirectional operations. Python's collections.deque, Java's ArrayDeque, and C++'s std::deque use this approach.

Doubly linked list: Each node has prev and next pointers. All four operations are O(1) by manipulating head and tail pointers.

Sliding Window Maximum (Classic Problem)

The most famous deque algorithm solves "maximum in every window of size k" in O(n):

Array: [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Deque stores indices of potentially useful elements:
Window [1, 3, -1]:  deque = [3] (index 1), max = 3
Window [3, -1, -3]: deque = [3] (index 1), max = 3
Window [-1, -3, 5]: deque = [5] (index 4), max = 5
Window [-3, 5, 3]:  deque = [5] (index 4), max = 5
Window [5, 3, 6]:   deque = [6] (index 6), max = 6
Window [3, 6, 7]:   deque = [7] (index 7), max = 7

The deque maintains elements in decreasing order. Elements smaller than the new element are popped from the rear. Elements outside the window are popped from the front.

Palindrome Checking

Deques provide an elegant palindrome checker:

1. Push all characters into a deque.
2. Repeatedly compare and pop from both front and rear.
3. If all pairs match, the string is a palindrome.

Language Implementations

Language	Implementation
Python	collections.deque
Java	ArrayDeque, LinkedList
C++	std::deque
JavaScript	No built-in (use array or custom)
Go	No built-in (use container/list or custom)