Priority Queue Exercise
Posted: Sat Dec 15, 2018 7:07 am
I have to do this
Imagine you're writing a little program to categorize bugs in a game and you want to push the bugs into a queue. The bugs will have a char priority(level) of 'A', 'B', or 'C'.
I want you to create a small class (or struct) for the bugs and they only have to have two properties:
A char for the priority with a suggested name of m_cPriority
A string or char* for the description with a suggested name of m_sDesc
You'll be creating a queue of these objects as the nodes and this will be somewhat of a custom priority queue exercise.
For the most part, you're going to change the enQueue method of the BasicQueue to account for the priority of the Bug. For maximum templatability(?), you should have the char priority as the second parameter in the new enQueue in case you want to test the queue with other types. Then you would somehow need to set the priority of the node in the main when enQueue is called.
For example, when enQueueing a Bug node, invoke a GetPriority method for the Bug that returns the char priority and have that function invocation as the second parameter of the enQueue call.
Or, if you want to enQueue a simple type like int, give the simple nodes an arbitrary char priority. They would, of course, not be Bugs but you're still able to use this priority queue for other purposes.
So, in the enQueue, you have to check the priority of the Node and then insert the Node in the queue based on these priorities. 'A' have the highest priority, 'B' second and 'C' third. Nodes of the same priority are pushed to the end of their respective priorities. For example a new 'A' bug, will get pushed to the end of the 'A's already in the queue.
All I want you to alter is the enQueue and add the Bug struct and account for this new priority.
i have this so far basicqueue.h
main.cpp
this is my basicqueue.h
Imagine you're writing a little program to categorize bugs in a game and you want to push the bugs into a queue. The bugs will have a char priority(level) of 'A', 'B', or 'C'.
I want you to create a small class (or struct) for the bugs and they only have to have two properties:
A char for the priority with a suggested name of m_cPriority
A string or char* for the description with a suggested name of m_sDesc
You'll be creating a queue of these objects as the nodes and this will be somewhat of a custom priority queue exercise.
For the most part, you're going to change the enQueue method of the BasicQueue to account for the priority of the Bug. For maximum templatability(?), you should have the char priority as the second parameter in the new enQueue in case you want to test the queue with other types. Then you would somehow need to set the priority of the node in the main when enQueue is called.
For example, when enQueueing a Bug node, invoke a GetPriority method for the Bug that returns the char priority and have that function invocation as the second parameter of the enQueue call.
Or, if you want to enQueue a simple type like int, give the simple nodes an arbitrary char priority. They would, of course, not be Bugs but you're still able to use this priority queue for other purposes.
So, in the enQueue, you have to check the priority of the Node and then insert the Node in the queue based on these priorities. 'A' have the highest priority, 'B' second and 'C' third. Nodes of the same priority are pushed to the end of their respective priorities. For example a new 'A' bug, will get pushed to the end of the 'A's already in the queue.
All I want you to alter is the enQueue and add the Bug struct and account for this new priority.
i have this so far basicqueue.h
Code: Select all
#pragma once
#include <iostream>
using namespace std;
class Unit
{
private:
string m_sName;
public:
Unit(const string s) : m_sName(s) {}
friend ostream& operator<<(ostream& s, const Unit& u);
};
template <class T>
class Node
{
public:
T m_tData;
Node<T>* m_pNext;
Node(T val) : m_tData(val), m_pNext(nullptr) {}
};
class Bugs
{
private:
char m_cPriority;
string m_sDesc;
};
template <class T>
class BasicQueue
{
private:
Node<T>* m_pHead;
Node<T>* m_pTail;
public:
BasicQueue() : m_pHead(nullptr), m_pTail(nullptr) {}
~BasicQueue()
{
//Node<T>* current = m_pHead; // Consider this an iterator.
Node<T>* next;
while (m_pHead != nullptr)
{
next = m_pHead->m_pNext;
delete m_pHead;
m_pHead = next;
}
}
void enQueue(T val) // 'Push' method.
{
Node<T>* newNode = new Node<T>(val);
if (m_pHead == nullptr) // List is empty.
{
m_pHead = m_pTail = newNode;
}
else // New node becomes the new tail.
{
m_pTail->m_pNext = newNode;
m_pTail = m_pTail->m_pNext;
}
}
T deQueue() // 'Pop' method.
{
if (m_pHead != nullptr)
{
T val = m_pHead->m_tData; // Storing the data to be returned.
Node<T>* next;
next = m_pHead->m_pNext;
delete m_pHead; // Deallocating head.
m_pHead = next;
return val; // Throwing copy of old head's data.
}
}
bool isEmpty()
{
return m_pHead == nullptr;
}
void print()
{
if (isEmpty())
return;
cout << "Queue contents: ";
Node<T>* current = m_pHead;
while (current != nullptr)
{
cout << current->m_tData << ' ';
current = current->m_pNext;
}
cout << endl;
}
};
ostream& operator<<(ostream& s, const Unit& u)
{
s << u.m_sName;
return s;
}
Code: Select all
#include <iostream>
#include <string>
#include "BasicQueue.h"
using namespace std;
int main()
{
BasicQueue<int> iQ;
iQ.enQueue(42);
iQ.enQueue(117);
iQ.print();
Unit uOne("Infantry");
Unit uTwo("Commando");
BasicQueue<Unit> uQ;
uQ.enQueue(uOne);
uQ.enQueue(uTwo);
uQ.print();
uQ.deQueue();
uQ.print();
system("pause");
return 0;
}
this is my basicqueue.h
)