support@assignmenthelp.net
+1-617-874-1011 (US)
+44-117-230-1145 (UK)
+61-7-5641-0117 (AU)
+44-117-230-1145 (UK)
+61-7-5641-0117 (AU)
Deques are one of the many standard template library (STL) containers available in C++. Similar to queue, a Deque known as a double-ended queue, is an ordered collection of items in Data Structures. It is also often called a head tail linked list.
Figure: Representing Insertion and deletion in a Deque.
What makes a deque stand out is the unrestrictive nature of adding and removing items i.e. it allows fast insertion and deletion of elements at both ends of the queue.
This algorithm is used for implementing the task scheduling for multiple processors often called multiprocessor scheduling.
The processor takes the first element from the deque.
A thread can be accessed from another processor, when one of the processor completes execution of its own threads.
The last element from the deque of another processor is accessed by one of the processor which then executes it.
The Deque can be implemented to achieve the functionality of Undo Redo operations in software application.
A palindrome is a word or sequence which reads the same from any direction i.e. either backward or forward.
Reviver, Radar, Level are few examples of palindrome.
Figure: Showing palindrome checker using deque
In Input-restricted deque deletion can be performed at both the end of the deque, but insertion can be performed at one end only.
Figure: Insertion and deletion in input-restricted deque
In Output-restricted deque insertion can be performed at both the end of the deque, but deletion can be performed at one end only.
Figure: Insertion and deletion in input-restricted deque
The C++ STL i.e. Standard Template Library is a powerful set of C++ template classes to provide general purpose templates, classes and functions that implement popular algorithms and data structures such as vectors, queue, list and stack one of which is Deque container.
To begin with deque in our programming, we must include its header < deque>. #include < deque> using namespace std;
Let us create few deque objects for understanding deque creation in a better way.
Creating an empty deque:
Pseudo code: deque< double> deqA;
Creating a deque with 10 empty elements
Pseudo code: deque< double> deqB(10);
Creating a deque with 10 elements, each element having value equals to 2.
Pseudo code: deque< double> deqC(10, 2);
Creating a deque based on an array
Pseudo code:
int array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 5.55, 8,99};
deque deqC(array, array + 10);
Using copy constructor to copy the contents of deque ‘deqC’ into deque ‘deqCcopy’
Pseudo code: dequedeqCcopy(deqC);
To display or print the elements of a deque, we can use the [] operator, the at() member function, and iterators.
Let us create the display() function for printing a deque:
Pseudo code:
void display(deque< double> deqA, char * name)
{
deque< double>::iterator it;
cout << Printing << ": ";
for(it = deqA.begin(); it != deqA.end(); ++it)
cout << *it << " ";
cout << endl;
}
Creating an array to print a deque in reverse order:
Pseudo code:
double array[10] = {2.33,5.43, 3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
deque< double> deq(array, array + 10);
print(deq, "deq");
// Displaying elements of a deque in reverse order
cout << "deq in reverse order: ";
deque< double>::reverse_iterator rit;
for(rit = deq.rbegin(); rit != deq.rend(); ++rit)
cout << *rit << " ";
To insert elements into a deque, we can use the functions push_back(), push_front(), and insert().
Pseudo code: deque< double> deq; deque< double>::iterator it; // add an element at the end of the deque deq.push_back(6.67);
Pseudo code: deq.push_front(4.56); print(deq, "deq");
Pseudo code: it = deq.begin(); ++it; deq.insert(it, 40.04); print(deq, "deq");
To resize a deque, we can use the resize() function. Deque does not have the capacity()and reserve() member functions, unlike vectors.
Pseudo code:
deque< double> deq;
deq.push_back(3.45);
deq.push_back(19.26);
deq.push_back(3.517);
cout << "deq size is " << deq.size() << endl;
print(deq, "deq");
// case when new size <= size of vector
deq.resize(1);
cout << "deq size is " << deq.size() << endl;
print(deq, "deq");
// case when new size > size of vector
deq.resize(5);
cout << "deq size is " << deq.size() << endl;
print(deq, "deq");
To remove elements from a deque, we can use the pop_back(), pop_front(), and erase() functions.
Pseudo code:
double array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 10.25, 89.76};
deque deq(array, array + 10);
deque::iterator it;
print(deq, "deq");
// remove the last element of the deque
deq.pop_back();
print(deq, "deq");
Pseudo code: deq.pop_front(); print(deq, "deq");
Pseudo code: it = deq.begin(); it += 2; deq.erase(it); print(deq, "deq");
Psedo code: deq.clear(); if(deq.empty()) cout << "deq is empty" << endl;
Performing insert, delete and display operations on Dequeue in C++.
#include< iostream>
#include< conio.h>
#include< stdlib.h>
using namespace std;
class node
{
public:
int data;
class node *next;
class node *prev;
};
class dqueue: public node
{
node *head,*tail;
int top1,top2;
public:
dqueue()
{
top1=0;
top2=0;
head=NULL;
tail=NULL;
}
void push(int x){
node *temp;
int ch;
if(top1+top2 >=5)
{
cout <<"dqueue overflow";
return ;
}
if( top1+top2 == 0)
{
head = new node;
head->data=x;
head->next=NULL;
head->prev=NULL;
tail=head;
top1++;
}
else
{
cout <<" Add element 1.FIRST 2.LAST\n enter ur choice:";
cin >> ch;
if(ch==1)
{
top1++;
temp=new node;
temp->data=x;
temp->next=head;
temp->prev=NULL;
head->prev=temp;
head=temp;
}
else
{
top2++;
temp=new node;
temp->data=x;
temp->next=NULL;
temp->prev=tail;
tail->next=temp;
tail=temp;
}
}
}
void pop()
{
int ch;
cout <<"Delete 1.First Node 2.Last Node\n Enter ur choice:";
cin >>ch;
if(top1 + top2 <=0)
{
cout <<"\nDqueue under flow";
return;
}
if(ch==1)
{
head=head->next;
head->prev=NULL;
top1--;
}
else
{
top2--;
tail=tail->prev;
tail->next=NULL;
}
}
void display()
{
int ch;
node *temp;
cout <<"display from 1.Staring 2.Ending\n Enter ur choice";
cin >>ch;
if(top1+top2 <=0)
{
cout <<"under flow";
return ;
}
if (ch==1)
{
temp=head;
while(temp!=NULL)
{
cout << temp->data <<" ";
temp=temp->next;
}
}
else
{
temp=tail;
while( temp!=NULL)
{
cout << temp->data << " ";
temp=temp->prev;
}
}
}
};
main()
{
dqueue d1;
int ch;
while (1){
cout <<"1.INSERT 2.DELETE 3.DISPLAU 4.EXIT\n Enter ur choice:";
cin >>ch;
switch(ch)
{
case 1: cout <<"enter element";
cin >> ch;
d1.push(ch); break;
case 2: d1.pop(); break;
case 3: d1.display(); break;
case 4: exit(1);
} }}
Performing insert, delete and display operations on Dequeue in JAVA.
/*
Java program to implement dequeue.
*/
import java.io.*;
class dequeue
{
int DQ[] = new int[100];
int n;
int front, rear;
static BufferedReader br = new BufferedReader(newInputStreamReader(System.in));
public dequeue(int nn)
{
n = nn;
front = rear = 0;
}
public void pushrear(int v)
{
if((rear+1)< n)
{
rear++;
DQ[rear] = v;
}
else
System.out.println("Overflow from rear !");
}
public void pushfront(int v)
{
if(front>=0)
{
DQ[front] = v;
front--;
}
else
System.out.println("Overflow from front !");
}
public int popfront()
{
int v;
if(front!=rear)
{
front++;
v = DQ[front];
return v;
}
else
return -9999;
}
public int poprear()
{
int v;
if(front!=rear)
{
v = DQ[rear];
rear--;
return v;
}
else
return -9999;
}
public void display()
{
if(front!=rear)
{
for(int i=front+1;i<=rear;i++)
System.out.println(DQ[i]);
}
else
System.out.println("No element in queue !");
}
public static void main() throws IOException
{
System.out.print("Enter the size of the queue : ");
int size = Integer.parseInt(br.readLine());
dequeue call = new dequeue(size);
int choice;
boolean exit = false;
while(!exit)
{
System.out.print("\n1 : Push from Front\n2 : Push from
Rear\n3 : Delete from Front\n4 : Delete from Rear\n5 : Display\n6 :
Exit\n\nYour Choice : ");
choice = Integer.parseInt(br.readLine());
switch(choice)
{
case 1 :
System.out.print("\nEnter number to be added : ");
int num = Integer.parseInt(br.readLine());
call.pushfront(num);
break;
case 2 :
System.out.print("\nEnter number to be added : ");
int num2 = Integer.parseInt(br.readLine());
call.pushrear(num2);
break;
case 3 :
int popped = call.popfront();
if(popped != -9999)
System.out.println("\nDeleted : " +popped);
break;
case 4 :
int popped2 = call.popfront();
if(popped2 != -9999)
System.out.println("\nDeleted : " +popped2);
break;
case 5 :
call.display();
break;
case 6 :
exit = true;
break;
default :
System.out.println("\nWrong Choice !");
break;
}
}
}
}
Performing insert at right hand and left hand, delete at right hand and left hand and display operations on Dequeue in PYTHON.
# importing "collections" for deque operations
import collections
# initializing deque
de = collections.deque([1,2,3])
# using append() to insert element at right end
# inserts 4 at the end of deque
de.append(4)
# printing modified deque
print ("The deque after appending at right is : ")
print (de)
# using appendleft() to insert element at right end
# inserts 6 at the beginning of deque
de.appendleft(6)
# printing modified deque
print ("The deque after appending at left is : ")
print (de)
# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()
# printing modified deque
print ("The deque after deleting from right is : ")
print (de)
# using popleft() to delete element from left end
# deletes 6 from the left end of deque
de.popleft()
# printing modified deque
print ("The deque after deleting from left is : ")
print (de)
Queue is an abstract data structure which keeps an order of elements in it. We can add element to the end of a sequence and remove element from the head of the sequence in a queue. Queue can be referred as FIFO (First in First out). This means retrieving elements from a queue happens in the same order as they were put in it.
Deque or dequeue is double-ended queue. We can add and remove elements to and from both ends of a sequence.
Both Queue and Deque does not specify access to elements between their ends. So, implementation of queue or dequeue may or may not provide operations for accessing elements others than current ends of the sequence. Also Queue and Deque may provide such operations with a very different efficiency.
Vector provides insertion and deletion at middle and end of the list only. Also, it provides good performance while insertion and deletion at end and somewhat poor performance while performing insertion and deletion at middle. In case of performance of addition and deletion at end for vector is better than deque.
Deque provides operations for insertion at front, middle and end. Apart from push_back() and pop_back() APIs like vector, deque also has push_front() and pop_front() API to add and delete elements from front of the list. Both deque and vector provides samekind of performance for insertion & deletion at end and middle. Also, deque provides good performance for insertion and deletion at front also.
One should prefer deque over vector in case of adding or deleting from both the ends like implementing a Queue. The vector should be chosen if insertion or deletions are required mostly in end like implementing a Stack.
A list holds data in blocks of memory which are individually allocated. A List data structure is quick to insert or delete in the beginning of the list, end or in the middle. It contains only sequential iterators and hence random access is not granted.
A deque holds data in blocks of allocated memory. It is quick to insert or delete in the beginning or end, but deletion or insertion in the middle is slow. Unlike vectors it has random access and therefore contains random access iterators.
Deque allocates memory in chunks rather than allocating each time for one node. The standard templates are optimized for speed not size or efficiency.
A list should be used when lot of nodes are present that are processing in a largely sequential manner and vector when the processing is more random in nature. Otherwise, a deque should be preferred.
The time complexity or efficiency of common operations on deques can be summarized as follows:
[1] Sathasivam R , December 11th, 2014. Deque and its Applications. http://www.slideshare.net/sathasivamr1/team-6-42605244
[2] Cristitomi, October 21st, 2007. The complete guide to STL: Part 3 - Deque. https://www.codeproject.com/Articles/20965/The-complete-guide-to-STL-Part-Deque
Assignment Writing Help
Engineering Assignment Services
Do My Assignment Help
Write My Essay Services