Chapter 15, Problem 12PP

Program Plan Intro

Priority Queue

Program Plan:

queue.h:

• Include required header files.
• Create a namespace named “queuesavitch”.
  • Create a structure.
    • Declare a variable and a pointer.
  • Declare a class “Queue”.
    • Inside “public” access specifier.
      • Declare the constructor and destructor.
      • Declare the functions “add ()”, “remove ()”, “empty ()”.
    • Inside the “protected” access specifier,
      • Create a pointer “front” that points to the head of the linked list.
      • Create a pointer “back” that points to the other end of the linked list.

queue.cpp:

• Include required header files.
• Create a namespace named “queuesavitch”.
  • Declare the constructor.
  • Inside the parameterized constructor,
    • Declare the temporary point that moves through the nodes from front to the back.
    • Create a pointer “temp_ptr_new” that is used to create new nodes.
    • Create new nodes.
    • Assign “emp_ptr_old->link” to “temp_ptr_old”.
    • Using while condition “temp_ptr_old != NULL”.
      • Create a new node.
      • Assign the temporary old data to the new pointer.
      • Assign NULL to the link of temporary new pointer.
      • Assign “temp_ptr_new” to “back->link”.
      • Assign “temp_ptr_new” to “back”.
      • Assign “temp_ptr_old->link” to “temp_ptr_old”.
  • Give definition for the destructor.
    • Declare a variable “next”.
    • Do till the queue is empty.
      • Remove the items using “remove ()” method.
  • Give definition for “empty ()” to check if the queue is empty or not.
    • Return “back == NULL”.
  • Give definition for the method “add ()”.
    • Check if the queue is empty.
      • Create a new node.
      • Assign the item to the data field.
      • Make the front node as null.
      • Assign front as the back.
    • Else,
      • Create a new pointer.
      • Create a new node.
      • Assign the item to “temp_ptr->data”.
      • Assign “NULL” to “temp_ptr->link”.
      • Assign temporary pointer to the link.
      • Assign temporary pointer to the back.
  • Give definition for the method “remove ()”.
    • Check if the queue is empty.
      • Print the message.
    • Store the value into the variable “result”.
    • Create an object “discard” for the pointer “QueueNodePtr”.
    • Assign “front” to “discard”.
    • Assign the link of front to “front”.
    • Check if the front is null.
      • Assign null to the back.
    • Delete the object “discard”.
    • Return “result”.

PriorityQueue.h:

• Include required header files.
• Create a namespace named “queuesavitch”.
  • Declare a class “PriorityQueue”.
    • Inside “public” access specifier,
      • Declare the constructor and destructor.
      • Declare the virtual function.

PriorityQueue.cpp:

• Include required header files.
• Create a namespace named “queuesavitch”.
  • Declare the constructor and destructor.
  • Give function to remove items.
    • Check if the queue is empty.
      • Print the messge.
    • Assing “front->data” to “smallest”.
    • Assign “NULL” to “nodeBeforeSmallest”.
    • Assign “front” to “previousPtr”.
    • Assign the link of front to “current”.
    • Using while condition “current != NULL”,
      • Check if the data is smaller.
        • Assing “current->data” to “smallest”.
        • Assign “previousPtr” to “nodeBeforeSmallest”.
      • Assign “current” to “previousPtr”.
      • Assign “current->link” to “current”.
    • Create an object “discard”.
    • Check if the node is null.
      • Assign “front” to “discard”.
      • Assign the link of front to “front”.
    • Check if the link is equal to back.
      • Assign “back” to “discard”.
      • Assign “nodeBeforeSmallest” to “back”.
      • Assign “NULL” to “back->link”.
    • Else,
      • Assign “nodeBeforeSmallest->link” to “discard”.
      • Assign “discard->link” to “nodeBeforeSmallest->link”.
    • Check if front is equal to null.
      • Assign “NULL” to “back”.
    • Delete the object “discard”.
    • Return the smallest item.

main.cpp:

• Include required header files.
• Inside the “main ()” function,
  • Create an object for “PriorityQueue”.
  • Add the integers to the queue using “add ()” method.
  • While “(!que.empty())”,
    • Call the function “que.remove()”.
  • Declare a character variable.
  • Get a character.
  • Return the statement.