Deque in C++: The Complete Guide

0
397
Deque in C++ Example | C++ Deque Program

Deque stands for a double-ended queue. It is pronounced as “deck”. It is containers that have dynamic sizes and can be expanded or contracted on both ends, i.e., both ends are operational in this deque.

Vectors also have contiguous storage allocation, but memory is generally dynamically allocated in the case of the deque.

Deque in C++

Deque in C++ is a data structure implemented on the double-ended queue. It is related to queue as queue insertion is done at the end, and deletion is done from the front.

Double-ended queues are individual queues in which insertion and deletion are possible at both ends.

The std::deque(double-ended queue) is an indexed sequence container that allows fast insertion and deletion at its beginning and end.

In addition, insertion and deletion at either end of a deque never invalidate pointers or references to the rest of the elements.

Deque has the function of pop() and push() for both front and back.

Initialization of deque :  deque <x> deque_name where x is the datatype.

Different methods associated with deque

insert()

It is used to insert an element and returns an iterator that points to the first of the newly inserted elements.

rbegin()

It returns a reverse iterator, which points to the last element of the deque.

rend()

It returns a reverse iterator, which points to the position before the beginning of the deque.

cbegin()

It returns a constant iterator, which points to the first element of the container.

assign()

It is used to assign values to the same or different deque container.

max_size()

It returns the maximum number of elements that a particular deque can hold.

resize()

This function changes the size of the queue.

push_front()

It pushes the elements into a deque from the front.

push_back()

It is used to push the elements in a deque from the back.

pop_front()

It is used to pop elements from the front of the queue.

pop_back()

It is used to pop elements from the back of the queue.

clear()

It is used to remove all the items from the deque.

erase()

It is used to remove items from a specified position.

front()

It is used to reference the first element of the deque.

back()

It is used to reference the last element of the deque.

at()

This is used to reference the element present at the position given as the parameter to that given function.

swap()

It is used to swap the contents of one deque with another deque of the same type and size.

begin()

It returns the iterator to the first element of the deque.

end()

It returns an iterator to the last element of the deque.

emplace_front()

It is used to insert a new element at the beginning of the queue.

emplace_back()

It is used to insert a new element at the back of the container.

There are more methods defined for deque.

C++ Deque Program

Q1- Write a program to push two elements from the front end and two from the back end and print the deque.

#include <iostream>
#include <deque>

using namespace std;

void showdata(deque<int> deque1)
{
  deque<int>::iterator iterator_1;
  for (iterator_1 = deque1.begin(); iterator_1 != deque1.end(); ++iterator_1)
    cout << "\t" << *iterator_1;
  cout << "\n";
}

int main()
{
  deque<int> myqueue;
  myqueue.push_front(230); // getting data from front
  myqueue.push_front(240); // getting data from front
  myqueue.push_back(250);  // getting data from back
  myqueue.push_back(260);  // getting data from back
  cout << "Deque elements are: ";
  showdata(myqueue);

  return (0);
}

See the following output.

 

Deque in C++ Example

Q2- Write a program to push five elements in a deque, pop two elements, and then print the deque size.

#include <iostream>
#include <deque>

using namespace std;

void showdata(deque<int> deque1)
{
  deque<int>::iterator iterator_1;
  for (iterator_1 = deque1.begin(); iterator_1 != deque1.end(); ++iterator_1)
    cout << "\t" << *iterator_1;
  cout << "\n";
}

int main()
{
  deque<int> myqueue;
  myqueue.push_front(230); // getting data from front
  myqueue.push_front(240); // getting data from front
  myqueue.push_back(250);  // getting data from back
  myqueue.push_back(260);  // getting data from back
  cout << "Deque elements before popping are: ";
  showdata(myqueue);

  myqueue.pop_back();
  myqueue.pop_back();
  cout << "Deque elements after popping are: ";
  showdata(myqueue);

  cout << "Final size of the deque is: " << myqueue.size() << endl;
  return (0);
}

See the output.

C++ Deque Program

Time Complexity

The complexity (efficiency) of main operations on deques is as follows:

  1. Random access: constant O(1)
  2. Insertion or removal of items at the end or beginning – constant O(1)
  3. Insertion or removal of items – linear O(n)

Conclusion

Deques are one of the many Standard Template Library (STL) containers currently available in C++.

Their name suggests a better deal about their intended usage and what is possible with them.

That’s it.

Recommended Posts

Queues in C++

C++ List

C++ Iterators

C++ Array

Leave A Reply

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.