Dequeue

Dequeue

• Definition: Doubly ended queue is a queue in which insertion and deletion both can be done by both the ends.

• As we know, normally we insert the elements by rear end and delete the elements from front end. Let us say we have inserted the elements 10, 20, 30 by rear end.

• Now if we wish to insert any element from front end then first we have to shift all the elements to the right.

For example if we want to insert 40 by front end then, the deque will be

We can place -1 for the element which has to be deleted.

Let us see the implementation of deque using arrays

Ex. 3.7.1: Implementation of deque using arrays.

/******************************************************

Program To implement Doubly ended queue using arrays

*******************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 5

/*Data structure for deque*/

struct queue {

int que[size];

int front,rear;

}Q;

int Qfull()

{

if(Q.rear==size-1)

return 1;

else

return 0;

}

int Qempty()

{

if((Q.front>Q.rear) || (Q.front ==-1&&Q.rear==-1))

return 1;

else

return 0;

}

int insert_rear(int item)

{

if(Q.front=-1&&Q.rear==-1)

Q.front++;

Q.que[++Q.rear]=item;

return Q.rear;

}

int delete_front()

{

int item;

if(Q.front==-1)

Q.front++;

item=Q.que[Q.front];

Q.que [Q.front]=-1;

Q.front++;

return item;

}

int insert_front(int item)

{

int i,j;

if(Q.front==-1)

Q.front++;

j=Q.rear;

while(j>=Q.front)

{

Q.quelj+1]=Q.que[j];

j- -;

}

Q.rear++;

Q.que[Q.front]=item;

return Q.front;

}

int delete_rear()

{

int item;

item=Q.que [Q.rear];

Q.que[Q.rear] =-1;/*logical deletion*/

Q.rear--;

return item;

}

void display()

{

int i;

printf("\n Straight Queue is:");

for(i=Q.front;i<=Q.rear;i++)

printf("%d",Q.que[i]);

}

void main()

{

int choice,i,item;

char ans;

ans='y';

Q.front=-1;

Q.rear=-1;

for(i=0;i<size;i++)

Q.que[i]=-1;

clrscr();

 printf("\n\t\t Program For doubly ended queue using arrays");

do

{

printf("\n1.insert by rear\n2.delete by front\n3.insert by front\n4.delete by rear");

printf("\n5.display\n6.exit");

printf("\n Enter Your choice");

scanf("%d", &choice);

switch(choice)

{

case 1:if(Qfull())

printf("\n Doubly ended Queue is full");

else

{

printf("\n Enter The item to be inserted");

scanf("%d",&item);

Q.rear-insert_rear(item);

}

break;

case 2:if(Qempty())

printf("\n Doubly ended Queue is Empty");

else

{

item=delete_front();

printf("\n The item deleted from queue is %d",item);

}

break;

case 3:if(Qfull())

printf("\n Doubly ended Queue is full");

else

{

printf("\n Enter The item to be inserted");

scanf("%d", &item);

Q.front insert_front(item);

}

break;

case 4:if(Qempty())

printf("\n Doubly ended Queue is Empty");

else

{

item=delete_rear();

printf("\n The item deleted from queue is %d",item);

}

break;

case 5:display();

break;

case 6:exit(0);

}

printf("\n Do You Want To Continue?");

ans=getch();

}while(ans ==`y`|| ans == `Y`);

getch();

}

Output

Program For doubly ended queue using arrays

1. insert by rear

2. delete by front

3. insert by front

4. delete by rear

5. display

6. exit

Enter Your choice1

Enter The item to be inserted10

Do You Want To Continue?

1. insert by rear

2. delete by front

3. insert by front

4. delete by rear

5. display

6. exit

Enter Your choice 3

Enter The item to be inserted 20.

Do You Want To Continue?

1. insert by rear

2. delete by front

3. insert by front

4. delete by rear

5. display

6. exit

Enter Your choice 5

 Straight Queue is: 20 10

Do You Want To Continue?

1. insert by rear

2. delete by front

3. insert by front

4. delete by rear

5. display

6. exit

Enter Your choice4

The item deleted from queue is 10

Do You Want To Continue?

Difference between Doubly End Queue and Circular Queues

Review Questions

1. What is a circular queue and double-ended queue? Give suitable examples to differentiate them.

2. Differentiate between double ended queue and Circular queue.

3. What is a DeQueue? Explain its operation with example.