Deque, short for “double-ended queue”, is a versatile and efficient container provided by the C++ Standard Template Library (STL). It allows for dynamic resizing, provides constant time insertion and deletion at both ends, and offers random access to its elements.

Introduction to Deque

A deque is similar to a vector but supports efficient insertion and deletion at both its beginning and end. It stands out with its ability to expand and shrink dynamically, providing flexibility in managing data.

Characteristics of Deque

1. Double-Ended Access: Deque supports efficient insertion and deletion of elements at both its front and back ends.
2. Dynamic Resizing: Deque can dynamically resize itself to accommodate a varying number of elements.
3. Random Access: Deque supports random access to its elements, meaning that individual elements can be accessed directly using their indices.
4. Contiguous Storage: Deque stores its elements in a contiguous block of memory, ensuring efficient memory access and cache utilization.

Syntax of Deque

Include header file:

#include <deque>

std::deque<T> dequeName;

• Replace T with the type of elements you want to store in the deque, and dequeName with the name you choose for your deque variable.

Functions

1 push_back()

Adds an element ot the end of the deque.

std::deque<int> myDeque;
myDeque.push_back(10);

Time Complexity: Amortized constant time O(1)

2 push_front

Adds an element to the beginning of the deque

std::deque<int> myDeque;
myDeque.push_front(5);

Time Complexity: Amortized constant time O(1)

3 pop_back()

Removes the last element form the deque

std::deque<int> myDeque = {1, 2, 3};
myDeque.pop_back();

Time Complexity: Constant time O(1)

4 pop_front()

Removes the first element from the deque.

std::deque<int> myDeque = {1, 2, 3};
myDeque.pop_front();

Time Complexity: Constant time O(1)

5 front()

Returns a reference to the first element in the deque.

std::deque<int> myDeque = {1, 2, 3};
int firstElement = myDeque.front(); // firstElement will be 1

Time Complexity: Constant time O(1)

6 back()

Returns a reference to the last element in the deque.

std::deque<int> myDeque = {1, 2, 3};
int lastElement = myDeque.back(); // lastElement will be 3

Time Complexity: Constant time O(1)

7 empty()

Checks if the deque is empty.

std::deque<int> myDeque = {1, 2, 3};
bool isEmpty = myDeque.empty(); // isEmpty will be false

Time Complexity: Constant time O(1)

8 size()

Returns the number of elements in the deque.

std::deque<int> myDeque = {1, 2, 3};
int dequeSize = myDeque.size(); // dequeSize will be 3

Time Complexity: Constant time O(1)

9 clear()

Removes all elements from the deque.

std::deque<int> myDeque = {1, 2, 3};
myDeque.clear();

Time Complexity: Linear time O(n), where n is the number of elements in the deque.

10 at()

Accesses the element at the specified position with bounds checking.

std::deque<int> myDeque = {1, 2, 3};
int element = myDeque.at(1); // element will be 2

Time Complexity: Constant time O(1)

11 operator[]

Accesses the element at the specified position without bounds checking.

std::deque<int> myDeque = {1, 2, 3};
int element = myDeque[1]; // element will be 2

Time Complexity: Constant time O(1)

12 insert()

Inserts element at the specified position in the deque.

std::deque<int> myDeque = {1, 2, 3};
auto it = myDeque.begin() + 1;
myDeque.insert(it, 4); // Inserts 4 at the second position

Time Complexity: Linear time O(n), where n is the number of elements inserted plus the distance to the insertion point.

13 erase()

Removes elements from the deque from a specific position or range.

std::deque<int> myDeque = {1, 2, 3};
auto it = myDeque.begin() + 1;
myDeque.erase(it); // Removes the element at the second position

Time Complexity: Linear time O(n), where n is the number of elements erased plus the distance to the erased elements.