Lab 9: Queues

This lab will consist of two parts. The first part focuses on implementing a node-based queue. The second part uses your queue to simulate the checkout lines at a store.

To begin this lab, you should read these lecture slides to learn what a queue is. You should also review your notes and lecture material for information about linked lists.

Part I

1. Create a package lab.util
2. Add the classes Node, NodeIterator, and Queue to the package lab.util. Their APIs can be found here.
3. Complete the implementation of the Queue class:
   1. Your queue implementation must use a node-based linked sequence to represent the queue. The sequence is very similar to a singly linked list but does not need to provide all of the functionality of a linked list. You must use the provided Node class to implement the linked sequence. All of the required fields are already provided for you in the starter code.
   2. The constructor should create an empty queue. An empty queue has no front or back node, and its size is zero.
   3. The enqueue method should add a new element to the back of the queue, increasing the size of queue by one. It does so by adding a new node to the end of the sequence of nodes. Note that there are two cases that you must handle: (1) the queue is not empty before you enqueue the element, and (2) the queue is empty before you enqueue the element.
   4. The dequeue method should remove and return the element at the front of the queue, decreasing the size of the queue by one. It does so by removing the node at the front of the sequence of nodes.
   5. The peek method should return the element at the front of the queue without removing it. It does so by returning the element stored in the node at the front of the sequence of nodes.
   6. The size method should return the size of the queue.
   7. The isEmpty method should return true if the queue is empty and false otherwise.
4. Test your queue using the JUnit test QueueTest.

Part II

In this part of the lab you will create a class to simulate a checkout line. A CheckoutLine models a queue of customers in a simulation environment. A Cashier is a subclass of CheckoutLine that models the processing of customers through the checkout process.

There are many different strategies for managing queues of customers. The most common strategy is to have multiple checkout lines where the customers are free to choose which line to queue in. An alternate strategy is to have a single line for customers to queue in, and the customer at the front of the line is served by the first available cashier.

A simulation of these two strategies can be seen by running the following command from any computer in the Prism lab:

java -jar /cse/dept/www/course/classpath/1030/CheckoutSimulation.jar

The simulation generates customers that arrive at the checkout line(s) after random intervals of time, and each customer requires a random amount of cashier time to process their order. Each time you run the simulation, a new set of 100 customers is generated and passed through the checkout line(s). The amount of time needed to serve all of the customers is printed to the terminal. Which strategy seems to produce the shortest overall checkout time?

To reproduce this simulation, you need to:

1. Add the JAR file lab9.jar to your project.
2. Examine the Customer and CheckoutLine APIs found here.
3. Implement the CheckoutLine class. Starter code that you should use is available here.
4. Test your class using the JUnit test CheckoutLineTest.
5. Run the simulation. In the Package Explorer of Eclipse, under Referenced Libraries of your project, click on the triangle of lab9.jar and then click on the triangle of lab.util. Right click on CheckoutSimulation.class choose Run As..., and choose Java Application.

Submission instructions

• Submit your classes before Friday April 17, 4pm. To submit, log into a computer of the Prism lab (clips showing how to log in from home and transfer files can be found here).
• Transfer your Java classes to your EECS account (if they are not already there).
• Create a file named group.txt in the directory which contains the lab directory which contains the util directory which in turn contains the Java classes. Do not put the group.txt in the same directory as Java classes. Each line of the file group.txt contains the EECS login name of a member of the group.
• Submit your Java classes: Queue and CheckoutLine. Each class should be submitted separately as follows. Open a terminal and go to the directory that contains the file group.txt. In that directory, run the following command to submit your Queue class.

  submit 1030 lab9 group.txt lab/util/Queue.java
  

  If something fails, you may see something like

  submitted:  group.txt (17 bytes)
  submitted:  Queue.java (5934 bytes)
  All files successfully submitted.
  
  Note: lab/util/Queue.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  Your Queue class compiled successfully.
  queue size should be 1 expected:<1> but was:<0>
  java.lang.AssertionError: queue size should be 1 expected:<1> but was:<0>
  SUBMITTED FILE Queue.java HAS BEEN REMOVED.
  PLEASE SUBMIT AGAIN.
  

  Fix your code and submit again. If you successfully submitted your code, you will see something like this

  submitted:  group.txt (17 bytes)
  submitted:  Queue.java (5929 bytes)
  All files successfully submitted.
  
  Note: lab/util/Queue.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  Your Queue class compiled successfully.
  Your Queue class passed all the tests.
  Your code contains no style errors.
  
  Your group.txt file has been successfully validated.
  

• You can check which files you have successfully submitted by opening a terminal and running the following command.

  submit -l 1030 lab9
  

  After submitting your classes, you should see something like this

  The following files have been submitted:
  group.txt.submitted                              17 bytes
  Queue.java.submitted                           5929 bytes
  CheckoutLine.java.submitted                    3715 bytes
  

• If you run into problems with submitting your Java classes, please email franck@cse.yorku.ca.