Double Ended Queue ( DEQUE)


 

  It is a homogeneous list of elements in which insertion and deletion operations are performed from both the ends i.e, we can insert elements from the rear end or from the front ends. Hence, it is called double-ended queue. It is commonly referred to as deque.

There are two types of deques. These two types are due to the restrictions put to preform either the insertions or deletions only at the end. They are :

1) Input Restricted Deque
2) Output Restricted Deque

Four Operations :

=> Insertion of an element at the REAR end of the queue
=> Deletion of an element from the FRONT end of the queue
=> Insertion of an element at the FRONT end of the queue
=> Deletion of an element from the REAR end of the queue
For an input-restricted deque only the operations 1,2,3 & 4 are valid. And for an output-restricated deque only the operations specified in 1,2,3 are valid.

a) Insertion of an element at the REAR end of the queue

void dqinsert_rear(int q[10],int front,int rear,int item,int MAXSIZE)
{
if(rear == (MAXSIZE-1))
{
printf(” QUEUE is full “);
return;
}
rear=rear+1;
q[rear]=item;
}
b) Deletions of an element from the FRONT end of the queue

void dqdelete_front(int q[10],int front,int rear,int item)
{
if(front == rear)
{
printf(” QUEUE is empty “);
return;
}

front=front+1;
item=q[item];
}

3) Insertion of an element at the FRONT end of the queue

void dqinsert_front(int q[10], int front, int rear, int item)
{
if(front == 0)
{
printf(” QUEUE is full”);
return;
}
front=front-1;
q[front]=item;

}

d) Deletion of an element from the REAR end of the queue
void dqdelete_rear( int q[10], int front, int rear, int item)
{
if(front == rear)
{
printf(” QUEUE is empty “);
return;
}

rear=rear-1;
item=q[item];

}

e) Function to display the contents (status) of a QUEUE

void dq_display(int q[10], int front, int rear)
{
if(front <= rear)
{
printf(” Status of the Queue \n”);
for(i = front; i<=rear; i++)
printf(“%d”,dq[i]);

}
else
printf(” QUEUE is empty “);

}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s