DSA Basics: Deque

A deque is a double-ended queue.

Unlike a normal queue, a deque can add and remove values from both ends.

Core operations

• addFront(value)
• addBack(value)
• removeFront()
• removeBack()
• peekFront()
• peekBack()

Why deques are useful

A deque is flexible because it can behave like both a stack and a queue.

If you only use the back, it acts like a stack. If you add at the back and remove from the front, it acts like a queue.

Common use cases

• Sliding window maximum
• Palindrome checking
• Browser-like navigation
• Undo and redo buffers
• Work stealing queues

Sliding window intuition

Deque problems often ask you to keep a useful window of values while moving through an array.

For example, in a sliding window maximum problem, the deque stores indexes that could still become the maximum.

Complexity

When backed by a proper deque implementation:

• Add front: O(1)
• Add back: O(1)
• Remove front: O(1)
• Remove back: O(1)

Practice links

• LeetCode Queue problems
• NeetCode practice roadmap

Use the visualizer below to operate on both ends.