Problem Solving with C++ (10th Edition)
10th Edition
ISBN: 9780134448282
Author: Walter Savitch, Kenrick Mock
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
C++
A queue is essentially a waiting list. It’s a sequence of elements with a front and a back. Elements can only be added to the back of the queue and they can only be removed from the front of the queue. Elements are kept in order so that the first element to enter the queue is the first one to leave it.
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++ (10th 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
- Java All classes must be named as shown in the above UML diagram except the concrete child classes. The ItemList is a singly-linked list with the following methods: • insert(index: int, item: Item) : boolean o Inserts the given item at the given index if an equal item is not already in the list. If the method is successful it returns true. If an equal item already exists in the list or the index is out of range, this method returns false. • add(item: Item): boolean o Adds the given item to the front of the list. Returns true if successful and false if an equal item is already in the list. • set(index: int, item: Item) : Item o Replaces the object in the list at the given index with this object. If the index is out of range or the given item is already in the list, the method returns null. If the operation is successful, the method returns the object that was replaced by this one. • delete(index: int) : Item o Deletes the object at the given index from the list. If the index is out of…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_forwardTour.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_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_forwardThis one in c++.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_forward
- This in c++.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_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
- JAVA CODEarrow_forwardWithout 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_forwardJavaWrite a program that implements the methods of a list using the operations of each ADT. Making use of Inheritance and Polymorphism. Create the stack (STACK) and queue (QUEUE) derived classes and implement their methods as indicated in the book.In the main program place a main menu with three options 1. List, 2. Stack and 3. Queue and in each option show the use of the operations of each ADTarrow_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