What is STL Deque in C++?

A deque (Double-Ended Queue) is a sequence container in the Standard Template Library (STL) that allows efficient insertion and deletion of elements at both the beginning and the end.

Unlike a vector, which is optimized for operations at the end, a deque is designed for efficient operations at both ends.

Think of a deque as a train where passengers can board or leave from either the front or the back, making it more flexible than a single-entry train.

Why does STL Deque exist?

A std::vector is very efficient for adding elements at the end, but inserting or removing elements at the beginning requires shifting all remaining elements.

• Fast insertion at the front
• Fast insertion at the back
• Fast deletion at the front
• Fast deletion at the back
• Random access to elements

Real-world use cases

• Browser history navigation
• Undo/redo functionality
• Task scheduling
• Sliding window algorithms
• CPU scheduling
• Double-ended queues in operating systems
• Palindrome checking
• Game event queues

Prerequisites

• Variables and data types
• Arrays
• Loops
• Functions
• Templates
• Basic STL containers, especially std::vector

Including the header

#include <deque>

Creating a deque

deque<data_type> deque_name;

// Example:
deque<int> numbers;

Initializing a deque

• deque<int> d; – empty deque
• deque<int> d(5); – five elements initialized to 0
• deque<int> d(5, 10); – five elements initialized to 10
• deque<int> d = {1,2,3}; – initialize using a list

Characteristics of STL Deque

• Memory layout: non-contiguous blocks
• Random access: supported
• Front insertion: O(1)
• Back insertion: O(1)
• Middle insertion: O(n)
• Front deletion: O(1)
• Back deletion: O(1)

Common deque operations

• push_back() – add element at the end
• push_front() – add element at the beginning
• pop_back() – remove last element
• pop_front() – remove first element
• front() – access first element
• back() – access last element
• at() – safe indexed access
• operator[] – direct indexed access
• insert() – insert an element
• erase() – remove an element
• size() – number of elements
• empty() – check if deque is empty
• clear() – remove all elements

How deques store data

Unlike vectors, deques do not store all elements in one continuous memory block.

Instead, they use multiple fixed-size memory blocks connected together. This allows efficient insertions and deletions at both ends without moving all elements.

Iterating through a deque

for (int value : numbers)
{
    cout << value << " ";
}

// You can also use index-based loops or iterators.

Example 1: Creating and displaying a deque

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

int main()
{
    deque<int> numbers;

    numbers.push_back(20);
    numbers.push_back(30);
    numbers.push_front(10);

    for (int num : numbers)
    {
        cout << num << " ";
    }

    return 0;
}

// Output: 10 20 30

Example 2: Accessing elements

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

int main()
{
    deque<int> marks = {80, 85, 90};

    cout << "First: " << marks.front() << endl;
    cout << "Last: " << marks.back() << endl;
    cout << "Second: " << marks.at(1) << endl;

    return 0;
}

// Output:
// First: 80
// Last: 90
// Second: 85

Example 3: Inserting and removing elements

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

int main()
{
    deque<int> values = {2, 3, 4};

    values.push_front(1);
    values.push_back(5);

    values.pop_front();
    values.pop_back();

    for (int value : values)
    {
        cout << value << " ";
    }

    return 0;
}

// Output: 2 3 4

Example 4: Sliding window maximum

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

int main()
{
    vector<int> numbers = {1, 3, 2, 5, 4};
    deque<int> window;

    for (int num : numbers)
    {
        window.push_back(num);

        if (window.size() > 3)
        {
            window.pop_front();
        }

        cout << "Window: ";

        for (int value : window)
        {
            cout << value << " ";
        }

        cout << endl;
    }

    return 0;
}

Example 5: Browser navigation

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

int main()
{
    deque<string> history;

    history.push_back("Home");
    history.push_back("Products");
    history.push_back("Cart");

    cout << "Current Page: ";
    cout << history.back() << endl;

    history.pop_back();

    cout << "After Back: ";
    cout << history.back() << endl;

    return 0;
}

Common mistakes and pitfalls

• Using push_back() when front insertion is needed. Fix: use push_front() for efficient front insertion
• Assuming deque stores elements contiguously. Fix: remember that a deque uses multiple memory blocks
• Accessing invalid indexes. Fix: use at() when bounds checking is required
• Using a deque for frequent middle insertions. Fix: consider std::list for efficient middle insertions
• Forgetting to check if the deque is empty before calling front() or back(). Fix: always check empty() first

Best practices

• Use deque when you need efficient insertions and deletions at both ends
• Prefer vector if operations are mostly at the back and cache performance is important
• Use at() when index validation is required
• Pass large deques by const reference to functions
• Use range-based for loops for cleaner code
• Avoid frequent insertions in the middle of a deque

When not to use this

• Frequent middle insertions or deletions are required (use std::list)
• Maximum cache efficiency is important (use std::vector)
• The collection size is fixed (consider std::array)
• You require sorted key-value storage (use std::map or std::set)
• You only need insertion and deletion at one end (consider std::stack or std::queue adapters)

Summary

• STL Deque in C++ is a double-ended queue that allows efficient insertion and deletion at both the front and the back
• Deques support random access using indexes, similar to vectors
• Elements are stored in multiple memory blocks rather than a single contiguous block
• Common operations include push_front(), push_back(), pop_front(), pop_back(), front(), back(), insert(), erase(), size(), and clear()
• Use std::deque when your application requires efficient operations at both ends of the container
• Prefer std::vector when most operations occur at the end and memory locality is important

Frequently asked questions

What is the difference between a vector and a deque?

A vector stores elements in contiguous memory and is optimized for operations at the end. A deque stores elements in multiple memory blocks and supports efficient insertions and deletions at both the front and the back.

Can I access deque elements using an index?

Yes. Like a vector, a deque supports both the [] operator and the at() member function for random access.

Why is a deque called a Double-Ended Queue?

Because it allows elements to be inserted and removed efficiently from both the front and the back of the container.

What is the time complexity of inserting into a deque?

push_front() is O(1), push_back() is O(1), and middle insertion is O(n).

When should I use std::deque instead of std::vector?

Use std::deque when your application frequently inserts or removes elements from both ends. If your operations are mostly at the back and you need the best cache performance, std::vector is usually the better choice.