Double Ended Queue or Deque : Insertion/ Deletion

Hi All,

one more post coming up about the double ended queue which is also known as deque. A deque is a special type of data-structure in which insertion and deletion can be done at both end. So there are 5 operations for deque.

1. Insert element at front end.
2. Insert element at rear end.
3. Delete element from front end.
4. Delete element from rear end.
5. Display the elements of the deque.

So let me introduce the code for each of these function one by one. Here I will be using f for front index and r for rear index.

1. Insert element at front end.

Here there are 3 cases which needs to be taken care of

case 1. When queue is empty, so here is the code :

if(f == 0 && r == -1)

{

Queue[++r] = val; //value which needs to be added.

return;

}




case 2. when queue have element, but some elements from front has been deleted

if(f != 0)

{

Queue[--f] = val;

return;

}




case 3: when queue is full

if(f ==0 && r != -1)

{

printf("No Space left");

return;

}




2. Insert at rear end

Here only 2 cases needs to take care

case 1. if queue is full

if(r == Queue_SIZE - 1)

{

printf("No Space left");

return;

}




case 2. otherwise

else

{

Queue[++r] = val;

}




3. Delete from front end

Here there will be 3 cases.

case 1 : When front index has larger index than rear, it means there is no elements

if(f>r)

{

printf("No element left to delete");

return;

}




case 2. When there is only one element in the queue

if(f==r)

{

printf("deleted element is = %d",Queue[r]);

f = 0;

r =-1;

return;

}

case 3. otherwise

else

{

printf("deleted element is = %d",Queue[f++]);

}

4. Delete from rear end

Here there will be 2 cases.

case 1. when there is no element

if(f>r)

{

printf("No element to delete");

return;

}

case 2. otherwise

else

{

printf("Deleted element is = %d\n",Queue[r--]);

// now only one element was there in queue then adjust rear and front index

if(f>r)

{

f = 0;

r = -1;

}

5. Display the element

int i;

for(i = f; i

{

printf("%d ",Queue[i]);

}

Hope it will help you to understand the complete logic.