Deque Data Structure

Deque Data Structure

Deque data structure is an abstract data type similar to an simple queue, it allows you to insert and delete from both sides means items can be added or deleted from the front or rear end

 

 

Types of Deque

1. Input Restricted Deque
2. Output Restricted Deque

 

 

1. Input Restricted Deque

In input restricted double ended queue, the insertion operation is performed at one end and deletion operation is performed at both the ends

 

 

2. Output Restricted Deque

In output restricted double ended queue, the insertion operation is perormed at both the ends and deletion operation is performed at one end

Operations on Deque

There are four operation performed on deque they are follows

• • Insert at front
  • Delete from end
  • insert at rear
  • delete from rear

 

 

Algorithm for insertion at rear end

Step-1: [Check for overflow]   
        if(rear==MAX)  
            Print("Queue is Overflow”);  
            return;  
Step-2:  [Insert Element]	  
        else  
            rear=rear+1;  
            q[rear]=no;      
        [Set rear and front pointer]                
        if rear=0  
            rear=1;  
        if front=0  
            front=1;  
Step-3: return

 

 

Algorithm for insertion at front end

Step-1 :  [Check for the front position]  
        if(front<=1)  
            Print("Cannot add item at the front”);  
            return;  
Step-2 :  [Insert at front]  
        else  
            front=front-1;  
            q[front]=no;  
Step-3  : Return

 

 

Algorithm for deletion at front end

Step-1 [ Check for front pointer]  
        if front=0  
            print(" Queue is Underflow”);  
            return;  
Step-2 [Perform deletion]          
        else  
            no=q[front];  
            print(“Deleted element is”,no); 
        [Set front and rear pointer]       
        if front=rear  
            front=0;  
            rear=0;  
        else  
            front=front+1;  
Step-3 : Return

 

 

Algorithm for deletion at rear end

Step-1 : [Check for the rear pointer]  
        if rear=0  
            print(“Cannot delete value at rear end”);  
            return;  
Step-2:  [ perform deletion]  
        else  
            no=q[rear];  
            [Check for the front and rear pointer]  
        if front= rear  
            front=0;  
            rear=0;  
        else  
            rear=rear-1;  
            print(“Deleted element is”,no);  
Step-3 : Return

Time Complexity of deque

The time complexity of deque is constant i.e. 0(1)

 

Application of deque

• Pallindrome checker.
• A-steal job scheduling algorithm

 

Also read, Priority Queue Data Structure