Introduction to Deque its applications

Table of Contents

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.

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.

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

}

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.

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.

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

}

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.

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.

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.

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:

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

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.

Conclusion:

Applications of Deque:

An internet browser’s history. Recently visited URLs ar 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.

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.

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.

By Yogesh Kumar