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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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:

 

1. Create a Stack data structure to store and retrieve objects

2. Create a Queue data structure to store and retrieve objects

3. Use the PriorityQueue class to store and retrieve objects

4. 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

1. 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.

 

1. 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

2. Finish the Restaurant, StackRestaurant, QueueRestaurant, and Prior- ityQueue. Be sure to properly update

3. 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

1. 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.

2. 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

3. If you complete the above instructions during lab, you may have your imple- mentation checked by one of the

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of