Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Dequeue Operation
2.1.
Implementation of Deque 
3.
Insert Components at Beginning
3.1.
Insert Parts at End
3.2.
Delete Starting Component
3.3.
Delete Last Component
3.4.
Check If Queue is Empty
3.5.
Return Initial Element
4.
Sample Problem
4.1.
Implementing a Deque in Python
4.2.
Using Dequeue for Palindrome-Checker
5.
Frequently Asked Questions
5.1.
What do you mean by Deque?
5.2.
What are the operations you can perform in the deque?
5.3.
What are the benefits of deque?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Introduction to Deque its applications

Author Aditya kumar
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Dequeue stands for “Double concluded queue”, not like Queue arrangement (wherever we have a tendency to add some part from just one finish and delete the part from the different finish). In Dequeue we will add and delete a part from each the ends.

introduction to deque and its applications

That is we will add a part from {front finish|front|forepart|side|face} further as a side and additionally delete a part from side further as back end. In computing, a double-ended queue (Deque) is associate degree abstract information kind that generalises a Queue, that components are adscititious to or aloof from either the front (head) or back (tail) – Wikipedia.

implementation of deque

Also read, Duck Number in Java and Hashcode Method in Java

Dequeue Operation

Accessing information from the queue could be a method of two tasks − access the info where the front is informed and take away the info when access. the subsequent steps area unit taken to perform dequeue operation −

  • Step 1: Check if the queue has no elements left.
  • Step 2: If the queue is empty, turn out underflow error and exit.
  • Step 3: If the queue isn’t empty, access the info where the front is inform
  • Step 4: Increment front pointer to point to successive obtainable information part.
  • Step 5: Come success.

List Of Operations Available

  • AddFront: Insert a component at the front of the Deque..
  • AddBack: Insert a component at the rear of the Deque.
  • RemoveFront: Remove an element from the front.
  • RemoveBack: Remove a component from the rear.
  • PeekBack: This methodology returns the primary part of the Deque same as queue front method.
  • PeekFront: This methodology returns the top part of the Deque same as stack peek method.
  • Size: Return Size of the deque.
  • isEmpty: Check if the Deque is empty if empty come true else false.
  • Clear: Reset the Deque.

Implementation of Deque
 

// Most size of array or Dequeue
define SIZE 5
class Dequeue
{
//front and rear for storing the head and tail pointers
int *arr;
int front, rear;
public :

Dequeue()
{
    //Create the array
    arr = new int[SIZE];

    //Initialize front and rear with -1
    front = -1;
    rear = -1;
}

// Operations on Deque
void  push_front(int );
void  push_back(int );
void  pop_front();
void  pop_back();
int  get_front();
int  get_back();
bool  full();
bool  empty();   
};
void Dequeue :: push_front(int key)
{
	if(full())
	{
		cout << “OVERFLOW\n”;
	}
	else
	{
		//If queue is empty
		if(front == -1)
			front = rear = 0;
    	//If front points to the primary position compoenent
    	else if(front == 0)
        	front = SIZE-1;
    	else
        	--front;
    	arr[front] = key;
	}
}

Also see,  Swap Function in Java

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Insert Components at Beginning

First, we have a tendency to check if the queue is full. If it’s not full we have a tendency to insert a component at face by following the given conditions :

  • If the queue is empty then initialise front and rear to zero. each can purpose to the primary component.
queue is empty
  • Else we have a tendency to decrement front and insert the component. Since we have a tendency to are exploitation circular array, we’ve got to stay in mind that if the front is capable zero then rather than decreasing it by one we have a tendency to create it capable SIZE-1.
insertion at front
void Dequeue :: push_front(int key)
{
	if(full())
	{
		cout << “OVERFLOW\n”;
	}
	else
	{
		//If queue is empty
		if(front == -1)
			front = rear = 0;
    	//If front points to the primary position component
    	else if(front == 0)
        	front = SIZE-1;
    	else
        	--front;
    	arr[front] = key;
	}
}

Try it on java online compiler.

Insert Parts at End

Again we have a tendency to check if the queue is full. If its not full we have a tendency to insert a component at back by following the given conditions:

  • If the queue is empty then intialise front and rear to zero. each can purpose to the primary component.
  • Else we have a tendency to increment rear and insert the component. Since we have a tendency to ar exploitation circular array, we’ve got to stay in mind that if the rear is capable SIZE-1 then rather than increasing it by one we have a tendency to create it capable zero.
