Question

I need solution of this homework

Question: Queues, Deques and Priority Queues. Enter the necessary code

Answer 1

Queue:

A queue is an abstract data structure that contains a collection of elements.

Queue implements the First In First Out mechanism i.e. the element that is inserted first is also deleted first. In other words, the least recently added element is removed first in a queue.

This is an empty queue and thus we have rear and empty set to -1.

front rear

we add 1 to the queue and as a result, the rear pointer moves ahead by one location.

1

2

front rear

we add element 2 to the queue by moving the rear pointer ahead by another increment.

1

2

3

front rear   

code:   

#include <iostream>
#include<conio.h>
#include<stdlib.h>
#define MAX_SIZE 100

using namespace std;

int main()
{
int item, choice, i;
int arr_queue[MAX_SIZE];
int rear = 0;
int front = 0;
int exit = 1;

cout << "\n Simple Queue Example ";
do {
cout << "\n\n Queue Main Menu";

cout<<"\n1. Insert";
cout<<"\n2. Remove ";
cout<<"\n3. Display ";
cout<<"\n4. Others to exit ";
cout << "\n Enter Your Choice : ";
cin>>choice;
switch (choice) {
case 1:
if (rear == MAX_SIZE)
cout << "\n## Queue Reached Max!!";
else {
cout << "\nEnter The Value to be Insert : ";
cin>>item;
cout << "\n## Position : " << rear + 1 << " , Insert Value : " << item;
arr_queue[rear++] = item;
}
break;
case 2:
if (front == rear)
cout << "\n## Queue is Empty!";
else {
cout << "\n## Position : " << front << " , Remove Value :" << arr_queue[front];
front++;
}
break;
case 3:
cout << "\n## Queue Size : " << (rear - front);
for (i = front; i < rear; i++)
cout << "\n## Position : " << i << " , Value : " << arr_queue[i];
break;
default:
exit = 0;
break;
}
} while (exit);

return 0;
}

Dequeue

Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.

Some basic operations of dequeue are −

• insert_at_beg():- Inserts an item at the front of Dequeue.
• insert_at_end():- Inserts an item at the rear of Dequeue.
• delete_fr_beg():- Deletes an item from front of Dequeue.
• delete_fr_rear():- Deletes an item from rear of Dequeue.

They are similar to vectors, but are more efficient in case of insertion and deletion of elements.

Not like vectors, contiguous storage allocation may not be guaranteed.
Double Ended Queues are basically an implementation of the data structure double ended queue. A queue data structure allows insertion only at the end and deletion from the front. This is like a queue in real life, wherein people are removed from the front and added at the back.

Double ended queues are a special case of queues where insertion and deletion operations are possible at both the ends.

code:

#include<iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
deque<int> d;
deque<int>::iterator it;
int c, item;
while (1)
{
cout<<" 1.Size of the Deque"<<endl;
cout<<" 2.Insert Element at the End"<<endl;
cout<<" 3.Insert Element at the Front"<<endl;
cout<<" 4.Delete Element at the End"<<endl;
cout<<" 5.Delete Element at the Front"<<endl;
cout<<" 6.Front Element at Deque"<<endl;
cout<<" 7.Last Element at Deque"<<endl;
cout<<" 8.Display Deque"<<endl;
cout<<" 9.Exit"<<endl;
cout<<" Enter your Choice: ";
cin>>c;
switch(c)
{
case 1:
cout<<"Size of the Deque: "<<d.size()<<endl;
break;
case 2:
cout<<"Enter value to be inserted at the end of queue : "<<endl;
cin>>item;
d.push_back(item);
break;
case 3:
cout<<"Enter value to be inserted at the front of queue : "<<endl;
cin>>item;
d.push_front(item);
break;
case 4:
item = d.back();
d.pop_back();
cout<<"Element "<<item<<" deleted"<<endl;
break;
case 5:
item = d.front();
d.pop_front();
cout<<"Element "<<item<<" deleted"<<endl;
break;
case 6:
cout<<"Front Element of the Deque is: "<<endl;
cout<<d.front()<<endl;
break;
case 7:
cout<<"Back Element of the Deque is: "<<endl;
cout<<d.back()<<endl;
break;
case 8:
cout<<"Elements of Deque is : ";
for (it = d.begin(); it != d.end(); it++)
cout<<*it<<" ";
cout<<endl;
break;
case 9:
exit(1);
break;
default:
cout<<"You Enter Wrong Choice"<<endl;
}
}
return 0;
}

Priority Queues:

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority.

If elements with the same priority occur, they are served according to their order in the queue.

Generally, the value of the element itself is considered for assigning the priority.

example, The element with the highest value is considered as the highest priority element. However, in other cases, we can assume the element with the lowest value as the highest priority element. In other cases, we can set priorities according to our needs.

code

#include <iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int> p;
p.push(11);
p.push(33);
p.push(22);
p.push(202);
p.push(29);
cout<<"Number of elements available in 'priority queue' :"<<p.size()<<endl;
while(!p.empty())
{
std::cout << p.top() << std::endl;
p.pop();
}
return 0;
}