C++ STL

deque

Complete lesson for deque using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — deque

Section: C++ STL. C++ std::deque — double-ended queue: fast growth at both ends, random access, and Vector vs Deque.

What is a deque?

std::deque means **double-ended queue** — a sequence you can efficiently grow/shrink from **both ends**.
Supports **random access** like vector (d[i], at(i)).
Internally uses a map of fixed-size blocks (not one single contiguous buffer like vector).
Header: #include
Default underlying container for stack and queue adapters.
**Real-life:** a line where people can join at the front *or* the back (VIP / normal queues).

Idea	Meaning
Double-ended	Fast `push_front` / `push_back`
Random access	`d[i]` is O(1)
Blocks	Chunked storage — not fully contiguous
Adapters	Often backs `stack` / `queue`

Why use deque?

Need frequent insert/remove at **both** ends — vector is slow at the front.
Still want index access (d[i]) unlike list.
Good default for sliding windows, BFS queues, undo buffers at both ends.
Prefer vector if you mostly grow at the **back** only (better cache locality).

Benefit	What you gain
Front ops	O(1) `push_front` / `pop_front`
Back ops	O(1) `push_back` / `pop_back`
Indexing	O(1) random access
Flexibility	Both-end workloads without list overhead

Differences between Vector and Deque

Both are sequence containers with random access — pick by **where** you insert most.

Feature	Vector (`std::vector`)	Deque (`std::deque`)
Memory layout	One contiguous buffer	Multiple chunks / blocks
`push_back` / `pop_back`	Amortized O(1)	O(1)
`push_front` / `pop_front`	O(n) (must shift)	O(1)
Random access `[]`	O(1), very cache-friendly	O(1), slightly less local
`data()` pointer	Yes — contiguous	No portable single `data()` block
Iterator invalidation on growth	All iterators if reallocates	Usually milder at ends; mid insert still shifts
`capacity()` / `reserve()`	Yes	No `capacity`/`reserve` API
Typical default choice	Yes — most sequences	When both ends matter
Used as adapter base	stack (optional)	Default for `stack` & `queue`
Mid insert/erase	O(n)	O(n)
Header
When to prefer	Grow at back; need contiguous	Grow at front and back

Creating and initializing a deque

Same construction styles as vector — empty, sized, filled, braced list.

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
    deque<int> a;                 // empty
    deque<int> b(4, 7);           // 7 7 7 7
    deque<int> c = {1, 2, 3};
    deque<string> d = {"hi", "bye"};
    cout << c.size() << "\n";
    return 0;
}

Accessing elements

d[i] — unchecked random access.
d.at(i) — bounds-checked.
front() / back() — ends of the deque.
Range-for works like other containers.

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d = {10, 20, 30};
    cout << d[0] << " " << d.at(1) << "\n";
    cout << d.front() << " " << d.back() << "\n";
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

Adding and removing at both ends

push_front / push_back — insert at ends.
pop_front / pop_back — remove at ends.
emplace_front / emplace_back — construct in place.
Middle insert / erase still cost O(n).

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d;
    d.push_back(2);
    d.push_front(1);
    d.push_back(3);   // 1 2 3
    d.pop_front();    // 2 3
    d.pop_back();     // 2
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

Insert, erase, and size

insert / erase at an iterator — elements shift within chunks (O(n)).
size(), empty(), clear() like other sequences.
No capacity() / reserve() — growth strategy is implementation-defined chunks.

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d = {1, 3, 4};
    d.insert(d.begin() + 1, 2); // 1 2 3 4
    d.erase(d.begin() + 2);     // 1 2 4
    cout << "size=" << d.size() << "\n";
    return 0;
}

Iterators and algorithms

Random-access iterators — works with sort, find, etc.
begin() / end() form a half-open range.

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
    deque<int> d = {4, 1, 3, 2};
    sort(d.begin(), d.end());
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

Key points to remember

deque = efficient growth at **both** ends + random access.
Prefer vector if you only push at the back.
Not one contiguous block — no portable data() like vector.
Default base for queue and often stack.
Mid insert/erase is still O(n).

Advanced — deque

Complexity cheat sheet

Common operation costs for deque.

Operation	Complexity
`d[i]`, `at`, `front`, `back`	O(1)
`push_front` / `push_back`	O(1)
`pop_front` / `pop_back`	O(1)
`insert` / `erase` in middle	O(n)
Traverse all	O(n)

Memory model (overview)

deque stores elements in fixed-size **blocks**; a map of block pointers tracks them.
Growing at either end usually allocates/links another block — no full reallocation of all elements like vector.
Trade-off: slightly more overhead and less cache locality than vector.

Iterator invalidation notes