insertion at rear
void Dequeue :: push_back(int key)
{
	if(full())
	{
		cout << “OVERFLOW\n”;
	}
	else
	{
    	//If queue is empty
       	if(front == -1)
          	front = rear = 0;

       	//If rear points to the last component
    	else if(rear == SIZE-1)
        	rear = 0;

    	else
        	++rear;

    	arr[rear] = key;
	}    
}

Delete Starting Component

In order to try and do this, we have a tendency to initial check if the queue has no elements left. If it does not then delete the front component by following the given conditions:

  • If just one component is a gift we have a tendency to another time create front and rear capable -1.
  • Else we have a tendency to increment front. However, we’ve got to stay in mind that if the front is capable SIZE-1 then rather than increasing it by one we have a tendency to create it capable zero.
deletion from front
void Dequeue :: pop_front()
{
	if(empty())
	{
		cout << “UNDERFLOW\n”;
	}
	else
	{
		//If only one component is there
		if(front == rear)
			front = rear = -1;
    	//If front is pointing to the last component
    	else if(front == SIZE-1)
        	front = 0;
    	else
        	++front;        
	}
}

Delete Last Component

In order to try and do this, we have a tendency to once more initial check if the queue is empty. If its not then we have a tendency to delete the last component by following the given conditions :

  • If just one component is a gift we have a tendency to create front and rear capable -1.
  • Else we have a tendency to decrement rear. However, we’ve got to stay in mind that if the rear is capable zero then rather than decreasing it by one we have a tendency to create it capable SIZE-1.
deletion from last
void Dequeue :: pop_back()
{
	if(empty())
	{
		cout << “UNDERFLOW\n”;
	}
	else
	{
	//If only single component is there
		if(front == rear)
			front = rear = -1;
    	//If rear points to the primary position component
    	else if(rear == 0)
        	rear = SIZE-1;
    	else
        	--rear;     
	}
}

Check If Queue is Empty

It is merely checked by wanting wherever front points to. If the front continues to be intialised with -1, the queue is empty.

bool Dequeue :: empty()
{
	if(front == -1)
		return true;
	else
		return false;
}

Check if Queue is full
Since we have a tendency to are exploitation circular array, we have a tendency to check for following conditions as shown in code to ascertain if queue is full.

bool Dequeue :: full()
{
	if((front == 0 && rear == SIZE-1) || (front == rear + 1))
		return true;
	else
		return false;
}

Return Initial Element

If the queue isn’t empty then we have a tendency to merely come to the worth hold on within the position that front points.

int Dequeue :: get_front()
{
	if(empty())
	{ 
		cout << “f=” <<front << endl;
		cout << “UNDERFLOW\n”;
		return -1;
	}
	else
	{
		return arr[front];
	}
}

Return Last Component
If the queue isn’t empty then we have a tendency to merely come the worth hold on within the position that rear points.

int Dequeue :: get_back()
{
	if(empty())
	{
		cout << “UNDERFLOW\n”;
		return -1;
	}
	else
	{
		return arr[rear];
	}
}

Sample Problem

Maximum of all subarrays of size k 

Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.

Example 1

Input
9 3
1 2 3 1 4 5 2 3 6
Output
3 3 4 5 5 5 6
Explanation
1st contiguous subarray = {1 2 3} Max = 3

2nd contiguous subarray = {2 3 1} Max = 3
3rd contiguous subarray = {3 1 4} Max = 4
4th contiguous subarray = {1 4 5} Max = 5
5th contiguous subarray = {4 5 2} Max = 5
6th contiguous subarray = {5 2 3} Max = 5
7th contiguous subarray = {2 3 6} Max = 6

Example 2

Input
10 4
8 5 10 7 9 4 15 12 90 13
Output
10 10 10 15 15 90 90

Your Task
You don’t need to read input or print anything. Complete the function max_of_subarrays() which takes the array, N and K as input parameters and returns a list of integers denoting the maximum of every contiguous subarray of size K.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 107
1 ≤ K ≤ N
0 ≤ arr[i] <= 107

