Homework answers / question archive / CS351: Data Structures & Algorithms In this homework you will implement a queue using a circular buer

CS351: Data Structures & Algorithms In this homework you will implement a queue using a circular buer

Computer Science

Share With

CS351: Data Structures & Algorithms

In this homework you will implement a queue using a circular buer. The textbook describes
the technique on pages 383{393 (3rd ed. pp. 372{382), but we change the data structure somewhat.
You will also complete the implementation of a multi-threaded check-out simulation system that
uses your ADT.
Use this link to accept the assignment:
https://classroom.github.com/a/t73ZR6ps
1 Queue ADT
For this assignment, a Queue will provide the following operations:
boolean isEmpty() Return true if the queue is empty.
int size() Return the number of elements in the queue.
E front() Return the element at the front of the queue.
void enqueue(E) Add something at the back of the queue. The argument cannot be null.
E dequeue() Remove the front element from the queue and return it.
If one tries to access or remove the front element when the queue is empty, a NoSuchElementException
exception should be thrown.
We dene an interface for this ADT. It is in the JAR le.
2 ArrayQueue Class
In this assignment you will implement a ArrayQueue class that has the interface described above.
We provide a skeleton le for ArrayQueue.java
The data structure for this assignment is a circular buer built using dynamic arrays. The
implementation makes use of three elds:
data An array of values.
head The index of the rst queue value.
tail The index of where the next queue item is to be added.
It does not (and must not) include a manyItems eld (as in the book's implementation).
Spring 2023 page 1 of 4
CS 351: Data Structures & Algorithms Homework #7
3 Simulation and Threads
Queues are often used in simulation. We provide a supermarket checkout simulation that uses
the Queue ADT, with a few methods of the key class CashRegister left out. Complicating this
assignment: the simulation is multi-threaded. Each cash register is one thread, the simulation as a
whole is another thread (which generates shoppers) and nally the graphical display is yet another
thread.
The simulation works by having the cash register wait for the amount of time it takes to check
out the shopper (by calling Clock.pause). But it would be boring to watch the simulation go at
the natural speed. Thus the Clock class denes a \time dilation" parameter that starts at 600:
hence ten minutes of simulation time takes a second of real time.
The time dilation and many other parameters can be controlled from the command line (or by
setting Program Arguments in Eclipse). The default values of parameters shows that the limit on
items for the express line means that few shoppers can use it, reducing productivity. A simulation
engine would be used to try to nd a better conguration of registers, or to set the maximum number
of items dierently. An optional exercise for this Homework is to discover a more productive use
of parameters that doesn't cause the queues to get arbitrarily long. (Shoppers don't like that!)
Accessing (and mutating!) data structure from multiple threads is fraught with diculties.
To avoid these, the Queue data structure must only be accessed from the UI thread (AWT Event
Thread). In order to make this somewhat easier, we provide two static methods for executing code
on the correct thread. For example, if one wanted to nd out if the queue was currently empty,
one could write:
boolean wasEmpty = Utilities.computeUI(new Supplier<Boolean>(){
public Boolean get() {
return queue.isEmpty();
}
});
The computeUI method is used when you want a value back from the other thread; otherwise, use
invokeUI.
Of course, by the time the example code returns, the queue might not be empty any more
(hence the name wasEmpty). You don't need to know any more about threads (threads are the
topic of other courses here at UWM). We're having you write this code to get experience in writing
anonymous classes. (Each Runnable or Supplier instance is actually an instance of an anonymous
class that implements the respective interface.)
3.1 Concerning Lambda Expressions
While the code above is perfectly functional to instantiate an anonymous class and pass it as an
argument, it is perhaps a cumbersome syntax for doing so. You may notice that the Supplier and
Runnable interfaces are rather simple constructions: they declare a single method to be dened by
any classes that implement them. Since Java 8, we now have a handier syntax for instantiating such
a single-method class. It's called the lambda expression, and it allows us to shorten the previous
piece of code as follows:
boolean wasEmpty = Utilities.computeUI( () -> queue.isEmpty() );
The anonymous function we are passing as the argument is now assumed by the compiler to
dene the only method in the contract of Supplier. You may ask how it knows to use the Supplier
Spring 2023 page 2 of 4
CS 351: Data Structures & Algorithms Homework #7
interface instead of Runnable or some other class. We will leave it up to you to investigate Oracle's
documentation on lambda expressions and their usage of target typing. We use lambda expressions
extensively in our tests, as you ma have noticed.
3.2 Concerning Results
A simulation needs to convey its results so that they can be examined and compared against reality
or against a metric (such as a cost metric) to determine the appropriateness of the metric. The
simulation program here has two ways to convey information: rst of all, it has a graphical views of
the current state of the simulation: the express lane is red, the other lanes black; so-called \smart
shoppers" (who consider the number of items in the queue, not just the number of shoppers in
the queue when trying to nd the best queue to join) are green, others are gray. The size of the
rectangle for a shopper indicates how many items the shopper has in their basket. Each register is
annotated with its productivity: the percentage of time spent working on customers, rather than
idle.
4 What You Need To Do
You need to implement the ArrayQueue class with the data structure specied (one array, two index
variables). We use a tail index that points to the next available space, rather than to the last item
in the queue, as the book does. Do not copy code blindly from the book! Your code should use if
sparingly: only in the nextIndex helper method, to check for errors and in the ensureCapacity
method. The methods all should be ecient. The skeleton le for ArrayQueue.java includes
comments where if and loops are permitted.
For ArrayQueue, we have internal tests (mainly the invariant), normal tests (TestArrayQueue),
random tests and eciency tests.
You also need to complete the simulation program by completing the following four methods
from CashRegister.java:
enqueue Add a shopper to the queue.
getLength Return the length of the queue.
getTotalItems Return the total number of items of all of the shoppers in the queue for this
register.
run Process shoppers in the queue pausing to simulate the time needed to perform the checkout
procedure.
These methods are trickier than at rst glance because the queue can only be accessed from the
UI thread. Also, the queue does not have iterators of any kind: in order to look at all the items in
the queue, it is necessary to copy it (using clone) and destructively process the copy.
For the CashRegister class, we provide TestCashRegister. These tests, especially those that
interest with the thread, are much more involved than our normal tests. They require that the
Clock class behave dierently during testing, and they make extensive use of threading. The \run\
tests (testXn and testYn) pass an series of groups of shoppers, for example:
{{s1}, {}, {}, {s2,s3,s4}, {}}
Spring 2023 page 3 of 4
CS 351: Data Structures & Algorithms Homework #7
In this test, at the start, shopper 1 is waiting in the line, then when they are done, there are two
time periods when nothing happens, and then three shoppers show up at once, and in the next time
slot no one else comes, which is helpful since the cashier won't have nished all three shoppers yet.
When the simulation ends, three of the shoppers will have been served (with a total of six items)
and the cashier will have had two times to rest. This expectation is why the test has the following
assertions:
assertEquals("2 rests and 6 items", simulationTime());
assertEquals(3, completedShoppers());
The tests can be dicult to debug with a normal debugger, because they depend on actions in
several dierent threads. For this reason, we recommend that you use the simple logging system
for this assignment. You should enable the logging system by adding
-Dedu.uwm.cs351.util.Log.enable=true
as a VM Argument. Then write Log.println(...) when you want to print something. This will
work better than using System.out because it will prevent messages from dierent threads form
being mixed up. The logging system also shows the simulation \time" when printing.
5 Files
We provide the following les (among others) in your homework7.git repository:
src/edu/uwm/cs351/util/ArrayQueue.java The skeleton le.
src/edu/uwm/cs351/CashRegister.java A skeleton le for the CashRegister object in the
supermarket simulation.
src/edu/uwm/cs351/Simulation.java The main program.