Deque

The dequeue stands for Double Ended Queue. In the queue, the insertion takes place from one end while the deletion takes place from another end. The end at which the insertion occurs is known as the rear end whereas the end at which the deletion occurs is known as front end.

 Deque is a linear data structure in which the insertion and deletion operations are performed from both ends. We can say that deque is a generalized version of the queue.

Some properties of deque:

Deque can be used both as stack and queue as it allows the insertion and deletion operations on both ends.

In deque, the insertion and deletion operation can be performed from one side. The stack follows the LIFO rule in which both the insertion and deletion can be performed only from one end; therefore, we conclude that deque can be considered as a stack.

 

In deque, the insertion can be performed on one end, and the deletion can be done on another end. The queue follows the FIFO rule in which the element is inserted on one end and deleted from another end. Therefore, we conclude that the deque can also be considered as the queue.

 

There are two types of Queues, Input-restricted queue, and output-restricted queue.

Input-restricted queue: The input-restricted queue means that some restrictions are applied to the insertion. In input-restricted queue, the insertion is applied to one end while the deletion is applied from both the ends.

 

Output-restricted queue: The output-restricted queue means that some restrictions are applied to the deletion operation. In an output-restricted queue, the deletion can be applied only from one end, whereas the insertion is possible from both ends.

 

Applications of Deque

• The deque can be used as a stack and queue; therefore, it can perform both redo and undo operations.
• It can be used as a palindrome checker means that if we read the string from both ends, then the string would be the same.
• It can be used for multiprocessor scheduling. Suppose we have two processors, and each processor has one process to execute. Each processor is assigned with a process or a job, and each process contains multiple threads. Each processor maintains a deque that contains threads that are ready to execute. The processor executes a process, and if a process creates a child process then that process will be inserted at the front of the deque of the parent process. Suppose the processor P₂ has completed the execution of all its threads then it steals the thread from the rear end of the processor P₁ and adds to the front end of the processor P₂. The processor P₂ will take the thread from the front end; therefore, the deletion takes from both the ends, i.e., front and rear end. This is known as the A-steal algorithm for scheduling.

Implementation of Deque using a circular array

 

The following are the steps to perform the operations on the Deque:

Enqueue operation

• Initially, we are considering that the deque is empty, so both front and rear are set to -1, i.e., f = -1 and r = -1. 

 

• As the deque is empty, so inserting an element either from the front or rear end would be the same thing. Suppose we have inserted element 1, then front is equal to 0, and the rear is also equal to 0. 

•   Suppose we want to insert the next element from the rear. To insert the element from the rear end, we first need to increment the rear, i.e., rear=rear+1. Now, the rear is pointing to the second element, and the front is pointing to the first element.

 

• Suppose we are again inserting the element from the rear end. To insert the element, we will first increment the rear, and now rear points to the third element.

 

• If we want to insert the element from the front end, and insert an element from the front, we have to decrement the value of front by 1. If we decrement the front by 1, then the front points to -1 location, which is not any valid location in an array. So, we set the front as (n -1), which is equal to 4 as n is 5. Once the front is set, we will insert the value as shown in the below figure:

 

Dequeue Operation

• If the front is pointing to the last element of the array, and we want to perform the delete operation from the front. To delete any element from the front, we need to set front=front+1. Currently, the value of the front is equal to 4, and if we increment the value of front, it becomes 5 which is not a valid index. Therefore, we conclude that if front points to the last element, then front is set to 0 in case of delete operation.

 

• If we want to delete the element from rear end then we need to decrement the rear value by 1, i.e., rear=rear-1 as shown in the below figure:

• If the rear is pointing to the first element, and we want to delete the element from the rear end then we have to set rear=n-1 where n is the size of the array as shown in the below figure:

Implementation of Double Ended Queue  using array

 

 

#include<stdio.h>
#include<conio.h>
#define SIZE 100

void enQueue(int);
int deQueueFront();
int deQueueRear();
void enQueueRear(int);
void enQueueFront(int);
void display();

