C++ Deque

C++ Deque (Double-Ended Queue)

The word Deque stands for "Double-Ended Queue" and is generally pronounced like "deck" (as in a deck of cards).

Unlike a standard queue where you can only add to the back and remove from the front, a Deque allows you to add and remove elements from both ends efficiently!

1. Using a Deque

To use this data structure, include the <deque> library.

It shares many similarities with vectors (including the ability to access elements by index), but provides fast operations at both the beginning and the end.

Key Deque Functions:

• .push_front() - Adds an element to the beginning.
• .push_back() - Adds an element to the end.
• .pop_front() - Removes the first element.
• .pop_back() - Removes the last element.

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

int main() {
  deque<int> numbers;
  // Add to the back
  numbers.push_back(10);
  numbers.push_back(20);
  // Add to the front
  numbers.push_front(5);
  numbers.push_front(1);
  // Current deque: {1, 5, 10, 20}
  cout << "First element: " << numbers.front() << "\n";
  cout << "Last element: " << numbers.back() << "\n";
  // Access via index is allowed in a Deque!
  cout << "Element at index 2: " << numbers[2] << "\n"; // Outputs 10
  return 0;
}

2. Deque vs. Vector

While they act similarly, a deque is preferred over a vector when you know your program will frequently need to insert or delete items at the start of the data structure. Doing this in a vector is very slow because every subsequent item has to shift over in memory.