C++/STL Containers Programs/Program

Deque (Double-ended Queue)

Deque Operations in C++

C++Intermediate
C++
Try
#include <iostream>
#include <deque>
using namespace std;

int main() {
    // Create deque
    deque<int> dq;
    
    // Add elements at both ends
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_front(5);
    dq.push_front(1);
    
    cout << "Deque elements: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "Front: " << dq.front() << endl;
    cout << "Back: " << dq.back() << endl;
    cout << "Size: " << dq.size() << endl;
    
    // Access elements by index
    cout << "Element at index 2: " << dq[2] << endl;
    cout << "Element at index 2 (at): " << dq.at(2) << endl;
    
    // Remove from front
    dq.pop_front();
    cout << "\nAfter pop_front: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    // Remove from back
    dq.pop_back();
    cout << "After pop_back: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    // Insert at specific position
    dq.insert(dq.begin() + 1, 15);
    cout << "\nAfter inserting 15 at index 1: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    // Erase element
    dq.erase(dq.begin() + 1);
    cout << "After erasing element at index 1: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output

Deque elements: 1 5 10 20 30
Front: 1
Back: 30
Size: 5
Element at index 2: 10
Element at index 2 (at): 10

After pop_front: 5 10 20 30
After pop_back: 5 10 20

After inserting 15 at index 1: 5 15 10 20
After erasing element at index 1: 5 10 20

This program teaches you how to use Deque (Double-ended Queue) in C++. Deque allows efficient insertion and deletion at both ends, combining the benefits of vectors and queues. It provides random access like vectors but with efficient front operations.

1. What This Program Does

The program demonstrates deque operations:

  • Adding elements at front and back
  • Removing elements from front and back
  • Random access using index
  • Inserting and erasing at specific positions

Deques provide flexible, efficient double-ended operations.

2. Header Files Used

  1. #include <iostream>

    • Provides cout and cin for input/output operations.

  2. #include <deque>

    • Provides deque container class.

3. Understanding Deque

Double-ended Queue Concept:

  • Insert/delete at both ends
  • Random access like vectors
  • Efficient front and back operations
  • Collection of memory blocks

Key Features:

  • O(1) operations at both ends
  • Random access (like arrays)
  • Flexible insertion/deletion
  • Combines vector and queue benefits

4. Adding Elements

At Back:

dq.push_back(10); // Add to end

At Front:

dq.push_front(5); // Add to beginning

How it works:

  • push_back(): adds to end (like vector)
  • push_front(): adds to beginning (unique to deque)
  • Both O(1) operations
  • Flexible insertion

5. Removing Elements

From Back:

dq.pop_back(); // Remove from end

From Front:

dq.pop_front(); // Remove from beginning

How it works:

  • pop_back(): removes from end
  • pop_front(): removes from beginning
  • Both O(1) operations
  • Flexible deletion

6. Accessing Elements

Random Access:

dq[2] // Element at index 2 dq.at(2) // Element at index 2 (with bounds check)

Front and Back:

dq.front() // First element dq.back() // Last element

How it works:

  • [] operator: array-like access
  • at(): bounds-checked access
  • front()/back(): end elements
  • O(1) access

7. Inserting at Position

Using insert():

dq.insert(dq.begin() + 1, 15);

How it works:

  • Inserts at specified position
  • Uses iterator arithmetic
  • O(n) operation (may shift elements)
  • Flexible but expensive for large deques

8. When to Use Deque

Best For:

  • Need both stack and queue operations
  • Random access required
  • Efficient front and back operations
  • Sliding window problems
  • Both ends manipulation

Example Scenarios:

  • Sliding window maximum
  • Palindrome checking
  • Both ends processing
  • Queue with random access
  • Double-ended operations

9. Important Considerations

Performance:

  • Front/back operations: O(1)
  • Random access: O(1)
  • Middle insert/erase: O(n)
  • More efficient than vector for front operations

Memory Layout:

  • Collection of memory blocks
  • Not contiguous like vector
  • Slightly less cache-friendly
  • More flexible memory management

Flexibility:

  • Combines vector and queue
  • Best of both worlds
  • Use when need both capabilities
  • More versatile than vector or queue alone

10. return 0;

This ends the program successfully.

Summary

  • Deque: double-ended queue, efficient insertion/deletion at both ends.
  • Operations: push_front(), push_back(), pop_front(), pop_back(), front(), back(), at(), [].
  • O(1) operations at both ends, O(1) random access, O(n) for middle operations.
  • Understanding deques enables flexible double-ended data manipulation.
  • Essential when both stack and queue functionality needed with random access.

This program is fundamental for learning double-ended containers, understanding flexible data structures, and preparing for algorithms requiring both ends manipulation in C++ programs.

Previous
Priority Queue