mar. Déc 6th, 2022

Hello Android

All android in one place

Deque Implementation Using C++ [Complete Guide]

2 min read

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 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

www.hello-android.com

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Hello android © All rights reserved. | Newsphere by AF themes.