C++ Deque

Key Deque Operations

myDeque.push_front(10);
myDeque.pop_front();

myDeque.push_back(20);
myDeque.pop_back();

cout << myDeque[0];
myDeque.at(1) = 100;

cout << myDeque.size();
cout << myDeque.empty();

🔹 Basic Deque Operations

A deque (double-ended queue) supports fast insertion and deletion at both its front and back. You can use push_front(), push_back(), pop_front(), and pop_back() to modify ends efficiently. Unlike vectors, deques don’t guarantee contiguous storage but offer constant-time front operations. They are ideal for scenarios requiring a sliding window, queues, or stacks where elements are frequently added or removed from both ends.

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

int main() {
    // Create a deque
    deque<int> numbers;
    
    // Add elements at both ends
    numbers.push_back(30);
    numbers.push_back(40);
    numbers.push_front(20);
    numbers.push_front(10);
    
    // Display deque
    cout << "Deque: ";
    for(int i = 0; i < numbers.size(); i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;
    
    // Access first and last elements
    cout << "First: " << numbers.front() << endl;
    cout << "Last: " << numbers.back() << endl;
    
    return 0;
}

🔹 Deque Insertion and Deletion

Deques provide efficient methods for inserting and erasing elements at either end or in the middle. While front/back operations are O(1), insertions in the middle are linear time. Functions like insert() and erase() work with iterators for precise positioning. For example, you can add a color to the front, remove one from the back, or insert an element at a specific index. This flexibility makes deques versatile for dynamic sequences.

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

int main() {
    deque<string> colors = {"red", "green", "blue"};
    
    // Add at front and back
    colors.push_front("yellow");
    colors.push_back("purple");
    
    cout << "After adding: ";
    for(const string& color : colors) {
        cout << color << " ";
    }
    cout << endl;
    
    // Remove from front and back
    colors.pop_front();
    colors.pop_back();
    
    cout << "After removing: ";
    for(const string& color : colors) {
        cout << color << " ";
    }
    cout << endl;
    
    // Insert at specific position
    colors.insert(colors.begin() + 1, "orange");
    
    cout << "After insert: ";
    for(const string& color : colors) {
        cout << color << " ";
    }
    
    return 0;
}

🔹 Deque vs Vector vs List

Choosing between deque, vector, and list depends on your access patterns and modification needs. Vectors provide O(1) random access and maintain contiguous memory, making them ideal for frequent index-based lookups, but suffer from slow front insertions and deletions. Deques offer efficient O(1) operations at both ends while supporting fast random access, though they don't guarantee contiguous storage. Lists excel at constant-time insertions and deletions anywhere in the sequence but lack random access capability, requiring iterators for traversal. Select std::vector for predominantly sequential or back-end operations, std::deque when you need fast front and back modifications, and std::list for frequent middle insertions or deletions to optimize performance and memory usage in your applications.

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

int main() {
    deque<int> myDeque;
    vector<int> myVector;
    
    // Deque: Fast front insertion
    auto start = chrono::high_resolution_clock::now();
    for(int i = 0; i < 1000; i++) {
        myDeque.push_front(i);
    }
    auto end = chrono::high_resolution_clock::now();
    cout << "Deque front insertion: Fast" << endl;
    
    // Vector: Slow front insertion (needs shifting)
    start = chrono::high_resolution_clock::now();
    for(int i = 0; i < 1000; i++) {
        myVector.insert(myVector.begin(), i);
    }
    end = chrono::high_resolution_clock::now();
    cout << "Vector front insertion: Slow" << endl;
    
    // Both support random access
    cout << "Deque[500]: " << myDeque[500] << endl;
    cout << "Vector[500]: " << myVector[500] << endl;
    
    return 0;
}