Insert/erase in the middle invalidate iterators.
Push/pop at ends typically invalidate less aggressively than vector reallocation — but do not rely on subtle rules; refresh iterators after modifying.
Always re-get begin()/end() after structural changes if unsure.

deque as adapter base

queue and stack default to deque underneath.
You can switch: stack> or queue> when needed.

#include <queue>
#include <stack>
#include <deque>
using namespace std;

queue<int> q;           // uses deque by default
stack<int> st;          // uses deque by default
deque<int> raw;         // use deque directly when you need both ends + indexing

Sliding window pattern

deque often stores indices for sliding-window maximum/minimum problems.
Push/pop from both ends keeps the window ends updated in O(1).

Design tips

Default sequence: **vector**. Use deque when front operations matter.
Need only FIFO? Prefer queue adapter for a clearer API.
Need mid-list splicing? Consider list (usually still measure vs vector/deque).
Do not assume &d[0] addresses a single C array for the whole deque.

Tricky Interview Points

Q1) What is std::deque?

Answer A double-ended queue sequence container with efficient push/pop at both ends and random-access indexing.

Q2) Vector vs deque — when choose deque?

Answer When you need frequent insertions/deletions at the front (and back). Prefer vector for back-only growth and contiguous storage.

Q3) Is deque memory contiguous?

Answer No — it uses multiple blocks. Random access is still O(1), but not as cache-friendly as vector.

Q4) Complexity of push_front on deque vs vector?

Answer Deque: O(1). Vector: O(n) because elements must shift.

Q5) Does deque have capacity() and reserve()?

Answer No. Those APIs are for vector (and string).

Q6) Why is deque the default for queue and stack?

Answer It supports efficient growth at the ends that those adapters need, without shifting like vector would for front ops on queue.

Q7) Can you sort a deque?

Answer Yes — it has random-access iterators, so sort(d.begin(), d.end()) works.

Q8) [] vs at() on deque?

Answer Same idea as vector: [] unchecked, at() throws out_of_range on bad indices.

Q9) Mid insert complexity?

Answer O(n) — elements must be moved within the structure.

Q10) Can you get a single data() pointer like vector?

Answer No portable contiguous data() for the entire deque contents.

Q11) Typical real-life uses?

Answer Task queues with priority inserts at front, sliding windows, undo/redo buffers, BFS with occasional front insert.

Q12) deque vs list?

Answer deque offers O(1) random access; list does not. list has O(1) splice given iterators; deque mid ops are O(n).

Simple Programs

push_front and push_back

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d;
    d.push_back(20);
    d.push_front(10);
    d.push_back(30);
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

pop both ends

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d = {1, 2, 3, 4};
    d.pop_front();
    d.pop_back();
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

random access and at()

#include <iostream>
#include <deque>
#include <stdexcept>
using namespace std;

int main() {
    deque<int> d = {5, 6, 7};
    cout << d[1] << "\n";
    try {
        cout << d.at(10) << "\n";
    } catch (const out_of_range& e) {
        cout << "Exception\n";
    }
    return 0;
}

sort a deque

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
    deque<int> d = {9, 2, 7, 1};
    sort(d.begin(), d.end());
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

sliding window of size 3 (store values)

#include <iostream>
#include <deque>
using namespace std;

int main() {
    int arr[] = {1, 3, 2, 6, 4};
    deque<int> win;
    for (int x : arr) {
        win.push_back(x);
        if (win.size() > 3) win.pop_front();
        if (win.size() == 3) {
            for (int v : win) cout << v << " ";
            cout << "\n";
        }
    }
    return 0;
}

deque as a manual queue

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
    deque<string> q;
    q.push_back("A");
    q.push_back("B");
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop_front();
    }
    cout << "\n";
    return 0;
}

Problem Solving Tricks

deque = double-ended queue + random access.
push_front is O(1) on deque, O(n) on vector.
Prefer vector for back-only growth.
Not fully contiguous — no vector-like data().
Default base for stack and queue.
sort works — random-access iterators.
Mid insert/erase still O(n).
Use queue adapter when you only need FIFO API.
at() checks bounds; [] does not.
Great for sliding-window end updates.
Header: .
Compare Vector vs Deque in interviews with a table.

Practice Programs List

Build a deque with push_front/back; print with range-for.
Pop from both ends until one element remains.
Sort a deque ascending and descending.
Simulate a FIFO line using only deque front ops.
Implement a size-3 sliding window over an array.
Show d.at(badIndex) throwing.
Write a Vector vs Deque table in comments (8 rows).
Insert in the middle and explain the O(n) cost.
Pass const deque& to a sum function.
List three features vector has that deque lacks (e.g. capacity).
Explain why queue defaults to deque.
Compare deque vs list for random access in one paragraph.