Introduction
In this lab, you will experiment with two common data structures: stacks and queues. In particular, you will use the PriorityQueue class from the Java Collections Frame- work and will implement a stack and queue yourself. You will also be creating and using generic classes.
Learning Objectives
By the end of this laboratory exercise, you should be able to:
Create a Stack data structure to store and retrieve objects
Create a Queue data structure to store and retrieve objects
Use the PriorityQueue class to store and retrieve objects
Create and use Generic Classes and Methods
Proper Academic Conduct
This lab is to be done individually. Do not look at or discuss solutions with anyone other than the instructor or the TAs. Do not copy or look at specific solutions from the net.
Preparation
Import the existing lab8 implementation into your eclipse
Download the lab9 implementation from
In Eclipse, select File/Import
Select General/Existing projects into workspace. Click Next
Select Select archive file. Browse to the lab9.zip file. Click Finish
Class Design
Below is the UML representation of the set of classes that make up the implementa- tion for this lab.9
The key classes in our project are:
Order: class representing an order at a The class has two variables: the description of the order (i.e. what it is) and the timeOrdered marking when the order was made. Some getters are made, and the toString always returns the description. The constructor takes in a description and a timeOrdered as an int which the order should store. The compareTo() in Order should compare order by timeOrdered i.e it should return -1 if this ticket was created before the other ticket; 0 if this ticket was created at the same time as the other ticket; 1 if this ticket was created after the other ticket.
This will look very similar to the Order class from the previous lab, but keep in mind that this is now a generic type. Instead of having a String be the description for an Order, the description can now be of any class! Which class that is is determined by the generic type (T in this case).
How does the ArrayList know what type of things it will store? This is done via generics. Now, you will be creating a generic class for Orders. Similar to the code for ArrayLists, you may have lines such as:
You should note that the restaurant classes are also now generic. This is done to allow them to store orders of different generic types. For more information on how to handle generics, you should see the link in the hints below.
Restaurant: An abstract class representing a restaurant. A Restaurant is expected to store a list of orders, and provides methods for adding and removing Subclasses define how orders are stored and removed. In addition, some methods are added to get additional information about the Restaurant or add public accessibility. The following methods defines how it works:
addOrder(): Abstract method. Implementing classes should add the order passed in into an internal data I.e. the order should be stored in some way.
numberRemainingOrder(): Abstract method. Implementing classes should return an int indicating the number of orders that are stored in some in- ternal data
checkNextCompletedOrder(): Abstract method. Implementing classes should return the order that will next be That is, get the order that would be returned by completeOrder without actually com- pleting the order.
getCurrentStatus(): returns some In particular, returns in- formation on the current number of orders stored and what order is next.
completeOrder(): Abstract Method. Implementing classes should com- plete an order by updating the underlying data structure of the Each restaurant uses this function to determine the order in which order
are completed. Once an order has been completed, it should be consid- ered to be removed from the restaurant. An order may not be completed twice. A completed order symbolizes a meal that has been prepared and delivered to a customer.
completeOrder(): public method providing utility to other classes to re- move the next order from the internal data Also computes the time since the order was created to the given time that the order was completed and returns information based on this.
StackRestaurant: An implementation class of A StackRestau- rant stores orders in a Stack orderList. The spaces in which elements may be inserted is defined by orderList, but what is actually in the stack is defined by its start and end indices (locations inside the orderList). See the code com- mentary and the link in the hints section to better understand what you should do to complete this class. This is not much different from the StackRestaurant class you have implemented previously but don’t forget about generics.
Stacks are a “Last In - First Out” or “LIFO” data structure. This means that the last element added to a stack is the first one that is removed from it. e.g. we add the elements A,B, and C to a stack in that order (“pushing” the values onto the stack). We then remove 3 elements (“popping”) from the stack. They will be removed in the order c, B, A.
The StackRestaurant completes orders in a LIFO ordering. The overridden abstract methods should reflect this.
QueueRestaurant: An implementation class of Restaurant. A QueueRestau- rant stores orders in a Circular The spaces in which elements may be inserted is defined by orderList, but what is actually in the queue is defined by its start and end indices (locations inside the orderList). See the code com- mentary and the link in the hints section to better understand what you should do to complete this class. This is not much different from the QueueRestau- rant class you have implemented previously but this time your orderList is an ArrayList, and again, do not forget about generics.
Queues are a “First In - First Out” or “FIFO” data structure. This means that the first element added to a queue is the first one that is removed from it.
e.g. we add the elements A,B, and C to a queue in that order. We then remove 3 elements from the queue. They will be removed in the order that they were inserted in: A, B, C.
The QueueRestaurant completes orders in a FIFO ordering. The overridden abstract methods should reflect this.
PriorityQueueRestaurant: An implementation class of A Pri- orityQueueRestaurant stores orders in a PriorityQueue orderList. Queues are a “First In - First Out” or “FIFO” data structure. This means that the first element added to a queue is the first one that is removed from it. Priori- tyQueues are a bit different, however. These sort the elements based on some ordering. The first element to be removed is determined by which element has the ”highest” priority. Because this PriorityQueue stores orders, it uses the natural ordering of Order (the compareTo) to determine how to sort the orders.
e.g. we add the elements A,B, and C to a queue in that order. We sort these element by size. We say that the sizes are as follows: B = Large; A = Medium; C = Small. We then remove 3 elements from the queue. They will be removed in the order that they were inserted in: B, A, C.
Implementation Steps
Start from the class files that are provided in lab9.zip.
The Driver and Order classes have been fully implemented and their code should not be modified. The Assert, AssertException and QueueR- estuarantTest classes are also fully implemented and can be used as a refer- ences when implementing the other restaurant
Finish the Restaurant, StackRestaurant, QueueRestaurant, and Prior- ityQueue. Be sure to properly update
Implement the remaining tester classes, PriorityQueueRestaurant and Stack- RestaurantTest as specified in the
Hints
See the documentation for PriorityQueue. Keep in mind the methods for a Queue (poll, peek, add):
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
Stacks: https://en.wikipedia.org/wiki/Stack (abstract data type)
Circular Queues:
https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/
Java Generic Classes:
https://docs.oracle.com/javase/tutorial/java/generics/types.html
Example Output
Below is an example output of the full program. The details of your interaction will vary (we do not test the output of Driver).
. [ enter ] an order .
. [ complete ] an order .
. [ check ] the next order to be completed . 4 . [ quit ]
incorrect
Please choose a restaurant option : 1 . [ enter ] an order .
. [ complete ] an order .
. [ check ] the next order to be completed . 4 . [ quit ]
check
For the stack restaurant :
salad
For the queue restaurant :
cake
For the priority queue restaurant :
salad
Please choose a restaurant option : 1 . [ enter ] an order .
. [ complete ] an order .
. [ check ] the next order to be completed . 4 . [ quit ]
enter
Please enter an order description and an order time ( comma separated ) with the ›
following format :
,
sandwich , 2
Order added to Stack Restaurant Order added to QueueRestaurant
Order added to Priority QueueRestaurant Please choose a restaurant option :
. [ enter ] an order .
. [ complete ] an order .
. [ check ] the next order to be completed . 4 . [ quit ]
complete
Please enter the time of completion as an i n t : 5
The completion f o r the stack restaurant :
It tooks 3 time units to complete the following order : sandwich
The completion f o r the queue restaurant :
It tooks 2 time units to complete the following order : cake
The completion f o r the priority queue restaurant :
It tooks 4 time units to complete the following order : salad
Please choose a restaurant option : 1 . [ enter ] an order .
. [ complete ] an order .
. [ check ] the next order to be completed . 4 . [ quit ]
complete
Please enter the time of completion as an i n t : 5
The completion f o r the stack restaurant :
It tooks 4 time units to complete the following order : salad
Final Steps
Generate Javadoc using
Select Project/Generate ..
Make sure that your project (and all classes within it) is selected
Select Private visibility
Use the default destination folder
Click Finish.
Open the lab9/doc/index.html file using your favorite web browser or Eclipse (double clicking in the package explorer will open the web page). Check to make sure that that all of your classes are listed and that all of your documented methods have the necessary
If you complete the above instructions during lab, you may have your imple- mentation checked by one of the
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
