| |
// File: priorityQueue.cpp
// Author: Nuno Alves (nca@bu.edu)
//
//Purpose: To write a class priorityQueue. As private data your class should
//contain an array of queues. Each element of the array corresponds to a
//different priority.
//Your insert method puts an element into the queue corresponding to its
//priority; the remove method checks the queues one by one to find the first
//non-empty queue and then takes it from there.
//You may assume that your priority queue is storing integer data, although
//your design will be nicer if the type is parameterized--i.e. if you make
//your class a template class.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
//Node structure. This is the base of this program. This Node structure has
//a pointer to the next node (*next) and an integer value (data). If there
//is no next node, then the value of next is NULL.
struct Node {
Node(int d) : data(d), next(0) { }
Node *next;
int data;
};
//class queue
//===========
//this class will implement a simple queue.
//
//example of operation:
//
// queue myqueue; //initializes the queue object
// myqueue.insert(1); //inserts value 1 into the queue
// myqueue.insert(2); //inserts value 2 into the queue
// myqueue.display(); //displays the contents of the queue
// myqueue.remove(); //removes the foremost value from the queue (1)
// myqueue.display(); //displays the contents of the queue
//
class queue{
public:
queue(){size=0;}
void insert(int data);
int remove ();
void display();
int get_size(){return size;} //returns the current size of queue
private:
int size;
Node *pNode;
Node *pHead;
};
//inserts a node into the queue. Takes in a data value that will
//be used to store in the node.
void queue::insert(int data)
{
//everytime another node is inserted, the size of the queue is
//increased... this is just so we can keep track of its size
size++;
Node *newnode;
newnode = new Node(data);
//if there already is more than one node in the queue
if (size>1)
{
//adds the address of the the newly created node to the
//previous node
pNode->next=newnode;
//puts the newnode in the last position of the queue
pNode=pNode->next;
}
//if there is no nodes in the queue, then add the first node to the
//pHead and never touch it again... This is how the class know where
//the linkedlist starts
else
{
pHead=newnode;
//pNode will now know what the newnode is
pNode=newnode;
}
}
//this will remove the first member of the queue. Returns the value
//that was inside the node that was just removed
int queue::remove()
{
//if there is something to remove
if (size>0)
{
//stores the value of the first node in the queue in a temporary
//variable
int value=pHead->data;
Node *ptmp;
ptmp=pHead;
//changes the Head to the second node
pHead=pHead->next;
//reclaims some memory back to the os
delete ptmp;
size--; //decrease the size of the queue
//returns the value stored in the temporary variable
return(value);
}
else return(-1); //if the queue is empty
}
//this will display all the queue contents
void queue::display()
{
//if there exist a node, then proceed
if (size>0)
{
Node *ptmp;
ptmp=pHead;
//goes through every single node and outputs its contents
while(ptmp!=NULL)
{
cout<<" "<<ptmp->data;
ptmp=ptmp->next;
}
}
cout<<"\n";
}
//class priorityQueue
//====================
//
//This class will implement a priority queue (various queues with different
//degrees of priority)
//
//example of operation:
//
//priorityQueue myqueue(3); //initialization of a priority queue with 3
// //levels of priority
// //priority queues: 0 is highest and 2 is the
// //lowest
//
//myqueue.insert_pq(2,13); //inserts the value 13, into queue with
// //priority 1
//
//myqueue.display_pq(); //displays all queues, contents and its
// //priorities
//
//myqueue.remove_pq(); //remove a node from the priority queue
class priorityQueue{
public:
priorityQueue(int n); //n is the number of queues
void insert_pq(int priority,int data);
void display_pq();
int remove_pq();
private:
int nqueues;
queue *pqueue;
};
//constructor. It will create an array of queues and store the number
//of queues in the nqueues variable
priorityQueue::priorityQueue(int n)
{
nqueues = n;
//allocating memory for the new array of queues
pqueue = new queue [nqueues];
}
//this will insert a value into the proper queue given its priority
void priorityQueue::insert_pq(int priority, int data)
{
//a bit of error checking against evil users
if ((priority>=nqueues)||(priority<0))
cout<<"There is no queue with such priority level "<<priority<<"\n";
else
//inserting data in the queue the user specified
pqueue[priority].insert(data);
}
//this will display the contents of all priority queues
void priorityQueue::display_pq()
{
//scanning all queues while displaying its contents
for(int i=0;i<nqueues;i++){
cout<<"Displaying Queue with priority "<<i<<": ";
pqueue[i].display();
}
}
//this will remove one value from the priority queue. Since one value needs
//to be removed, it will start from the queue with highest priority. If it
//does not have any value to be removed, then it will go the the next queue
//lower in priority. It will keep doing this until an entry is removed or
//until all queues are scanned
int priorityQueue::remove_pq()
{
for(int i=0;i<nqueues;i++)
{
//if there are elements in queue of a a certain priority
if (pqueue[i].get_size()>0){
//delete the first value of the queue and
//return the value
cout<<"\nFrom Queue with priority "<<i;
return(pqueue[i].remove());
}
}
return(-1); //returns -1 if there is no more elements to remove in
//the entire thing
}
void main()
{
srand(time(0));
int random_nbr=1+rand()%10;
cout<<"Random number of priority queues (from 1 to 10): "<<random_nbr;
//creating a number (random_nbr) of priority queues.
priorityQueue myqueue(random_nbr);
cout<<"\n\nPriority queues: \n0 has highest priority \n"<<
random_nbr-1<<" has lowest priority\n\n";
//inserting x random values into the priority queue (1 to 20 values),
//in random queues with different priorities. The values inserted will
//also be random (1 to 30)
//
//example of operation:
//myqueue.insert_pq(2,13); //inserts the value 13, into queue with
// //priority 1
int x=1+rand()%20;
for (int i=0;i<x;i++)
myqueue.insert_pq(rand()%(random_nbr),1+rand()%30);
//displaying the all queues contents, its values and priorities
myqueue.display_pq();
//removing all contents of the priorityqueue. It will not stop until
//all elements have been removed
while (random_nbr!=-1)
{
random_nbr=myqueue.remove_pq();
if (random_nbr!=-1)
cout<<", "<<random_nbr<<" was removed";
else
cout<<"\nNo more elements to remove... priority queue is empty.\n";
}
} |