Double Ended Queue
Double Ended queue is also one of the forms of queue with characteristic that, in deque we can add or remove an element from either end. Double ended Queue abbreviated as deque, (pronounced as like “cheque”).
Deque, double ended queue is an abstract data type in which elements can be added or removed either from front or back. Generally Front is considered as head end and Back is considered as Tail end.
In computer memory, deque data structure is implement as either through a circular array or by doubly linked list. A deque is maintained with two pointers, LEFT and RIGHT, that point to its two ends. The components of a deque are located from its LEFT end to its RIGHT end. In a deque of N elements, the first element of the deque is followed by the Nth element.
In Deque data structure, you will notice that it has combined characteristics of Stack and Queue data structure.
And also, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you, means depends on programmer that how he/she is performing an operation of addition and removal on such data structure.
Basic Operations on DEQUE
The fundamental or basic operations that can be performed on deque are as follows.
- insert front: Add or insert an item at the top of the deque.
void Dequeue :: push_front(int key)
{
if(full())
{
cout << “OVERFLOW\n”;
}
else
{
//If queue is empty
if(front == -1)
front = rear = 0;
//If front points to the first position element
else if(front == 0)
front = SIZE-1;
else
–front;
arr[front] = key;
}
}
- insertLast: Insert or add something last by using the insertLast command.
void Dequeue :: push_back(int key)
{
if(full())
{
cout << “OVERFLOW\n”;
}
else
{
//If queue is empty
if(front == -1)
front = rear = 0;
//If rear points to the last element
else if(rear == SIZE-1)
rear = 0;
else
++rear;
arr[rear] = key;
}
}
- deleteFront: The item has to be taken out of the front of the queue or deleted.
void Dequeue :: pop_front()
{
if(empty())
{
cout << “UNDERFLOW\n”;
}
else
{
//If only one element is present
if(front == rear)
front = rear = -1;
//If front points to the last element
else if(front == SIZE-1)
front = 0;
else
++front;
}
}
- Delete last: The item needs to be removed from the queue or put at the end.
void Dequeue :: pop_back()
{
if(empty())
{
cout << “UNDERFLOW\n”;
}
else
{
//If only one element is present
if(front == rear)
front = rear = -1;
//If rear points to the first position element
else if(rear == 0)
rear = SIZE-1;
else
–rear;
}
}
- getFront: displays the deque’s top-level item.
- getLast : getLast retrieves the very last item in the queue.
- isEmpty : check whether the deque is empty with isEmpty.
bool Dequeue :: empty()
{
if(front == -1)
return true;
else
return false;
}
- isFull: checks to see if the deque is full.
bool Dequeue :: full()
{
if((front == 0 && rear == SIZE-1) ||
(front == rear + 1))
return true;
else
return false;
}
Algorithm for deleting an element from front and end.
Deleting element from front:
Step-1
if rear =-1 that means Queue is underflow
Step-2
else perform deletion
No. to be deleted =q[front]
Print(no. To be deleted)
Set front and rear
If(front=rear=0) then set front =0 and rear =-1
Else front+=1
Deleting element from end:
Step-1
If rear =-1, then there is no element to be deleted
Else
Step-2
No. To be deleted=q[rear]
Print(no. To be deleted)
If(front =rear=0) then set front =0 and rear =-1
Else rear -=1
Deque also classified as
-
- Input Restricted Double Ended Queue
- Output Restricted Double Ended Queue
Input Restricted Double Ended Queue
In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends.
Output Restricted Double Ended Queue
In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.
Application of Double Ended Queue:
- A web browser’s browsing history can be saved via the deque.
- The list of undo operations for a software program is usually stored in a deque.
- A deque can be utilized, for example, in the A-Steal job scheduling method.
- Task scheduling for several processors is put into practice with this data structure.
Consider example of moneyControl App, it will show the stocks you last visited, it will remove the stocks after some time and will add the latest ones.