class solve{
	static ArrayList max_of_subarrays(int arr[], int n, int k)
	{
		//Declaring and Initializing an ArrayList of base size zero
		ArrayList res = new ArrayList (0);
    	//Declaring and Initialising an ArrayDeque
    	ArrayDeque<Integer> dq = new ArrayDeque<>();

    	//Creating a StringBuilder variable sb
    	StringBuilder sb = new StringBuilder();

    	int i = 0;

    	//adding solely the utmost component index within the vary
    	// 0 to k-1 and polling the remaining parts index
    	for(i  = 0; i < k ; i++)
    	{
        	while(dq.isEmpty() == false && arr[i] >= arr[dq.peekLast()])
          	dq.pollLast();

          	dq.add(i);
    	}

    	//adding solely the utmost component index within the vary
    	// interval k and polling the remaining parts index
    	for(; i < n; i++)
    	{
        	//adding the utmost in interval k
        	//to the ArrayList
        	res.add(arr[dq.peek()]);

        	while(dq.isEmpty() == false && (dq.peekFirst() <= i-k))
           	dq.pollFirst();

         	while(dq.isEmpty() == false && (arr[i] >= arr[dq.peekLast()]))
            	dq.pollLast();

        	dq.add(i);
    	}

      	//adding the last component of the
      	//ArrayDeque to the ArrayList
      	res.add(arr[dq.peek()]);
       	dq.pollFirst();

      	//returning the ArrayList of most parts 
      	//in subArrays of size k
      	return res;

	}
}

Implementing a Deque in Python

class Deque:
    def __init__(self):
        self.items=[]
    def isEmpty(self):
        come self.items ==[]def addFront(self,item):
        self.items.append(item)def addRear(self, item):
        self.items.insert(0,item)def removeFront(self):
        come self.items.pop()def removeRear(self):
        come self.items.pop(0)def size(self):
        come len(self.items)    

Using Dequeue for Palindrome-Checker

Since we are able to take away each of them directly, we are able to compare them and continue given that they match. If we are able to keep matching initial and also the last things, we’ll eventually either run out of characters or be left with a deque of size one betting on whether or not the length of the first string was even or odd. In either case, the string should be a word.

from pythonds.basic.deque import Deque
def palchecker(aString):
    chardeque=Deque()for ch in aString:
    chardeque.addRear(ch)stillEqual=TrueWhile chardeque.size()>one and stillEqual:
    initial=chardeque.removeFront()
    last=chardeque.removeRear()
    if initial!=last:
        stillEqual=Falsereturn stillEqualprint(palchecker("lsdkjsf"))
        print(palchecker("radar"))    

Frequently Asked Questions

What do you mean by Deque?

The characteristics of queues and stacks are both inherited by the data structure known as deque.

What are the operations you can perform in the deque?

You can perform AddFront, AddBack, RemoveFront, RemoveBack, PeekBack, PeekFront, etc.

What are the benefits of deque?

From the front and the back of the queue, you can add and remove things. Deques make it easier to add and remove components from the end or beginning of a sentence. A deque rotates rapidly in both the clockwise and counterclockwise directions.

Also read palindrome number in python.

Conclusion

Applications of Deque

  • An internet browser’s history. Recently visited URLs are supplementary to the front of the deque, and also the uniform resource locator at the rear of the deque is removed when some such range of insertions at the front.
  • Another common application of the deque is storing a computer code application’s list of undo operations.
  • Have you ever see Money-Control App, it’ll show the stocks you last visited, it’ll take away the stocks when a while and can add the most recent ones.
complexity

Since Deque supports each stack and queue operations, it is used as each. The Deque organisation supports right-handed and anticlockwise rotations in O(1) time which may be helpful inbound applications. Also, the issues wherever parts got to be removed and or supplementary each end is expeditiously resolved exploitation Deque. 

For further reading, you may refer to other blogs on Implementation of Queuereversing a queuereversing the first k elements of a queueApplication of Linked List, Advantages of Circular Queue and Implement min heap in C++. You can also go through Data Structure.

Some Standard Problems On Deque

  • The nth term of given recurrence relation having each term equal to the product of previous K terms.
  • Substring of length K having a maximum frequency in the given string.
  • Maximise the length of a subarray of equal elements by performing at most K increment operations.
  • Rearrange and update array elements as specified by the given queries.
  • Largest string obtained in Dictionary order after deleting K characters.
  • Rearrange a linked list into alternate first and last element.
  • Minimise the maximum difference between adjacent elements in an array.

To explore our courses, click here.