6

Deque Implementation Using C++ [Complete Guide]

 1 year ago
source link: https://www.journaldev.com/61941/deque-implementation-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Deque Implementation Using C

In this article, we will learn deque implementation using C++. Just like other data structures, deques play an essential role in software development. “Dequeues” implies doubly ended queues, i.e. expansion and contraction are possible in both directions. Queues are dynamic data structures, meaning you do not need to specify the size at the time of declaration. Let’s go through some basics of deques and learn to implement the CRUD operations.

What Are Deques?

Deques are dynamic double-ended queues that support insertion and deletion on both ends. A deque does not store its elements are contiguous memory locations, instead, it stores the elements at random locations. This provokes the random access of elements in a deque.

A deque supports the following functions for insertion and deletion.

  • push_front(): Adds an element to the front of the deque.
  • pop_front(): Deletes an element from the front of the deque.
  • push_back(): Adds an element at the rear of the deque.
  • pop_back(): Removes an element from the rear of the deque.

We can implement a deque in many different ways, but the most common way is by using a dynamic array. One disadvantage of using deques is that, for large sequences, the reallocation operations become very expensive.

If your operation involves frequent insertion and deletion at the ends, then deques are the way to go. Else, deques perform the worst for insertion and deletion not at the ends.

Enough of theory, let’s build some real deques and perform some crud operations on them using C++.

Deque Implementation Using STL C++

To demonstrate the use and working of the deque, we’ve taken the help of a problem from SPOJ. The problem is: Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

For example,
Array: [1 2 3 1 4 5 2 3 6]
K = 3
Ans: 3, 3, 4, 5, 5, 6
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main()
{
// take the input
cout << "Enter the number of elements in the array" << endl;
int n, copy_n;
cin >> n;
copy_n = n;
vector <int> arr;
cout << "Enter the array elements, press -1 to stop" << endl;
while(copy_n--)
{
int ele;
cin >> ele;
arr.push_back(ele);
}
// process the first k elements separately
cout << "Enter the value of k" << endl;
int k;
cin >> k;
// create a deque, below is the constructor
// call to initialize a deque and set its
// maximum size to k
deque <int> Q(k);
// after this loop you will have the index of the
// largest element in the first k elements of your
// array
for(int i = 0; i < k; i++)
{
while(!Q.empty() && arr[i] > arr[Q.back()])
{
Q.pop_back();
}
Q.push_back(i);
}
// process the remaining elements
for(int i = k; i < n; i++)
{
// first thing we will do is to
// print the element which is at the
// front of the queue
cout << arr[Q.front()] << " ";
// 1.Remove the elements which are not the part of
// a window (contraction)
while((!Q.empty()) && (Q.front() <= i - k))
{
// pop the element from the front
Q.pop_front();
}
// 2. Remove the elements which are not useful
// and are in the window (contraction)
while(!Q.empty() && (arr[i] > arr[Q.back()]))
{
// the elements which are smaller
// and are present in the current window
// are not of any use
Q.pop_back();
}
// 3. Add the new elements (expansion)
Q.push_back(i);
}
cout << arr[Q.front()] << endl;
return 0;
}
Deque Implementation Program 1
Deque Implementation Program 1
Deque Implementation Program 2
Deque Implementation Program 2

Output

Deque Implementation Output
Deque Implementation Output

Conclusion

Today we learned to implement a deque using STL. First, we went through the basics of the deque and its associated functions. Later we looked at a popular array-based problem at SPOJ. We understood the working of the deque by solving this problem. That’s all for today, thanks for reading.

Further Readings

To learn more about data structures and algorithms using C++, you can visit the following articles.

https://www.journaldev.com/61277/first-non-repeating-character-running-stream-c

https://www.journaldev.com/61662/intersection-point-of-two-linked-lists-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK