Question

In: Computer Science

Description( IN C++) NO TAIL POINTERS!! The purpose of this challenge is to implement a queue...

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

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

Solutions

Expert Solution

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;

}


Related Solutions

Description( IN C++)!! The purpose of this challenge is to implement a stack using a Linked...
Description( IN C++)!! The purpose of this challenge is to implement a stack using a Linked List as a backing data structure Requirements Write the following structs struct Location { string name; string address; }; struct VisitNode { Location loc; VisitNode * next; }; Create a class called Stack. In this class, create a private variable VisitNode * head. This will keep track of the location of the head node. Add the following private function. This function will be used...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy node. This challenge simulates an operating system’s window manager. Requirements Write the following struct struct Window { string appname; Window *next; Window *prev; }; Create a class called WindowManager. In this class, create a private variable Window * head. This will keep track of the location of the head node. Create private variables Window * current, * dummy. current will keep track of the...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
write C program to implement the priority queue with the operation insert
write C program to implement the priority queue with the operation insert
Implement a queue - C programming, please read the instruction carefully and implement queue.c using dynamic...
Implement a queue - C programming, please read the instruction carefully and implement queue.c using dynamic array structure given dynarray.h and dynarray.c below The second ADT you'll implement for this assignment is a queue. For this assignment, the interface for the queue (i.e. the structures and the prototypes of functions a user of the queue interacts with) is already defined for you in the file queue.h. Your first task in this assignment is to implement definitions for the functions that...
C language Write a program in C to implement Queue and its operation (like create, insert,...
C language Write a program in C to implement Queue and its operation (like create, insert, delete, search) using array data structure.
Write a C program to implement the priority queue with the operations insert and extractmax. Sample...
Write a C program to implement the priority queue with the operations insert and extractmax. Sample : ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 2 enter any key to go to main menu ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 4 enter any key to go to main menu ====Menu==== insert extractmax display exit Enter your choice: 1 Input a number: 6 enter any key to go to main menu...
Write a C++ program (using pointers and dynamic memory allocation only) to implement the following functions...
Write a C++ program (using pointers and dynamic memory allocation only) to implement the following functions and call it from the main function. (1)Write a function whose signature looks like (char*, char) which returns true if the 1st parameter cstring contains the 2nd parameter char, or false otherwise. (2)Create an array of Planets. Populate the array and print the contents of the array using the pointer notation instead of the subscripts.
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a...
Language C++ Implement a Priority Queue with a Binary HEAP. Use a Max Heap. Create a class called Node: Have a Name and Priority.Data set - 10 is the highest priority, 1 is lowest priority. Enqueue and dequeue in the following order. Function  Name, Priority Enqueue  Joe, 3 Enqueue  Fred,1 Enqueue Tuyet,9 Enqueue  Jose, 6 Dequeue Enqueue  Jing, 2 Enqueue  Xi, 5 Enqueue  Moe, 3 DequeueEnqueue  Miko, 7 Enqueue Vlady, 8 Enqueue Frank, 9 Enqueue  Anny, 3 DequeueEnqueue  Xi, 2 Enqueue  Wali, 2 Enqueue  xChe, 6 Enqueue  xVerra, 8 Dequeue Dequeue Dequeue Dequeue...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT