Ugenz Academy/Tutorial

Deque

12 min read2,251 words

Reading progress

Keep learning

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:

FunctionPurpose
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:

OperationComplexity
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

OperationDeque
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:

  1. Implement deque
  2. Palindrome using deque
  3. Sliding Window Maximum
  4. Sliding Window Minimum
  5. Maximum/minimum in every window
  6. Monotonic deque
  7. 0-1 BFS
  8. Shortest path with 0/1 edge weights
  9. 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy