Double Ended Queue (DeQueue) Tutorial

What is Double Ended Queue (DeQueue)?

DeQueue stands for Double Ended Queue.
It is just like a queue but does not support FIFO structure.
Insertion and deletion can be done from both side( FRONT & REAR).

The Operations in DeQueue are

Initialize –same as circular queue.
Insertion at rear – same as circular queue.
Deletion from front – same as circular queue.
Insertion at from
Deletion from rear.
Full status check – same a circular queue.
Empty status check – same as circular queue.

Note:Algorithm INSERT-AT-FRONT and DELETE-FROM-REAR are new in DeQueue and other are same as circular queue.

Algorithms

INSERT-AT-FRONT (DEQUEUE, FRONT,REAR,MAX,COUNT,ITEM)
This algorithm is used to insert item at front, 
usually insertion in queue is  done from rear but 
in dequeue we can insert item from front also. 

1.	If ( COUNT = MAX ) then
    a.	Print  “DeQueue Overflow”;
    b.	Return;
2.	Otherwise
    a.	If( FRONT = 1 ) then
        i.	FRONT  := MAX;
    b.	Otherwise
        i.	FRONT := FRONT – 1;
    c.	DEQUEUE(FRONT) := ITEM;
    d.	COUNT : = COUNT + 1;
3.	Return;

DELETE-FROM-REAR(DEQUEUE,FRONT,REAR,COUNT,ITEM)
This algorithm is used to delete item from rear, 
usually deletion in queue is done from front but 
in dequeue we can delete item from rear also.

1.	If(COUNT = 0 ) then
    a.	Print “DeQueue underflow”;
    b.	Return;
2.	Otherwise
    a.	ITEM := DEQUEUE(REAR);
    b.	If ( REAR = 1) then
        i.	REAR := MAX;
    c.	Otherwise
        i.	REAR := REAR -1;
    d.	COUNT := COUNT – 1;
3.	Return;

#define MAX 5

typedef struct DQ
{
    int     front	;
    int     rear	;
    int     count	;
    int     ele[MAX];
};

#define MAX 5

//Declaration of DQueue
class DQueue
{
	private:
		int front	;
		int rear	;
		int count	;
		int ele[MAX]	;

	public:
		DQueue();
		int  isFull();
		int  isEmpty();
		void insertDQueueAtRear(int item);
		int  deleteDQueueAtFont(int *item);
		void insertDQueueAtFront(int item);
		int  deleteDQueueAtRear(int *item);
};

Types of DeQueue

Input Restricted DeQueue
Output Restricted DeQueue

In Input Restricted DeQueue , insertion can be done from REAR only, but deletion can be done from both FRONT and REAR.

In Output Restricted DeQueue, deletion can be done from FRONT only, but insertion can be done from both FRONT and REAR.

DeQueue Implementation with all above Queue operations

Using C
Using C++


#include <stdio.h>
#define MAX 5

//Declaration of Dequeue.
typedef struct
{
	int front	;
	int rear	;
	int count	;
	int ele[MAX]	;
}DQueue;

//Initailization of Dequeue.
void initDQueue(DQueue * q)
{
	q->front =  0;
	q->rear  = -1;
	q->count =  0;
}

//Check Dequeue is full or not
int isFull(DQueue * q)
{
	int full=0;
	
	if(q->count == MAX)
		full = 1;	

	return full;
}

//Check Dequeue is empty or not
int isEmpty(DQueue * q)
{
	int empty=0;
	
	if(q->count == 0)
		empty = 1;	

	return empty;
}

//To insert item into Dequeue at rear.
void insertDQueueAtRear(DQueue * q, int item)
{
	if( isFull(q) )
	{
		printf("\nQueue Overflow");
		return;
	}
	
	q->rear = (q->rear+1)%MAX;
	q->ele[q->rear] = item;
	
	q->count++;
 
	printf("\nAfter insert At Rear FRONT : %d, REAR : %d",q->front,q->rear);
	printf("\nInserted item : %d\n",item);
}

//To delete item from Dequeue at front.
int deleteDQueueAtFront(DQueue * q, int *item)
{
	if( isEmpty(q) )
	{
		printf("\nQueue Underflow");
		return -1;
	}

	*item    = q->ele[q->front];

	q->front = (q->front+1)%MAX;
	
	q->count--;

	printf("\nAfter Delete At Front FRONT : %d, REAR : %d",q->front,q->rear);
	return 0;
}

//To insert item into Dequeue at front.
void insertDQueueAtFront(DQueue * q, int item)
{
	if( isFull(q) )
	{
		printf("\nQueue Overflow");
		return;
	}
	
	if ( q->front == 0)
		q->front = MAX - 1;
	else
		q->front = q->front - 1;
	q->ele[q->front] = item;
	
	q->count++;
	printf("\nAfter Insert At Front FRONT : %d, REAR : %d",q->front,q->rear);
	printf("\nInserted item : %d\n",item);
}

//To delete item from Dequeue at rear.
int deleteDQueueAtRear(DQueue * q, int *item)
{
	if( isEmpty(q) )
	{
		printf("\nQueue Underflow");
		return -1;
	}

	*item = q->ele[q->rear];

	if(q->rear == 0)
		q->rear = MAX - 1;
	else
		q->rear = q->rear - 1;

	printf("\nAfterDeleteAtRear FRONT : %d, REAR : %d",q->front,q->rear);
	q->count--;	
	return 0;
}

