C++ deque

📦 C++ deque (Double-Ended Queue)

std::deque is a sequence container in the C++ STL that allows fast insertion and deletion at both ends (front and back).
It combines some advantages of vector and queue.

🔹 1. Why Use deque?

  • Insert/delete at both ends in O(1)

  • Random access like vector

  • Used as underlying container for stack and queue

  • No costly shifting like vector (at front)

🔹 2. Include Header

#include <deque>

🔹 3. Declaring a Deque

std::deque<int> dq;

With initialization:

std::deque<int> dq = {1, 2, 3};

🔹 4. Adding Elements

dq.push_back(10); // add at end
dq.push_front(5); // add at front

🔹 5. Accessing Elements

cout << dq[0]; // random access
cout << dq.at(1); // bounds-checked
cout << dq.front(); // first element
cout << dq.back(); // last element

🔹 6. Removing Elements

dq.pop_back(); // remove last
dq.pop_front(); // remove first

🔹 7. Traversing a Deque

Range-based Loop

for (int x : dq) {
cout << x << " ";
}

Iterator

for (auto it = dq.begin(); it != dq.end(); ++it) {
cout << *it << " ";
}

🔹 8. Insert & Erase (Middle)

dq.insert(dq.begin() + 1, 99);
dq.erase(dq.begin() + 1);

🔹 9. Size & Capacity

dq.size();
dq.empty();

✔ deque does not expose capacity() like vector.

🔹 10. Deque Example

deque<int> dq;

dq.push_back(1);
dq.push_front(2);
dq.push_back(3);

for (int x : dq)
cout << x << " ";

Output:

2 1 3

🔹 11. Deque vs Vector

Featuredequevector
MemoryNon-contiguous blocksContiguous
Insert frontO(1)O(n)
Insert backO(1)O(1)
Random accessO(1)O(1)
Cache-friendly❌✔

🔹 12. Deque vs List

Featuredequelist
Random access✔❌
Insert middleO(n)O(1)
Memory overheadMediumHigh
Cache-friendlyMediumLow

🔹 13. Time Complexity

OperationComplexity
push_front / push_backO(1)
pop_front / pop_backO(1)
Random accessO(1)
Insert middleO(n)

❌ Common Mistakes

dq[5]; // ❌ out of range (if size < 6)

✔ Use:

dq.at(5);

📌 Summary

  • deque = double-ended queue

  • Fast insertion/removal at both ends

  • Supports random access

  • Used internally by stack and queue

  • Good alternative to vector when front operations are needed

You may also like...