In: Computer Science
Description( IN C++) NO TAIL POINTERS!!
The purpose of this challenge is to implement a queue using a linked list as a backing data structure
Requirements
struct JobNode { string name; JobNode * next; };
JobNode * create() { JobNode * newnode; try { newnode = new JobNode; } catch (bad_alloc) { newnode = NULL; } return newnode; } // USAGE: To create a new node, use as follows // JobNode * newnode = create();
Sample main()
int main() { Queue spooler; // simulate a printer spooler spooler.enqueue("Comm100 Paper.docx"); spooler.enqueue("Fwd: Direct Deposit"); spooler.enqueue("document(1).doc"); spooler.enqueue("lab9.cpp"); cout << "Pending jobs: " << endl; show(spooler); // this shows all jobs // simulate the printer completing the jobs string oldest; do { oldest = spooler.dequeue(); if (oldest != "") { cout << "Printing..." << endl; cout << oldest << " printed" << endl; cout << endl << "Pending jobs:" << endl; show(spooler); } } while (oldest != ""); cout << "No jobs" << endl; return 0; }
PROGRAM :
#include <iostream>
using namespace std;
struct JobNode {
string name;
JobNode * next;
};
class Queue
{
private:
JobNode * head;
JobNode * create();
void deallocate();
public:
Queue();
~Queue();
bool enqueue(string name);
string dequeue();
friend void show(Queue & Q);
};
// function to create and return a new JobNode
JobNode* Queue::create()
{
JobNode * newnode;
try{
newnode = new JobNode; // create a new JobNode
}catch(bad_alloc &e)
{
// if not allocated, set node to NULL
newnode = NULL;
}
return newnode; // return the new node
}
// function to deallocate the memory of nodes
void Queue::deallocate()
{
// loop till the end of list, deleting the nodes
while(head != NULL)
{
JobNode *temp = head;
head = head->next;
delete(temp);
}
}
// constructor that initializes an empty queue
Queue::Queue()
{
head = NULL;
}
// destructor that destroys the queue
Queue::~Queue()
{
deallocate();
}
// function to insert the name at the head of the queue
bool Queue:: enqueue(string name)
{
JobNode *node = create(); // create a new job node
if(node == NULL) // if allocation is not successful
return false;
// set the name and next pointer of the node
node->name = name;
node->next = NULL;
if(head == NULL) // empty queue
head = node;
else // non-empty queue
{
node->next = head;
head = node;
}
return true;
}
// function to delete and remove the last node of the
queue
string Queue:: dequeue()
{
string value = "";
if(head != NULL) // non-empty queue
{
JobNode *curr = head;
JobNode *prev = NULL;
// loop to get the last node
while(curr->next != NULL)
{
prev = curr;
curr = curr->next;
}
value = curr->name; // get the name of the last node
// if queue has only one node
if(prev == NULL)
{
head = NULL; // set it to empty queue
}else
{
prev->next = NULL; // set the next of previous node to
NULL
}
delete(curr); // delete the last node
}
return value;
}
// function to display the contents of the Queue from head to
NULL
void show(Queue & Q)
{
JobNode *curr = Q.head;
// loop over the queue and display the names
while(curr != NULL)
{
cout<<curr->name<<" ";
curr = curr->next;
}
}
int main()
{
Queue spooler; // simulate a printer spooler
spooler.enqueue("Comm100 Paper.docx");
//show(spooler);
spooler.enqueue("Fwd: Direct Deposit document(1).doc");
spooler.enqueue("lab9.cpp");
cout<<"Pending jobs: ";
show(spooler);
cout<<"\nPrinting....";
cout<<spooler.dequeue();
return 0;
}