Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inserting and deleting at either of the end.
Ans.
There are number of ways of representing dequeue in a computer. We will suppose that dequeue is maintained by a circular array DEQUE with pointer FRONT and REAR, which point to the 2 ends of dequeue. We suppose that the element extend from the left end to the right end in the array. The condition FRONT = NULL will be used to indicate that dequeue is blank.
Algorithm for inserting in dequeue is written below
Step 1: [check overflow condition] If rear ≥ n and front = 0
Output :overflow and return"
Step 2: [check front pointer value] If front > 0
Front = front -1
Else
Return
Step 3: [insert element at the front end] Q[front ] = value
Step 4: [check rear pointer value] If rear < n
Rear = rear +1
Else
Return
Step 5: [insert element at the rear end] Q [rear] = value
Step 6: Return
Deletion Algorithm for dequeue is given below
Step 1: [check for underflow] If front = 0 and rear = 0
Output "underflow" and return
Step 2: [delete element at front end] If front > 0
Value = q [front] Return [value]
Step 3: [check queue for empty]
If front = rear
Front = rear = 0
Else
Front = front +1
Step 4: [delete element at the rear end] If rear > 0
Value = Q [rear] Return (rear)
Step 5: [check queue for empty] If front = rear
Front = rear = 0
Else
Rear = rear - 1
Step 6: Return