Problem Solving with C++ (9th Edition)
9th Edition
ISBN: 9780133591743
Author: Walter Savitch
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
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.
- Inside “public” access specifier.
- Create a structure.
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.
- Check if the queue is empty.
- 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”.
- Check if the queue is empty.
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.
- Inside “public” access specifier,
- Declare a class “PriorityQueue”.
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”.
- Check if the data is smaller.
- 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.
- Check if the queue is empty.
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.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Assignment 05 PART 1 Queues
- Note Part 1 is a separate deliverable:
Write a class with a main method that uses a priority queue to store a list of prioritized chores. This
is all the information that is provided. The rest is up to you. You may decide how to store your
chores and how to store your priorities.
YOU MUST WRITE your own Queue class – do not use the Java Library, Queue Class.
Part 3: Building a Point of Sales (POS) linked list data structure.
In a POS system, a transaction is based on items purchased by the customer. The following is an example of a customer transaction receipt, where the prices shown in the receipt are GST inclusive.
Write a linked list classes (one class for Node and another class for List), which store the items in the transaction. Test the classes by printing the items in the linked list and show the total price of the transaction. The following listing is the sample output for your reference:
==============================
BC Items Price
==============================
10 Pagoda Gnut 110g 3.49
11 Hup Seng Cream Cracker 4.19
12 Yit Poh 2n1 Kopi-o 7.28
13 Zoelife SN & Seed 5.24
14 Gatsby S/FO Wet&Hard 16.99
15 GB W/G U/Hold 150g 6.49
==============================
Total (GST Incl.) 43.68…
C++ programming
design a class to implement a sorted circular linked list. The usual operations on a circular list are:Initialize the list (to an empty state).
Determine if the list is empty.
Destroy the list.
Print the list.
Find the length of the list.
Search the list for a given item.
Insert an item in the list.
Delete an item from the list.
Copy the list.
Write the definitions of the class circularLinkedList and its member functions (You may assume that the elements of the circular linked list are in ascending order). Also, write a program to test the operations of your circularLinkedList class.
NOTE: The nodes for your list can be defined in either a struct or class. Each node shall store int values.
Chapter 15 Solutions
Problem Solving with C++ (9th Edition)
Ch. 15.1 - Is the following program legal (assuming...Ch. 15.1 - Prob. 2STECh. 15.1 - Is the following a legal definition of the member...Ch. 15.1 - The class SalariedEmployee inherits both of the...Ch. 15.1 - Give a definition for a class TitledEmployee that...Ch. 15.1 - Give the definitions of the constructors for the...Ch. 15.2 - You know that an overloaded assignment operator...Ch. 15.2 - Suppose Child is a class derived from the class...Ch. 15.2 - Give the definitions for the member function...Ch. 15.2 - Define a class called PartFilledArrayWMax that is...
Ch. 15.3 - Prob. 11STECh. 15.3 - Why cant we assign a base class object to a...Ch. 15.3 - What is the problem with the (legal) assignment of...Ch. 15.3 - Suppose the base class and the derived class each...Ch. 15 - Write a program that uses the class...Ch. 15 - Listed below are definitions of two classes that...Ch. 15 - Solution to Programming Project 15.1 Give the...Ch. 15 - Create a base class called Vehicle that has the...Ch. 15 - Define a Car class that is derived from the...Ch. 15 - Prob. 4PPCh. 15 - Consider a graphics system that has classes for...Ch. 15 - Flesh out Programming Project 5. Give new...Ch. 15 - Banks have many different types of accounts, often...Ch. 15 - Radio Frequency IDentification (RFID) chips are...Ch. 15 - The goal for this Programming Project is to create...Ch. 15 - Solution to Programming Project 15.10 Listed below...Ch. 15 - The computer player in Programming Project 10 does...Ch. 15 - Prob. 12PP
Knowledge Booster
Similar questions
- You need to implement a class for Dequeue i.e. for double ended queue. In this queue, elements can be inserted and deleted from both the ends. You don't need to double the capacity. You need to implement the following functions - 1. constructor You need to create the appropriate constructor. Size for the queue passed is 10. 2. insertFront - This function takes an element as input and insert the element at the front of queue. Insert the element only if queue is not full. And if queue is full, print -1 and return. 3. insertRear - This function takes an element as input and insert the element at the end of queue. Insert the element only if queue is not full. And if queue is full, print -1 and return. 4. deleteFront - This function removes an element from the front of queue. Print -1 if queue is empty. 5. deleteRear - This function removes an element from the end of queue. Print -1 if queue is empty. 6. getFront - Returns the element…arrow_forwardWithout using C++ queue STL, write a simple menu based selection to insert, delete, show and exit from queue. 1. Create a class called Queue with member variable queueArr as integer queue array, integer rear and integer front to keep track both rear and front element in the queue array. 2. Define several member functions in Queue such as a a. constructor – initialize both rear and front to -1 b. insert – receive an integer and check if queue is full, if not then insert the integer to the queue array c. delete – delete front element from queue if front is not equal to rear (empty) d. display – if rear is not equal to front, then print out the queue array. 3. Write a main function to test the Queue class.arrow_forwardWithout using C++ queue STL, write a simple menu based selection to insert, delete, show and exit from queue. 1. Create a class called Queue with member variable queueArr as integer queue array, integer rear and integer front to keep track both rear and front element in the queue array. 2. Define several member functions in Queue such as a a. constructor – initialize both rear and front to -1b. insert – receive an integer and check if queue is full, if not then insert the integer to the queue arrayc. delete – delete front element from queue if front is not equal to rear (empty)d. display – if rear is not equal to front, then print out the queue array. 3. Write a main function to test the Queue class.arrow_forward
- Tour.java Create a Tour data type that represents the sequence of points visited in a TSP tour. Represent the tour as a circular linked list of nodes, one for each point in the tour. Each Node contains two references: one to the associated Point and the other to the next Node in the tour. Each constructor must take constant time. All instance methods must take time linear (or better) in the number of points currently in the tour. To represent a node, within Tour.java, define a nested class Node: private class Node { private Point p; private Node next; } Your Tour data type must implement the following API. You must not add public methods to the API; however, you may add private instance variables or methods (which are only accessible in the class in which they are declared). public class Tour // Creates an empty tour. public Tour() // Creates the 4-point tour a→b→c→d→a (for debugging). public Tour(Point a, Point b, Point c, Point d) // Returns the number of points in this tour. public…arrow_forwardALL TRUE OR FALSE QUESTIONS 1. A "deque" allows an application to enqueue and dequeue from both front and rear of a queue. 2. The Queue ADT of the text is defined to hold elements of type Objec 3. Java supports inheritance of interfaces. 4. The text's array-based queue implementations use the fixed-front approach. 5. If N represents the number of elements in the queue, then the dequeue method of the ArrayBoundedQueue class is O(1). 6. When an object of class LinkedQueue represents an empty queue, its rear variable is 0. 7. A standard linked list provides a good implementation of a "Deque". 8. When implementing a queue with a linked list, the front of the queue is also the front of the linked list. 9. Our LinkedQueue class implements the QueueInterface interface. 10. The text's array-based queue implementations use the floating-front approach.arrow_forwardProgramming Exercise 8 asks you to redefine the class to implement the nodes of a linked list so that the instance variables are private. Therefore, the class linkedListType and its derived classes unorderedLinkedList and orderedLinkedList can no longer directly access the instance variables of the class nodeType. Rewrite the definitions of these classes so that these classes use the member functions of the class nodeType to access the info and link fields of a node. Also write programs to test various operations of the classes unorderedLinkedList and orderedLinkedList. template <class Type>class nodeType{public:const nodeType<Type>& operator=(const nodeType<Type>&);//Overload the assignment operator.void setInfo(const Type& elem);//Function to set the info of the node.//Postcondition: info = elem;Type getInfo() const;//Function to return the info of the node.//Postcondition: The value of info is returned.void setLink(nodeType<Type>…arrow_forward
- 44 Computer Science In JAVA (not javascript) Build a class to encapsulate and implement the ADT of the problem below. Include instance variables, if it has public methods, and other classes if needed. Incude a test driver The ADT in this case is a Stack. Write the code for this stack. You are hired to help design software to help with a key train operation: processing food orders on a trip. Once the manager says that it is ok, train staff to walk from the back of the plane to the front taking everyone’s order. When they reach the front, they begin preparing those orders. Food orders are prepared in groups of 10, that being the number of cups that can fit onto a carrying tray. The first group whose food orders are prepared are those in the front of the plane (first class). The second group is the next 10 people further back in the plane and so on. You are in charge of developing a new application that will let train staff take food orders and then display those orders 10 at a…arrow_forwardJava Programming: There must be no error in the code. Attached is rubric with output it must show. Show the full code and the screenshot of the output in the terminal of Java. Create a Parser class that must have a constructor that accepts your collection of Tokens. We will be treating the collection of tokens as a queue – taking off the front. It isn’t necessary to use a Java Queue, but you may. We will add three helper functions to parser. These should be private: matchAndRemove – accepts a token type. Looks at the next token in the collection: If the passed in token type matches the next token’s type, remove that token and return it. If the passed in token type DOES NOT match the next token’s type (or there are no more tokens) return null. expectEndsOfLine – uses matchAndRemove to match and discard one or more ENDOFLINE tokens. Throw a SyntaxErrorException if no ENDOFLINE was found. peek – accepts an integer and looks ahead that many tokens and returns that token.…arrow_forward1 Implement a Queue Data Structure specifically to store integer data using a Singly Linked List. 2 The data members should be private. 3 You need to implement the following public functions: 4 1. Constructor: 5 It initialises the data members as required. 6 7 8 2. enqueue(data) : This function should take one argument of type integer. It enqueues the element into the queue and returns nothing. 3. dequeue(): It dequeues/removes the element from the front of the queue and in turn, returns the element being dequeued or removed. In case the queue is empty, it r 4. front (): 10 11 It returns the element being kept at the front of the queue. In case the queue is empty, it returns -1. 12 5. getSize(): 13 It returns the size of the queue at any given instance of time. 14 6. 1sEmpty(): 15 It returns a boolean value indicating whether the queue is empty or not. 16 Operations Performed on the Stack: 17 Query-1 (Denoted by an integer 1): Enqueues an integer data to the queue. 18 19 Query-2…arrow_forward
- Without using C++ queue STL, write a simple menu based selection to insert, delete, show andexit from queue.1. Create a class called Queue with member variable queueArr as integer queue array,integer rear and integer front to keep track both rear and front element in the queuearray.2. Define several member functions in Queue such as aa. constructor – initialize both rear and front to -1b. insert – receive an integer and check if queue is full, if not then insert the integerto the queue arrayc. delete – delete front element from queue if front is not equal to rear (empty)d. display – if rear is not equal to front, then print out the queue array.3. Write a main function to test the Queue class i. Create a class called Queue with member variable queueArr, integerqueue array, integer rear, integer front ii. a. Initialize rear and front to -1b. Receive an integer and check if queue is full, if not theninsert the integer to the queue arrayc. Delete front element from queue if front is not…arrow_forwardUsing C++ Without Using linked lists: Create a class AccessPoint with the following: x - a double representing the x coordinate y - a double representing the y coordinate range - an integer representing the coverage radius status - On or Off Add constructors. The default constructor should create an access point object at position (0.0, 0.0), coverage radius 0, and Off. Add accessor and mutator functions: getX, getY, getRange, getStatus, setX, setY, setRange and setStatus. Add a set function that sets the location coordinates and the range. Add the following member functions: move and coverageArea. Add a function overLap that checks if two access points overlap their coverage and returns true if they do. Add a function signalStrength that returns the wireless signal strength as a percentage. The signal strength decreases as one moves away from the access point location. Represent this with bars like, IIIII. Each bar can represent 20% Test your class by writing a main function that…arrow_forwardGiven the following specification of a front operation for queue:ItemType Front Function: Returns a copy of the front item on the queue. Precondition: Queue is not empty. Postcondition: Queue is not changed. 1. Write this operation as client code, using operations from the QueType class. (Remember,the client code has no access to the private variables of the class). 2. Write this function as a new member function of the QueType class. help me with complete codearrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning