Applications, Advantages and Disadvantages of Deque

Deque or double-ended queue is a sequential linear collection data queue that provides functionality similar to a double-ended queue. In this data structure, the method does not follow the first-in-first-out (FIFO) rule for data processing. This data structure is also called a deque because elements are inserted at the end of the queue and removed from the front. With a deque, we can only add and remove data from both ends. The time complexity of deque operation is O(1). There are two types of deque -

• Input restricted

• Single-ended input limit.

• Allows data to be deleted from both ends.

• Output limited

• Single-ended output limit.

• # Allows inserting data to both ends.

The following commands help coders perform various operations using dataset pooling on a deque -

• push_back() - Inserts an element from the back of the deque.

• push_front() - Inserts an element from the front of the deque.

• pop_back() - Removes an element from the back of a deque.

• pop_front() - Removes elements from the front of the deque.

• front() - Returns the front element of the deque.

• back() - Returns the element at the back of the deque.

• at() - Sets/returns the specified index.

• size() - Returns the number of elements.

• empty() - Returns true if the deque is empty.

We can use double-ended queue operations in circular arrays. If the array is full then we can start the process from the beginning. But for linear array, if the array is full, no more data can be inserted. Then we can see an "overflow popup".

Application of double-ended queue

Deque has many real-time applications available.

• is used for job scheduling applications.

• We can perform clockwise and counterclockwise rotation operations in O(1) time.

• The double-ended queue algorithm is also present in web browser history.

• Used for undo operations in sorting.

Advantages of double-ended queue

Deque has many advantages.

• We can add and delete data from the front and back.

• Their size is dynamic.

• Deque provides efficient timing for performing operations.

• LIFO stack is used here.

• Cannot be reassigned here.

• This is a thread-safe process with proper synchronization.

• Cache friendly.

Disadvantages of double-ended queue

The disadvantage of double-ended queue is

• The Deque process has a high memory consumption rate.

• It has multi-thread synchronization issues.

• Not available on all platforms.

• Not suitable for implementing sorting operations.

• Deque has fewer features.

Algorithm of double-ended queue operation

• Step 1 - Consider a deque array of size n.

• Step 2 - Set the two pointers to "front=-1" (for front) and "rear=0" (for set).

There are many sub-parts of this process. We can perform multiple operations in a deque. We summarize them here.

• Algorithm for inserting data from front in deque:-

• Step 1 - Check the previous position.

• Step 2 - If "front

• Step 3 - Otherwise, we need to reduce "front" by 1.

• Step 4 - Add the new key element to the front of the array.

• Algorithm for inserting data after deque:-

• Step 1 - Check if the array is full.

• Step 2 - If full, apply "rear=0".

• Step 3 - Otherwise, increase the value of "rear" by 1.

• Step 4 - Add the new key to "array[rear]" again.

• Algorithm for deleting data from front of deque:-

• Step 1 - Check if the deque is empty.

• Step 2 - If the list is empty ("front=-1"), it is an underflow condition and deletion cannot be performed.

• Step 3 - If there is only one element in the deque. Then "front=rear=-1".

• Step 4 - Otherwise, "front" is at the end, then set to "front=0".

• Step 5 - Otherwise, front=front 1.

• Algorithm for deleting data from the back of a deque:-

• Step 1 - Check if the deque is empty.

• Step 2 - If empty ("front=-1"), the delete cannot be performed. This is an underflow condition.

• Step 3 - If the deque has only one data, then "front=rear=-1".

• Step 4 - Otherwise, follow the steps below.

• Step 5 - If rear is in front "rear=0". Go to front "rear = n-1".

• Step 6 - Otherwise, rear=rear-1.

• Algorithm to check if deque is empty:-

• Step 1 - If front=-1, the deque is empty.

• Algorithm to check if deque is full:-

• Step 1 - if before=0 and after=n-1

• Step 2 - Alternatively, front=rear 1

Syntax of double-ended queue

deque< object_type > deque_name;
deque<int> deque1 = {11, 21, 31, 41, 51};
deque<int> deque2 {10, 20, 30, 40, 50};

In the data structure, the double-ended queue inherits some properties of the stack and queue. In C, a deque is implemented as a vector of vectors.

Processing of various methods using double-ended queue

• Method 1 - Implementing a deque in a general way

• Method 2 - Insert element into deque

• Method 3 - Accessing elements from a deque

• Method 4 - Changing Elements of a Deque

General implementation of double-ended queue

In this C build code, we configure the deque operation in a generic way. In this example, we insert an element at the backend of the queue, and this is how the entire system performs.

Example 1

<iostream>#include <iostream>
using namespace std;
#define MAX 10

class Deque {
   int arr[MAX];
   int front;
   int rear;
   int size;

   public:
   Deque(int size) {
      front = -1;
      rear = 0;
      this->size = size;
   }

   void insertfront(int key);
   void insertrear(int key);
   void deletefront();
   void deleterear();
   bool isFull();
   bool isEmpty();
   int getFront();
   int getRear();
};
bool Deque::isFull() {
   return ((front == 0 && rear == size - 1) ||
      front == rear + 1);
}
bool Deque::isEmpty() {
   return (front == -1);
}
void Deque::insertfront(int key) {
   if (isFull()) {
      cout << "Overflow\n"
         << endl;
      return;
  }
  if (front == -1) {
     front = 0;
     rear = 0;
  }
  else if (front == 0)
     front = size - 1;
   else
     front = front - 1;
   arr[front] = key;
}
void Deque ::insertrear(int key) {
  if (isFull()) {
    cout << " Overflow\n " << endl;
    return;
  }

  if (front == -1) {
    front = 0;
    rear = 0;
  }

  else if (rear == size - 1)
    rear = 0;

  else
    rear = rear + 1;

  arr[rear] = key;
}
void Deque ::deletefront() {
   if (isEmpty()) {
      cout << "Queue Underflow\n"
      << endl;
      return;
   }

   if (front == rear) {
      front = -1;
      rear = -1;
   } else if (front == size - 1)
      front = 0;
   else
      front = front + 1;
}
void Deque::deleterear() {
   if (isEmpty()) {
      cout << " Underflow\n"
      << endl;
    return;
   }

   if (front == rear) {
       front = -1;
      rear = -1;
   } else if (rear == 0)
      rear = size - 1;
   else
      rear = rear - 1;
}
int Deque::getFront() {
   if (isEmpty()) {
      cout << " Underflow\n"
      << endl;
      return -1;
   }
   return arr[front];
}
int Deque::getRear() {
   if (isEmpty() || rear < 0) {
      cout << " Underflow\n"
      << endl;
      return -1;
   }
   return arr[rear];
}
int main() {
   Deque dq(4);
   cout << "insert element at rear end \n";
   dq.insertrear(5);
   dq.insertrear(11);
   cout << "rear element: "
   << dq.getRear() << endl;
   dq.deleterear();
   cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;
   cout << "insert element at front end \n";
   dq.insertfront(8);
   cout << "front element: " << dq.getFront() << endl;
   dq.deletefront();
   cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}

</iostream>

Output

insert element at rear end 
rear element: 11
after deletion of the rear element, the new rear element: 5
insert element at front end 
front element: 8
after deletion of front element new front element: 5

Insert element into deque

In this code, we are trying to create C code to insert elements into a deque. There are two ways to do this.

• push_back() - Inserts an element at the end of the array.

• push_front() - Inserts an element at the beginning of the array.

Example 2

#include <iostream>
#include <deque>
using namespace std;
int main() {
   deque<int> nums {16, 7};
   cout << "Initial Deque As We Give: ";
   for (const int& num : nums) {
      cout << num << ", ";
   }
   nums.push_back(2001);
   nums.push_front(1997);
   cout << "\nFinal Deque Is Here: ";
   for (const int& num : nums) {
      cout << num << ", ";
   }
   return 0;
}

Output

Initial Deque As We Give: 16, 7, 
Final Deque Is Here: 1997, 16, 7, 2001,

Accessing elements from a deque

We can access elements in a deque using two methods.

• front() - At the front we can get the return value.

• back() - Returns the following data.

• at() - Returns from the specified index.

#include <iostream>
#include <deque>
using namespace std;
int main() {
   deque<int> nums {16, 07, 10};
   cout << "Front element are here: " << nums.front() << endl;
   cout << "Back element are here: " << nums.back() << endl;
   cout << "Element at index 1 present here: " << nums.at(1) << endl;
   cout << "Element at index 0 present here: " << nums[0];
   return 0;
}

Output

Front element are here: 16
Back element are here: 10
Element at index 1 present here: 7
Element at index 0 present here: 16

Changing elements of a deque

In this code, we can use the at() method to replace or change the elements of that specific deque.

Example 4

#include <iostream>
#include <deque>
using namespace std;
int main() {
   deque<int> nums = {07,16,10,1997,2001};
   cout << "Initial Deque: ";
   for (const int& num : nums) {
      cout << num << ", ";
   }
   nums.at(0) = 2022;
   nums.at(1) = 10-05;
   cout << "\nUpdated Deque: ";
   for (const int& num : nums) {
      cout << num << ", ";
   }
   return 0;
}

Output

Initial Deque: 7, 16, 10, 1997, 2001, 
Updated Deque: 2022, 5, 10, 1997, 2001,

in conclusion

Through this article, we learned about the double-ended queue, its operation method, applications, advantages and disadvantages, as well as algorithms and possible codes using C.

The above is the detailed content of Applications, Advantages and Disadvantages of Deque. For more information, please follow other related articles on the PHP Chinese website!