A priority queue is a collection of items each having a priority. A priority queue supports three fundamental operations.
For example, suppose that you start with an empty priority queue and imagine performing the following steps.
You should find that x is "two" and y is "one".
The Assignment
create a C++ module called pqueue.cpp that implements priority queues, with a header file called pqueue.h that describes what pqueue.cpp exports. The interface includes the following, and nothing else. Types ItemType and PriorityType are discussed below under the refinement plan.
PriorityQueue q;
bool isEmpty(const PriorityQueue& q);
void insert(PriorityQueue& q, ItemType x, PriorityType p);
void remove(PriorityQueue& q, ItemType& x, PriorityType& p);
exit(1);
Summary of the interface
A module that uses priority queues can do the following, and nothing more.
PriorityQueue q;
bool isEmpty(const PriorityQueue& q); void insert(PriorityQueue& q, ItemType item, PriorityType pri); void remove(PriorityQueue& q, ItemType& item, PriorityType& pri);
void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, PriorityPrinter printPriority);
Additional Requirements
Your program must follow the design in the section "A refinement plan." It can have additional functions, but it must have at least the functions indicated in the design. Do not add extra responsibilities to the required functions.
A Refinement Plan
Development plan1. Make a directory for assignment 6 and create files pqueue.h and pqueue.cpp.
Use the module-template for pqueue.cpp and the header-template for pqueue.h. Modify the templates with your name and the separation between tab stops, if you use tabs.
Get files Makefile, dotest and testpqueue.cpp and put them in that directory.
Add a comment to pqueue.cpp telling its purpose. It provides priority queues. Give a sketch of the interface.
2. Items and Priorities: Types ItemTypa and PriorityType
Your module is intended to support an application, not to be an application. You will use it in assignments 7 and 8.
It is not clear right now what types of items or priorities the application will need; assignment 7 needs different item and priority types than assignment 8.
To handle that, define two types, ItemType and PriorityType, in pqueue.h. For this assignment, use definitions
typedef const char* ItemType; typedef double PriorityType;
Later, when you want to change the definitions of ItemType and PriorityType, you should only need to change those two lines. Not a single other line should need to be touched. (You might need to add one or more #include lines to pqueue.h to make some types available.)
That means you need to write the entire implementation of priority queues using ItemType for the type of an item and PriorityType for the type of a priority. Do not assume that ItemType is const char* or that PriorityType is double. They will need to be changed for later assignments.
3. Representing Priority Queues: Types PriorityQueue and PQCell
You are required to represent the information in a priority queue using a linked list, kept in nondecreasing order by priority. That means items with smaller priorities are closer to the beginning of the linked list. You will need the following types.
struct PQCell;
4. Testing Whether a Priority Queue Is Empty
In pqueue.cpp, document and define function isEmpty(q) with the following prototype.
bool isEmpty(const PriorityQueue& q);
IsEmpty(q) must return true if q is empty, false if q is not empty.Add a prototype for isEmpty pqueue.h.
5. Insertion into a Priority Queue
In pqueue.cpp, document and define function insert(q, x, p), which inserts item x with priority p into PriorityQueue object q. Add prototype
void insert(PriorityQueue& q, ItemType x, PriorityType p);
to pqueue.h. will find it convenient to make a helper function
void insertCell(PQCell*& L, ItemType x, PriorityType p)
that inserts item x with priority p into linked list L (made of PQCells). It assumes that L is in nondescending order by priority, and it inserts the new item into the correct spot so that the list is still in nondescending order by priority.The reason for defining 'insertCell' is that it can be recursive, and that makes it easier to write. The body of 'insert' should just make a call to 'insertCell'. That is, 'insert' should have a one-line body.
Do not put a prototype for 'insertCell' into pqueue.h since 'insertCell; is not being exported; it is only to be used in pqueue.cpp.
6. Debugging: Printing the Priority Queue
In pqueue.cpp, make a function for debugging that prints the content of the priority queue in a readable format.
There is an important issue here. Remember that the definitions of types ItemType and PriorityType might be changed. You cannot assume that ItemType is const char* or that PriorityType is double. But then how do you know how to print the items and priorities?
A solution is to require the module that uses priority queues to say how to print items and priorities by providing two functions, one for printing an item and another for printing a priority. C++ allows you to pass a function as a parameter of a function. (Think of lending a tool to a friend. You don't use the tool, your friend does.)
Add the following type definitions to pqueue.h.
typedef void (*ItemPrinter)(ItemType); typedef void (*PriorityPrinter)(PriorityType);
They define types ItemPrinter and PriorityPrinter. The function to print an item has type ItemPrinter; it takes a parameter of type ItemType and has a void return type. The function to print a priority has type PriorityPrinter. It takes a parameter of type PriorityType and has a void return type.In pqueue.cpp, document and define a function printPriorityQueue with the following prototype.
void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, PriorityPrinter printPriority);
It must show a clear and readable representation of what is in priority queue q, including each value and its priority. In the body of printPriorityQueue, use statement
printItem(x);
to print item x and
printPriority(y);
to print priority y.PrintPriorityQueue should assume that printItem and printPriority do not make any spaces or newlines. PrintPriorityQueue should print those. It is not acceptable to write out the entire priority queue on one line.
Function printPriorityQueue is only intended to be used for debugging. Put a prototype for printPriorityQueue into pqueue.h so that other modules can use it for debugging.
7. Testing insert
Add a stub for 'remove'. It does nothing, but it allows you to run the tester to test 'insert'. Here is a suitable stub.
void remove(PriorityQueue& q, ItemType& x, PriorityType& p) { x = "nothing"; p = 0.0; }
Put a prototype for remove into pqueue.h.
Now use the automated tester to test insert. Don't be surprised that errors are reported about 'remove' not working. But don't move on to the next step until 'insert' is working.
8. Removing an Item
In pqueue.cpp, replace the stub for 'remove' by a correct definition. 'Remove' must remove the item from q that has the smallest priority. (If two or more items have the same priority, remove one of them.)
Parameters x and p are out-parameters. 'Remove' must store the item that is removed into variable x and store its priority into p.
Be sure that 'remove' deletes the list cell that is removed so that you do not have a memory leak.
9. Test remove
Rerun the automated tester. This time, everything should look right. If not, fix any errors.
10. Proofread pqueue.cpp and pqueue.h.
Check contracts for correctness, spelling and grammar. Are standards followed? Are all parameters described and referred to by na
pqueue.h
#include <cstdio>
#include <cstdlib>
using namespace std;
#include "tree.h"
typedef Tree ItemType;
typedef int PriorityType;
struct PQCell;
//PriorityQueue is a sturcture that holds the first ponter to
a
//linked list of PQCells
struct PriorityQueue
{
PQCell* First;
PriorityQueue()
{
First =
NULL;
}
};
bool isEmpty(const PriorityQueue& pQueue);
void insert(PriorityQueue& pQueue, ItemType thisItem,
PriorityType priority);
typedef void (*ItemPrinter)(ItemType);
typedef void (*PriorityPrinter)(PriorityType);
void printPriorityQueue(const PriorityQueue& pQueue,
ItemPrinter pi,
PriorityPrinter pp);
void remove(PriorityQueue& q, ItemType& x,
PriorityType& p);
pqueue.cpp
#include <cstdlib>
#include <cstdio>
#include "pqueue.h"
using namespace std;
//PQCell is a structure to be useds as a cell in a linked list,
it
//contains a priority, an item, and a PQCell pointer.
struct PQCell
{
ItemType item;
PriorityType priority;
PQCell* next;
};
//isEmpty(pQueue) returns true if PriorityQueue pQueue points
to
//an empty list
bool isEmpty(const PriorityQueue& pQueue)
{
return pQueue.First == NULL;
}
//insertCell(List, item, priority) inserts item x with priority
p into linked
//list List in the correct spot.
void insertCell(PQCell*& List, ItemType item, PriorityType
thisPriority)
{
if(List == NULL || List -> priority <=
thisPriority)
{
PQCell* newList = new PQCell;
newList -> item = item;
newList -> priority =
thisPriority;
newList -> next =
List;
List = newList ->
next;
}
else
{
insertCell(List -> next, item,
thisPriority);
}
}
//insert(pQueue, thisItem, priority) inserts Item thisItem into
PriorityQueue
//pQueue with PriorityType priority
void insert(PriorityQueue& pQueue, ItemType thisItem,
PriorityType priority)
{
insertCell(pQueue.First, thisItem, priority);
}
//printPriorityQueue(pQueue, pi, pp) is a method used for
debugging which
//prints the contents of priority queue pq to the standard
output.
void printPriorityQueue(const PriorityQueue& pQueue,
ItemPrinter pi,
PriorityPrinter pp)
{
if(!isEmpty(pQueue))
{
return;
}
PQCell* pointer = pQueue.First;
while(pointer != NULL)
{
pi(pointer ->next -> item);
printf("\t");
pp(pointer ->next -> priority);
printf("\n");
pointer = pointer -> next;
}
}
void remove(PriorityQueue& q, ItemType& x,
PriorityType& p)
{
if(!isEmpty(q))
{
x = q.First -> item;
p = q.First -> priority;
PQCell toBeDeleted =
*q.First;
q.First = q.First -> next;
delete [] &toBeDeleted;
}
else
{
exit(0);
}
}
A priority queue is a collection of items each having a priority. A priority queue supports three...
Can you please write the two C++ modules below is a step by step instuctions to follow that will make it very easy thanks. Create a module called pqueue.cpp that implements priority queues, with a header file calledpqueue.hthat describes what pqueue.cpp exports. The interface includes the following, and nothing else. Types ItemType and PriorityType are discussed below under the refinement plan. A type, PriorityQueue. Creating a PriorityQueue object with line PriorityQueue q; makes q be an initially empty priority queue....
Can you please write the two C++ modules below is a step by step instuctions to follow that will make it very easy thanks. Create a module called pqueue.cpp that implements priority queues, with a header file calledpqueue.hthat describes what pqueue.cpp exports. The interface includes the following, and nothing else. Types ItemType and PriorityType are discussed below under the refinement plan. A type, PriorityQueue. Creating a PriorityQueue object with line PriorityQueue q; makes q be an initially empty priority queue....
Data Structure Java code Q2 [ 20 pts]. In computer science, a priority queue is an abstract data type which is like a regular queue data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to the order in which they were enqueued A typical priority queue supports following...
CS 373 Home Work project 11 Create a queue class by priviate inherting the unorderedArrayListType class. A queue class is a First-In-First-Out data structure. To understand a queue, think of a checkout line at a grocery store: the person at the front is served first (removed), and people are added to the line from the back end. class queue : private unorderedArrayListType { public: bool isEmpty() const; // test whether queue is empty // Post: returns true if queue is...
I want the full code for this part and Its needs to be done in C++ Use a linked list to implement the following skeleton of an unsorted list typedef int ItemType: struct NodeType ItemType item; NodeType "next; class List List(); // default constructor List( const List &x); I copy constructor: deep copy is required List & operator = (const List &x); // assignment operator: deep copy. 1s required bool IsThere(ItemType x); identify if x is in the list void...
C++ ((USE STL verison please)) Implement the queue class as shown above. Use your queue to store the names of 5 students waiting outside Student Services to meet with advisors. You may want to add more data to each node including student ID, Major, etc. Add a member function displayQueue which displays the contents of the queue. Write the main function to test the queue. CLASS: #ifdef queue_h #define queue_h namespace queues { struct queueNode{ char data; queueNode *link; };...
C++ Error. I'm having trouble with a pointer. I keep getting the error "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)" The objective of the assignment is to revise the public method add in class template LinkedBag so that the new node is inserted at the end of the linked chain instead of at the beginning. This is the code I have: linkedBag-driver.cpp BagInterface.hpp LinkedBag.hpp Node.hpp int main) LinkedBag<string> bag; cout << "Testing array-based Set:" << endl; cout << "The initial bag is...
c++ please Given the following skeleton of an unsorted list class that uses an unsorted linked list: template<class ItemType> struct NodeType { ItemType item; NodeType* next; }; template<class ItemType> class UList { public: UList(); // default constrctor UList(const UList &x); // we implement copy constructor with deep copy UList& operator = (UList &x); // equal sign operator with deep copy bool IsThere(ItemType item) const; // return true of false to indicate if item is...
3. Some circular queue implementations use the mod operator % in enqueue and dequeue operations. Explain why this is inefficient. 4. If a queue is implemented using a singly linked list with a head and tail pointer, you should always insert at the tail and remove from the head. Explain why this is so. 5. What is a Priority Queue, and how does it differ from a standard queue? 6. Priority Queues are almost always implemented with an ordered data...
I'm just not sure how to tackle all the template class this header wants me to write. I got this far into making the template for public and private and would like help on the template functions. Thank you! This is in C++ by the way. #include <iostream> #include <cassert> using namespace std; #ifndef ARRAYLIST_H #define ARRAYLIST_H template<typename T> class arrayList { public: arrayList(); //Constructor with default parameter. //Sets maxSize = 100 and length = 0 if no parameter...