Description

The purpose of this challenge is to implement a queue using a linked list as a backing data structure

Requirements

1. Write the following struct

   struct JobNode
   {
     string name;
     JobNode * next;
   };

2. Create a class called Queue. In this class, create a private variable JobNode * head. This will keep track of the location of the head node.
3. Add the following private function. This function will be used to dynamically create new nodes for the linked list.

   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();

4. Create a private function called void deallocate(). This function will traverse the entire list and delete each node. Remember to make a copy of head. Also, realize that if you delete the current node as you’re traversing, you may lose the reference to the next node.
5. Create a destructor which will call deallocate() and set head to NULL.
6. Create a public function, bool enqueue(string name). This function will:
   1. create a new node (JobNode) using the create() function you wrote earlier. The new node will be assigned the values for name from the function’s parameter values.
   2. add the new node to the front of the linked list (where head points). Remember to deal with two possible scenarios: 1) The list is still empty and this is the first node to be added and 2) The list is not empty
   3. point head to the newly-added node
   4. return true if it’s successful, and false otherwise. The only reason it would be false is if the new node didn’t get created by the create() function (if the new node is NULL)
7. Create a public function, string dequeue(). This function will
   1. Identify the node at the end of the list (if not empty). You will have to traverse the list and identify the node that points to NULL at the end.
   2. Copy the value of the node’s name property into a temporary variable
   3. Point the next-to-last node to NULL. You will also have to account for if there is only one node in the actual queue — dequeue-ing the only node in the queue would mean head would need to point to NULL.
   4. delete the last node (this effectively is the “dequeue” action)
   5. Return the name value stored in the temporary variable. Return a blank string if the linked list is empty
8. Create a friend function void show(Queue & Q). This will display all the name values of all the nodes one per line. Traverse the entire linked list to show the node values. If you show the list from head to NULL (easier), it will display in reverse order of the queue — this is fine to display it this way. OR, you can display it in queue order (oldest to newest-more difficult) — this is how the sample interaction shows the queue.
9. main() is given below. Use it exactly as is. Note that main uses the Queue class as an abstract data type (ADT). From the perspective of the object spooler, it doesn’t even know or care that a linked-list is the mechanism that makes FIFO (first-in, first-out) work.

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;
}