int main()
{
	int item=0;
	DQueue q;

	initDQueue(&q);

	insertDQueueAtRear(&q, 10);	
	insertDQueueAtRear(&q, 20);
	insertDQueueAtRear(&q, 30);
	insertDQueueAtFront(&q, 40);
	insertDQueueAtFront(&q, 50);
	insertDQueueAtFront(&q, 60);

	if ( deleteDQueueAtFront( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	
	if ( deleteDQueueAtFront( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	
	if ( deleteDQueueAtFront( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	
	if ( deleteDQueueAtRear( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	
	if ( deleteDQueueAtRear( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	
	
	if ( deleteDQueueAtRear( &q, &item ) == 0 )
		printf("\nDeleted item is : %d\n",item);

	printf("\n");
	return 0;	
}

    After insertAtRear FRONT : 0, REAR : 0
    Inserted item : 10

    After insertAtRear FRONT : 0, REAR : 1
    Inserted item : 20

    After insertAtRear FRONT : 0, REAR : 2
    Inserted item : 30

    AfterInsertAtFront FRONT : 4, REAR : 2
    Inserted item : 40

    AfterInsertAtFront FRONT : 3, REAR : 2
    Inserted item : 50

    Queue Overflow
    AfterDeleteAtFront FRONT : 4, REAR : 2
    Deleted item is : 50

    AfterDeleteAtFront FRONT : 0, REAR : 2
    Deleted item is : 40

    AfterDeleteAtFront FRONT : 1, REAR : 2
    Deleted item is : 10

    AfterDeleteAtRear FRONT : 1, REAR : 1
    Deleted item is : 30

    AfterDeleteAtRear FRONT : 1, REAR : 0
    Deleted item is : 20

    Queue Underflow


#include <iostream>

using namespace std;
#define MAX 5

//Declaration of DQueue
class DQueue
{
	private:
		int front	;
		int rear	;
		int count	;
		int ele[MAX]	;

	public:
		DQueue();
		int  isFull();
		int  isEmpty();
		void insertDQueueAtRear(int item);
		int  deleteDQueueAtFont(int *item);
		void insertDQueueAtFront(int item);
		int  deleteDQueueAtRear(int *item);
};

//Initalize DQueue
DQueue:: DQueue()
{
	front =  0;
	rear  = -1;
	count =  0;	
}

//To check DQueue is full or not
int DQueue:: isFull()
{
	int full=0;

	if( count == MAX )
		full = 1;

	return full;	
}

//To check DQueue is empty or not
int DQueue:: isEmpty()
{
	int empty=0;

	if( count == 0 )
		empty = 1;

	return empty;	
}

//Insert item into DQueue
void DQueue:: insertDQueueAtRear(int item)
{
	if( isFull() )
	{
		cout<<"\nQueue Overflow";
		return;
	}

	rear= (rear+1) % MAX;

	ele[rear] = item;
	count++;
	
	cout<<"\nAfterInsert At Rear FRONT : "<< front<<", REAR : "<< rear;
	cout<<"\nInserted item : "<< item << endl;
}

//Delete item from DQueue
int DQueue:: deleteDQueueAtFont(int *item)
{
	if( isEmpty() )
	{
		cout<<"\nQueue Underflow";
		return -1;
	}
	*item = ele[front];
	front = (front+1) % MAX;
	
	cout<<"\nAfter Delete At Front FRONT : "<< front<<", REAR : "<< rear;
	count--;
	return 0;
}

//To insert item into Dequeue at front.
void DQueue:: insertDQueueAtFront(int item)
{
	if( isFull() )
	{
		cout<<"\nQueue Overflow";
		return;
	}
	
	if ( front == 0)
		front = MAX - 1;
	else
		front = front - 1;
	ele[front] = item;
	
	count++;
	cout<<"\nAfter Insert At Front FRONT :"<< front<<", REAR : "<< rear;
	cout<<"\nInserted item : "<< item<< endl;
}

//To delete item from Dequeue at rear.
int DQueue:: deleteDQueueAtRear(int *item)
{
	if( isEmpty() )
	{
		cout<<"\nQueue Underflow";
		return -1;
	}

	*item = ele[rear];

	if(rear == 0)
		rear = MAX - 1;
	else
		rear = rear - 1;

	cout<<"\nAfterDeleteAtRear FRONT : "<< front<<", REAR : "<< rear;
	count--;	
	return 0;
}

int main()
{
	int  item;
	DQueue q = DQueue();

	q.insertDQueueAtRear(10);
	q.insertDQueueAtRear(20);
	q.insertDQueueAtRear(30);
	q.insertDQueueAtFront(40);
	q.insertDQueueAtFront(50);
	q.insertDQueueAtFront(60);

	if( q.deleteDQueueAtFont(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}

	if( q.deleteDQueueAtFont(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}

	if( q.deleteDQueueAtFont(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}

	if( q.deleteDQueueAtRear(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}

	if( q.deleteDQueueAtRear(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}
	
	if( q.deleteDQueueAtRear(&item) == 0 )
	{
		cout<<"\nDeleted item:"<< item<< endl;
	}


	cout<<"\n";
	return 0;
}

    AfterInsert At Rear FRONT : 0, REAR : 0
    Inserted item : 10

    AfterInsert At Rear FRONT : 0, REAR : 1
    Inserted item : 20

    AfterInsert At Rear FRONT : 0, REAR : 2
    Inserted item : 30

    After Insert At Front FRONT :4, REAR : 2
    Inserted item : 40

    After Insert At Front FRONT :3, REAR : 2
    Inserted item : 50

    Queue Overflow
    After Delete At Front FRONT : 4, REAR : 2
    Deleted item:50

    After Delete At Front FRONT : 0, REAR : 2
    Deleted item:40

    After Delete At Front FRONT : 1, REAR : 2
    Deleted item:10

    AfterDeleteAtRear FRONT : 1, REAR : 1
    Deleted item:30

    AfterDeleteAtRear FRONT : 1, REAR : 0
    Deleted item:20

    Queue Underflow