C++ Program Chapter 17, Programing Project 6: Write a template version of a clas
ID: 3695902 • Letter: C
Question
C++ Program
Chapter 17, Programing Project 6:
Write a template version of a class that implements a priority queue. Queues are discussed in Chapter 13 and priority queues are discussed in Chapter 18. To summarize, a priority queue is essentially a list of items that is always ordered by priority. Each item that is added to the list requires an associated priority value. For this problem, make the priority an integer where 0 is the highest priority and larger values are lower in priority. Removing an item from the queue removes the item with the highest priority.
The add function of the priority queue should take a generic type and then an integer priority. In the following example, the generic type is a char and we have added three items to the queue:
q.add(‘X’, 10);
q.add(‘Y’, 1);
q.add(‘Z’, 3);
The remove function should return and remove from the priority queue the item that has the highest priority. Given the example above, we would expect the following:
cout << q.remove(); //Outputs Y (priority 1)
cout << q.remove(); //Returns Z (priority 3)
cout << q.remove(); //Returns X (priority 10)
Test your queue on data with priorities in various orders (for example, ascending, descending, mixed). You can implement the priority queue by storing the items using a list(s) of your choice (for example, vector array, linked list, or GenericList described in this chapter) and then performing a linear search for the item with the lowest integer value in the remove function. In future courses you may study a data structure called a heap that affords a more efficient way to implement a priority queue.
Explanation / Answer
program code: Priority queue using arrays
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int iVal;
int iPri;
}pri_queue_item;
typedef struct
{
int iSize;
int iFront;
int iRear;
int iCapacity;
pri_queue_item *itemArr;
}pri_queue_int_by_arr;
pri_queue_int_by_arr *createPriQueue_ByIntArr(int iCapacity)
{
pri_queue_int_by_arr *pQueue = NULL;
pQueue =(pri_queue_int_by_arr*)malloc(sizeof(pri_queue_int_by_arr));
pQueue->itemArr = (pri_queue_item*)malloc(iCapacity *sizeof(pri_queue_item));
pQueue->iCapacity = iCapacity;
pQueue->iFront = 0;
pQueue->iRear = -1;
pQueue->iSize = 0;
return pQueue;
}
bool isPriQueueEmpty_ByIntArr(pri_queue_int_by_arr *pQueue)
{
return (pQueue->iSize == 0);
}
bool isPriQueueFull_ByIntArr(pri_queue_int_by_arr *pQueue)
{
return ((pQueue->iSize) == (pQueue->iCapacity));
}
void printPriQueue(pri_queue_int_by_arr *pQueue)
{
int iCurrInd = 0;
if(!isPriQueueEmpty_ByIntArr(pQueue))
{
for (iCurrInd = (pQueue->iFront); iCurrInd <= (pQueue->iRear); iCurrInd = (iCurrInd + 1) % (pQueue->iCapacity))
printf("%d ", pQueue->itemArr[iCurrInd].iVal);
}
}
bool insertToPriQueue_ByIntArr(pri_queue_int_by_arr *pQueue, int iData, int iPri)
{
if(isPriQueueFull_ByIntArr(pQueue))
{
printf("ERR(Trying to insert %d): Priority Queue Overflow! ", iData);
return false;
}
pQueue->iRear = (pQueue->iRear + 1) % (pQueue->iCapacity);
pQueue->itemArr[pQueue->iRear].iVal = iData;
pQueue->itemArr[pQueue->iRear].iPri = iPri;
(pQueue->iSize)++;
/*printf("%d pushed to queue ", iNewData);*/
return true;
}
int getHighestPriFromPriQueue_ByIntArr(pri_queue_int_by_arr *pQueue)
{
int iMaxPriInd = -1, iCurrInd = 0;
if(!isPriQueueEmpty_ByIntArr(pQueue))
{
iMaxPriInd = pQueue->iFront;
for (iCurrInd = (pQueue->iFront); iCurrInd <= (pQueue->iRear); iCurrInd = (iCurrInd + 1) % (pQueue->iCapacity))
{
if((pQueue->itemArr[iMaxPriInd].iPri) < (pQueue->itemArr[iCurrInd].iPri))
iMaxPriInd = iCurrInd;
}
}
return iMaxPriInd;
}
void deleteHighestPriFromPriQueue_ByIntArr(pri_queue_int_by_arr *pQueue)
{
int iMaxPriInd = 0, iCurrInd = 0;
iMaxPriInd = getHighestPriFromPriQueue_ByIntArr(pQueue);
if(iMaxPriInd != -1)
{
for (iCurrInd = iMaxPriInd; iCurrInd < (pQueue->iRear); iCurrInd++)
pQueue->itemArr[iCurrInd] = pQueue->itemArr[iCurrInd +1];
(pQueue->iRear)--;
}
}
void test_PriorityQueue_ByIntArr()
{
printf(" ---TEST: Priority Queue(By IntArr) Operations ");
pri_queue_int_by_arr *pQueue =createPriQueue_ByIntArr(10);
insertToPriQueue_ByIntArr(pQueue, 5, 3);
insertToPriQueue_ByIntArr(pQueue, 10, 2);
insertToPriQueue_ByIntArr(pQueue, 15, 5);
insertToPriQueue_ByIntArr(pQueue, 20, 1);
insertToPriQueue_ByIntArr(pQueue, 25, 4);
printf("Queue Content: ");
printPriQueue(pQueue);
printf(" Highest Pri. Item: %d ", pQueue>itemArr[getHighestPriFromPriQueue_ByIntArr(pQueue)].iVal);
deleteHighestPriFromPriQueue_ByIntArr(pQueue);
printf("Queue Content: ");
printPriQueue(pQueue);
printf(" Highest Pri. Item: %d ", pQueue>itemArr[getHighestPriFromPriQueue_ByIntArr(pQueue)].iVal);
}
int main(void)
{
test_PriorityQueue_ByIntArr();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.