int queue[SIZE];
int rear = 0, front = 0;

int main()
{
    char ch;
    int choice1, choice2, value;
    printf("\n******* Type of Double Ended Queue *******\n");
     do
     {
          printf("\n1.Input-restricted deque \n");
          printf("2.output-restricted deque \n");
          printf("\nEnter your choice of Queue Type : ");
          scanf("%d",&choice1);
          switch(choice1)
          {
               case 1:
                    printf("\nSelect the Operation\n");
                    printf("1.Insert\n2.Delete from Rear\n3.Delete from Front\n4. Display");
                    do
                    {
                       printf("\nEnter your choice for the operation in c deque: ");
                       scanf("%d",&choice2);
                       switch(choice2)
                       {   
                          case 1: enQueueRear(value);
                                  display();
                                 break;
                             case 2: value = deQueueRear();
                                 printf("\nThe value deleted is %d",value);
                                  display();
                                 break;
                          case 3: value=deQueueFront();
                                     printf("\nThe value deleted is %d",value);
                                  display();
                                     break;
                          case 4: display();
                                  break;
                          default:printf("Wrong choice");
                       }
                       printf("\nDo you want to perform another operation (Y/N): ");
                       ch=getch();
                    }while(ch=='y'||ch=='Y');
                    getch();
                    break;
     
               case 2 :
                   printf("\n---- Select the Operation ----\n");
                   printf("1. Insert at Rear\n2. Insert at Front\n3. Delete\n4. Display");
                   do
                   {
                      printf("\nEnter your choice for the operation: ");
                      scanf("%d",&choice2);
                      switch(choice2)
                      {   
                         case 1: enQueueRear(value);
                                 display();
                                 break;
                         case 2: enQueueFront(value);
                                 display();
                                 break;
                         case 3: value = deQueueFront();
                                 printf("\nThe value deleted is %d",value);
                                 display();
                                 break;
                         case 4: display();
                                 break;
                         default:printf("Wrong choice");
                       }
                       printf("\nDo you want to perform another operation (Y/N): ");
                       ch=getch();
                    } while(ch=='y'||ch=='Y');
                    getch();
                    break ;
            }
            printf("\nDo you want to continue(y/n):");
            ch=getch();
      }while(ch=='y'||ch=='Y');
}

void enQueueRear(int value)
{   
     char ch;
     if(front == SIZE/2)
      {
            printf("\nQueue is full!!! Insertion is not possible!!! ");
            return;
      }
      do
      {
            printf("\nEnter the value to be inserted:");
            scanf("%d",&value);
            queue[front] = value;
            front++;
            printf("Do you want to continue insertion Y/N");
            ch=getch();
      }while(ch=='y');
}

void enQueueFront(int value)
{   
     char ch;
     if(front==SIZE/2)
      {
            printf("\nQueue is full!!! Insertion is not possible!!!");
            return;
      }
      do
      {
            printf("\nEnter the value to be inserted:");
            scanf("%d",&value);
            rear--;
            queue[rear] = value;
            printf("Do you want to continue insertion Y/N");
            ch = getch();
      }
      while(ch == 'y');
}
int deQueueRear()
{
     int deleted;
     if(front == rear)
     {
            printf("\nQueue is Empty!!! Deletion is not possible!!!");
            return 0;
     }
     front--;
     deleted = queue[front+1];
     return deleted;
}
int deQueueFront()
{
     int deleted;
     if(front == rear)
     {
            printf("\nQueue is Empty!!! Deletion is not possible!!!");
            return 0;
     }
     rear++;
     deleted = queue[rear-1];
     return deleted;
}

void display()
{
     int i;
     if(front == rear)
        printf("\nQueue is Empty!!! Deletion is not possible!!!");
     else{
        printf("\nThe Queue elements are:");
        for(i=rear; i < front; i++)
        {
           printf("%d\t ",queue[i]);
        }
     }
}

Output