Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Algorithms and Data Structures I

Project 4: Simulation Theory

Background

Computer programs are often used to simulate real-world scenarios to gain useful insights. In this lab, we are going to simulate a literal queue using the Queue ADT that we just learned about in class. The simulation will handle Customers who are waiting in line to be served (at a bank, coffee shop, airport security, you name it).  Each Customer has a predefined “transaction time” that represents how long the customer will keep the clerk busy for. You can think of this as how long the Customer spends at the counter.

Exercise

Queue.java

Your first job is to implement a doubly-linked list that implements the interface defined in QueueInterface.java. Remember, doubly-linked lists contain Nodes that reference both their next Node and previous Node:

Each of the method definitions comes with a comment that explains what the method’s inputs are, what the method should do, and what it should return. It is important that you implement a generic Queue and not a Queue. You will be graded on generic Queues that use other data types besides Customer.

WaitLine.java

After your Queue class is implemented, you can use it to complete the implementation for Wait Line.java.   WaitLine is a subclass of Queue that also implements the WaitLineInterface, that is, your class definition should look exactly like this:

public class WaitLine extends Queue implements WaitLineInterface {

A WaitLine represents the line that customers are waiting in. Classes that implement the WaitLineInterface are responsible for counting the number of Customer arrivals, number of Customers served, and cumulative waiting time of all served Customers. The WaitLineInterface is explained thoroughly in the comments in Wait LineInterface.java. Remember, the WaitLine class can call Queue methods, so you shouldn’t have to reinvent any Queue-specific logic.

Starter Code

All of the starter code you need is located here. The starter code is as follows:

- Project4.java: The actual simulation. Uses a WaitLine object to represent a line of Customers.

Simulates 10 minutes of time. At each second, there is a 10% chance a new Customer will arrive.

When a Customer gets to the counter, their transaction will take a random amount of time between 0 and 30 seconds.

- QueueInterface.java: The methods that your Queue.java class must implement. Must work for generic types (T) and not just Customers. More instructions in the interface comments.

- WaitLineInterface.java: The methods that your Wait Line.java class must implement. The WaitLine class extends the Queue class, so the WaitLine class will only work for Customers.

- Customer.java: Class for a single Customer. Stores three ints: Customer ID, arrival time (what time they arrive in the line), and transaction time (how long they will be at the counter)

- EmptyQueueException.java: The exception that your Queue class must throw if dequeue() or getFront() are called when the Queue is empty.

Sample Output

- P4Out.txt: Provides sample output for a successful run of Project4.java. Your output will not exactly

match this since there are many random numbers at play, but your output should resemble this (i.e. > 0 customers served, > 0 customer arrivals, average wait time somewhere between ~50-200s).

Deliverables

You are responsible for submitting the following completed implementations:

- Queue.java: Implementation of the QueueInterface according to the comments in QueueInterface.java.

- WaitLine.java: Implementation of the WaitLineInterface according to the comments in Wait LineInterface.java