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
- Input Restricted Deque
- 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