COMP – 10205 – Data Structure and Algorithms

You are to write a program that will attempt to optimize the time it takes to process customers in check-out lines inside a grocery store. You will use the Queue data structure for this assignment.The general idea is to always place customers in the best checkout line possible. This will be based onthe total number of customers and the number of items in each cart being processed. The time to servea single customer is calculated by the following formula:t = 45 + 5*ni;where: t, time in seconds that it takes to serve a customer,ni, the number of items in the customers cart.A store consists of 1 or more check-out lines defined by:• n = number of normal check-out lines• f = number of express check-out lines (less than or equal to x items)A store could have up to 4 fast check-out lines.Customers at the store may have many items in their cart or only a few. Each new customer will beadded to the check-out line with the cumulative least amount of time in front of it (the shortest line).Any customer may optionally enter one of f express lines if they have less than or equal x items in thecart. It should be noted that they do not need to enter an express line if another check-out line wouldresult in a shorter service time. Customers with more than x items must enter one of the other n check-out lines in the store. The total number of check-out lines will be equal to n + f;Example CaseExample Data: x = 10, n = 2, f = 1 and 8 customers and carts come to the checkout in the followingorder: 6,7,45,10,11,21,2,4 (the number is the number of items in the cart). You can assume they allarrive at the check-out at the same time for this lab. When placed into the optimum check-out line thefollowing check-out lines (queues) will result. Part AYou need to output your optimum starting case for all of the check-out lines in the store and thencalculate the amount of time it will take for the store to be empty of all customers. Your output mustshow each Queue in order. An example output is shown below:Part BSimulate the removal of customers from each check-out by servicing the customers. It is suggested youset up a loop to calculate the state of the Checkout lines after each second, but only display lines every30 or 60 seconds simulated. Once the amount of time has passed required to service the customer atthe start of the Queue, the customer must be removed and processing will continue with the nextcustomer. For the above case we would start at time = 0 and continue until time = 330 s at which pointall customers would have been serviced. It is suggested that you not show the output after everysecond, but instead after every 30 or 60 seconds. The example below shows every 60 seconds for thesame data that was used in part A. In your solution you must use a simulation step of 30 seconds.Suggested Steps:1. Create a new project in IntelliJ.2. Add the example data (Customer_Example.txt) and evaluation data set (Customer.txt) to theproject.

3.AddatoStringmethod to theLinkedQueue.javathat will print all the items in the Queue on a

single line.4. Add a new class to the project to hold each Customer. Add a property for the number of itemsin the cart and a method to calculate how long it will take to serve a customer and any otherproperties and methods you feel are appropriate.5. Override the toString method to display the contents of the object neatly (in my example theCustomer will print the number of items and the time it will take to serve a customer).6. Inside the main class you will need to create a LinkedQueue for each of the checkout lines.You will also need to track the current wait time for each queue.7. Read the check-out line and customer information from the data file and add them to thecorrect Queue.8. Output your results for Part A and verify the test case and the Customer data case.9. Solve Part B by using a loop to process all the lines simultaneously one second at a time.Remove the customer when the loop counter equals the time to process for that check-out line.