Deque — Double-Ended Queue
Deque stands for:
Double-Ended Queue
A deque is a linear data structure where we can insert and delete elements from both ends.
Unlike a normal queue:
Queue: Insert → Rear Delete → Front
A deque allows:
Deque: Insert → Front or Rear Delete → Front or Rear
1. Basic Idea
Imagine a line where people can enter or leave from both sides.
FRONT REAR ↓ ↓ ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘ ↑ ↑ insert/delete insert/delete
Both ends are active.
That's why it is called:
Double-Ended Queue
2. Queue vs Deque
A normal queue:
FRONT REAR ↓ ↓ 10 → 20 → 30 → 40 → 50 ↑ ↑ delete insert
You normally:
insert → rear delete → front
A deque:
FRONT REAR ↓ ↓ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 ↑ ↑ insert/delete insert/delete
Both ends can be used.
3. Four Main Operations
A deque has four fundamental operations:
Insert at front
push_front()
Insert at rear
push_back()
Delete from front
pop_front()
Delete from rear
pop_back()
In C++:
deque<int> dq; dq.push_front(10); dq.push_back(20); dq.pop_front(); dq.pop_back();
4. Insert at Rear
Start with:
FRONT REAR ↓ ↓ ┌────┬────┐ │ 10 │ 20 │ └────┴────┘
Perform:
push_back(30);
Result:
FRONT REAR ↓ ↓ ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘
30 was added to the rear.
5. Insert at Front
Start:
FRONT REAR ↓ ↓ 10 → 20 → 30
Perform:
push_front(5);
Result:
FRONT REAR ↓ ↓ 5 → 10 → 20 → 30
5 was added at the front.
6. Delete from Front
Suppose:
FRONT REAR ↓ ↓ 5 → 10 → 20 → 30
Perform:
dq.pop_front();
Result:
FRONT REAR ↓ ↓ 10 → 20 → 30
The first element was removed.
7. Delete from Rear
Suppose:
FRONT REAR ↓ ↓ 10 → 20 → 30
Perform:
dq.pop_back();
Result:
FRONT REAR ↓ ↓ 10 → 20
The last element was removed.
8. Deque in C++
C++ provides a deque through the STL.
Include:
#include <deque>
Create one:
deque<int> dq;
Now you can use:
dq.push_front(10); dq.push_back(20);
9. Complete Basic Example
#include <iostream> #include <deque> using namespace std; int main() { deque<int> dq; dq.push_back(20); dq.push_back(30); dq.push_front(10); cout << dq.front() << endl; cout << dq.back() << endl; dq.pop_front(); dq.pop_back(); cout << dq.front() << endl; return 0; }
Output:
10 30 20
Let's understand it:
push_back(20) 20
Then:
push_back(30) 20 → 30
Then:
push_front(10) 10 → 20 → 30
Then:
pop_front() 20 → 30
Then:
pop_back() 20
10. Important C++ Deque Functions
For:
deque<int> dq;
remember these:
| Function | Purpose |
|---|---|
push_front(x) | Insert at front |
push_back(x) | Insert at back |
pop_front() | Remove front |
pop_back() | Remove back |
front() | Get first element |
back() | Get last element |
empty() | Check empty |
size() | Number of elements |
clear() | Remove all elements |
11. Accessing Elements
Unlike a linked list, C++'s deque supports indexing.
Example:
deque<int> dq = {10, 20, 30, 40};
You can do:
cout << dq[0];
Output:
10
And:
cout << dq[2];
Output:
30
So:
dq[0] → 10 dq[1] → 20 dq[2] → 30 dq[3] → 40
12. Deque vs Array
A deque is not simply the same thing as a normal array.
A standard array has fixed storage:
[10][20][30][40]
A C++ deque is a specialized dynamic container designed to efficiently insert/remove at both ends.
It provides:
front insertion → efficient back insertion → efficient front deletion → efficient back deletion → efficient random access → supported
13. Complexity
For the standard C++ deque, the main operations are generally:
| Operation | Complexity |
|---|---|
push_front() | O(1) amortized |
push_back() | O(1) amortized |
pop_front() | O(1) |
pop_back() | O(1) |
front() | O(1) |
back() | O(1) |
Access using [] | O(1) |
size() | O(1) |
This combination is what makes deque useful.
14. Deque vs Queue
This is very important.
Queue
QUEUE FRONT REAR ↓ ↓ 10 → 20 → 30 → 40 → 50 ↑ ↑ delete insert
Operations are restricted:
Insert → Rear Delete → Front
Deque
DEQUE FRONT REAR ↓ ↓ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 ↑ ↑ insert/delete insert/delete
Operations:
Insert → Front / Rear Delete → Front / Rear
15. Deque vs Stack
A stack uses one active end:
STACK TOP ↓ ┌────┐ │ 30 │ ├────┤ │ 20 │ ├────┤ │ 10 │ └────┘
Operations:
push → top pop → top
A deque uses both ends:
DEQUE FRONT REAR ↓ ↓ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 ↑ ↑ operations operations
Interestingly, a deque can be used to implement a stack.
For example:
dq.push_back(10); dq.push_back(20); dq.pop_back();
This behaves like a stack.
16. Deque Can Also Behave Like a Queue
A deque can also behave like a normal queue.
Use:
push_back() pop_front()
Example:
dq.push_back(10); dq.push_back(20); dq.push_back(30); dq.pop_front();
This gives:
10 → 20 → 30 pop front 20 → 30
That's FIFO behavior.
So:
A deque is more flexible than both a normal queue and a stack.
17. Important Example: Palindrome
A deque is useful for checking whether a string is a palindrome.
Example:
"madam"
Put characters into a deque:
FRONT REAR ↓ ↓ m → a → d → a → m
Compare:
front = m back = m
They match.
Remove both:
a → d → a
Again:
front = a back = a
Remove both:
d
Palindrome confirmed.
18. C++ Palindrome Example
#include <iostream> #include <deque> using namespace std; int main() { string s = "madam"; deque<char> dq; for(char ch : s) { dq.push_back(ch); } bool palindrome = true; while(dq.size() > 1) { if(dq.front() != dq.back()) { palindrome = false; break; } dq.pop_front(); dq.pop_back(); } if(palindrome) cout << "Palindrome"; else cout << "Not Palindrome"; return 0; }
Output:
Palindrome
The interesting part is that we can access both ends efficiently.
19. Sliding Window Problems
Deque becomes very important in advanced DSA for:
Sliding Window Maximum
Suppose:
Array: 2 1 5 3 4 6 2
and window size:
k = 3
Windows are:
[2 1 5] [1 5 3] [5 3 4] [3 4 6] [4 6 2]
We need the maximum of each window:
5 5 5 6 6
A deque can solve this efficiently using a technique called a monotonic deque.
This becomes an important problem-solving pattern later.
20. Why Deque Is Useful for Sliding Windows
Suppose the deque stores useful candidate elements:
FRONT REAR ↓ ↓ largest ← ... ← smaller
When a new element arrives:
- Remove elements that are no longer useful.
- Remove elements outside the current window.
- Add the new element.
This allows the maximum to be available at the front.
The optimized solution can achieve:
Time = O(n)
instead of checking every window from scratch.
21. Deque and BFS
A normal BFS uses:
queue
But some advanced graph algorithms can use a deque.
A famous example is:
0-1 BFS
This is used for graphs where edge weights are only:
0 or 1
The idea is:
weight 0 → push_front() weight 1 → push_back()
So deque provides exactly the two-ended behavior needed.
This is an advanced application you'll encounter later.
22. Deque and Monotonic Data Structures
A monotonic deque keeps elements in a particular order.
For example, decreasing:
10 → 8 → 5 → 3
When a new value arrives, smaller/unnecessary elements can be removed from the rear.
This is useful in:
- Sliding window maximum
- Sliding window minimum
- Optimization problems
- Some dynamic programming problems
- Advanced array problems
Don't worry about implementing this yet. Just remember:
Deque is an important tool for sliding-window problems.
23. Empty Deque
Before calling:
dq.front();
or:
dq.back();
you should make sure the deque isn't empty.
Example:
if(!dq.empty()) { cout << dq.front(); }
Similarly:
if(!dq.empty()) { cout << dq.back(); }
Calling front/back on an empty deque is invalid.
24. clear()
You can remove all elements:
dq.clear();
Example:
deque<int> dq = {10, 20, 30}; dq.clear();
Now:
dq.empty() → true
and:
dq.size() → 0
25. Iterating Through a Deque
You can use a range-based loop:
deque<int> dq = {10, 20, 30, 40}; for(int x : dq) { cout << x << " "; }
Output:
10 20 30 40
You can also use indexing:
for(int i = 0; i < dq.size(); i++) { cout << dq[i] << " "; }
26. A Complete Deque Example
#include <iostream> #include <deque> using namespace std; int main() { deque<int> dq; // Insert at rear dq.push_back(20); dq.push_back(30); // Insert at front dq.push_front(10); dq.push_front(5); cout << "Deque: "; for(int x : dq) { cout << x << " "; } cout << "\nFront: " << dq.front(); cout << "\nBack: " << dq.back(); // Remove front dq.pop_front(); // Remove back dq.pop_back(); cout << "\nAfter removals: "; for(int x : dq) { cout << x << " "; } return 0; }
Output:
Deque: 5 10 20 30 Front: 5 Back: 30 After removals: 10 20
27. How Deque Is Implemented Internally
A deque needs to efficiently support both ends.
A simple contiguous array is not ideal because inserting at the front could require shifting everything.
For example:
Before: [10][20][30][40]
Insert 5 at front:
[5][10][20][30][40]
A naive array would have to move many elements.
Instead, a deque implementation uses a more sophisticated storage structure, commonly involving multiple blocks of memory.
Conceptually:
Block 1 Block 2 Block 3 [10][20] → [30][40] → [50][60]
This allows efficient growth at both ends.
You normally don't need to implement the internal STL mechanism yourself at this stage.
28. Types of Operations
Let's organize everything:
Front operations
push_front() pop_front() front()
Rear operations
push_back() pop_back() back()
General operations
size() empty() clear()
Think:
DEQUE | ┌──────────┴──────────┐ ↓ ↓ FRONT REAR ↓ ↓ push_front() push_back() pop_front() pop_back() front() back()
29. Queue, Stack and Deque Together
This is an important comparison:
STACK Only one end ↓ 10 → 20 → 30 ↑ TOP
QUEUE Two ends, different jobs FRONT REAR ↓ ↓ 10 → 20 → 30 → 40 ↑ ↑ remove insert
DEQUE Two ends, both active FRONT REAR ↓ ↓ 10 ⇄ 20 ⇄ 30 ⇄ 40 ↑ ↑ insert/delete insert/delete
So:
Stack → one active end Queue → insert rear, delete front Deque → both ends active
30. Important Complexity Table
| Operation | Deque |
|---|---|
push_front() | O(1) amortized |
push_back() | O(1) amortized |
pop_front() | O(1) |
pop_back() | O(1) |
front() | O(1) |
back() | O(1) |
dq[i] | O(1) |
size() | O(1) |
empty() | O(1) |
31. Common Deque Problems
As you progress, you'll encounter problems such as:
- Implement deque
- Palindrome using deque
- Sliding Window Maximum
- Sliding Window Minimum
- Maximum/minimum in every window
- Monotonic deque
- 0-1 BFS
- Shortest path with 0/1 edge weights
- Optimized sliding-window problems
The sliding window + deque combination is especially important.
32. The Most Important Mental Model
Imagine a train where you can add or remove coaches from either end:
FRONT REAR ↓ ↓ [10] ⇄ [20] ⇄ [30] ⇄ [40] ⇄ [50] ↑ ↑ └──── both ends usable ──────┘
That's a deque.
Remember:
Deque = Double-Ended Queue = insertion and deletion from both ends.
Final Summary
Deque
Double-Ended Queue
Main operations
push_front() // insert at front push_back() // insert at rear pop_front() // remove from front pop_back() // remove from rear front() // first element back() // last element empty() // check empty size() // number of elements
Core idea
DEQUE FRONT REAR ↓ ↓ ┌─────────────────────┐ │ 10 │ 20 │ 30 │ 40 │ └─────────────────────┘ ↑ ↑ insert/ insert/ delete delete
Remember the three:
STACK → LIFO QUEUE → FIFO DEQUE → BOTH ENDS
Important applications
- Palindrome checking
- Sliding Window Maximum/Minimum
- Monotonic deque
- 0-1 BFS
- Advanced graph and optimization problems