PA 3: Deque, Queue, Stack and applications Due: ● Entire PA: January 28th (Tuesday, midnight 11:59 PM) ● PA Quiz: January 24th (Friday, midnight 11:59 PM) ● Checkpoint: January 24th (Friday, midnight, 11:59 PM) 100 points + possible bonus points In this assignment you will implement data structures that provide an implementation for three abstract data types: A double-ended queue, a stack and a queue. In addition, you will make use of the double sided queue to simulate a fitting room! Also, along the way you will get more experience with implementing Java interfaces and writing JUnit test cases. START EARLY! Style Requirements You will be graded on your code’s style: https://sites.google.com/eng.ucsd.edu/dsc30/resources/style-guide IntelliJ has a great plugin to check your style automatically. Use it! There are style considerations beyond indentation and such. ● Choose names for test methods and for variables that are descriptive and useful when you see them in test output. ● Consider writing helper methods if you repeatedly use the same set of statements. ● Use Javadoc comments for descriptions of your methods and classes and inline comments if the logic of your program is not captured by your variable names and the natural flow of code. Part 0 – Starter Code Starter Code Our starter code will be distributed from github. Now you need to create the private repo for your PA3. If you forgot how, please follow the same instructions from PA1. (Name your repo dsc30-pa3 instead). Follow the same steps from PA2 to make your new project and move the starting files. PA Quiz Take the PA quiz so we can check that you understood the write-up. You can take the quiz 5 times. We will take your highest score. Be sure that you have read the whole PA before starting the assignment! Due Friday at midnight. PA quiz is on canvas Overview Read the documentation for a Deque class, understand the responsibilities of each method required by the write up. Sketch a test plan for a class that implement these methods. Besides the requirements for the methods and constructor documented, for this assignment there is the additional requirement that this implementation must use a circular array to hold its elements. A circular array can be rather tricky to implement correctly! It will be worth your time to sketch it out on paper before you start writing code. You will of course need to create an array with a length equal to the capacity of the Deque object. You will use ArrayLists in this assignment. However there are a couple of subtleties to look out for when using an ArrayList instead of an array: ● Be careful with the difference between the ArrayList’s add method and its set method. You’ll almost certainly want to use set , not add . But this means that you must add capacity items to your ArrayList before you do anything else (i.e. in the constructor), or set will throw an IndexOutOfBounds error. ● Remember that no matter what size you initialize your ArrayList, it can always be increased, so be careful not to accidentally grow your ArrayList beyond your Deque’s capacity. If you only use set and not add , you should not run into this problem. You will want to have instance variables for the size of the Deque (how many data elements it is currently holding), and to indicate which elements of the array are the current front and back elements. Think about what the values of these instance variables should be if the Deque is empty, or has one element, or is full (has size equal to its capacity). And in each case, think carefully about what needs to change for an element to be added or removed from the front or the back. Different solutions are possible, as long as all the design decisions you make are consistent with each other. Important: Since deque is a generalized queue, all its operations (add, delete etc) must run in O(1), ASIDE FROM THE CONSTRUCTORS Part 1 – Deque Deque is a linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”. Let’s go over the methods here to see what they each do. ALL METHODS IMPLEMENTED SHOULD RUN IN CONSTANT TIME, ASIDE FROM THE CONSTRUCTORS. public Deque(int cap) throws IllegalArgumentException { Constructor will set the list to be a new arraylist with the size given. You also need to initialize head, tail and size. Throws IllegalArgumentException if cap in less than 0. public Deque() throws IllegalArgumentException { Constructor will set the list to be a new arraylist with the default size of 5. You also need to initialize head, tail and size. You don’t need to throw an exception for this constructor. public int capacity(){ Returns the capacity of the Deque, that is, the maximum number of objects it can hold. public int size() { Return the current size of the Deque public boolean isEmpty() Return true if Deque is empty public boolean isFull() Return true if Deque is full public boolean addFront(Integer i) throws NullPointerException { Adds the specified element to the front the Deque. Throws NullPointerException if specified element is null. Returns true if element was added, and false if it could not add the element (if there was no space for the element to be added). Make sure to update instance variables as needed. public boolean addBack(Integer i) throws NullPointerException { Adds the specified element to the back the Deque. Throws NullPointerException if specified element is null. Returns true if element was added, and false if it could not add the element (if there was no space for the element to be added). Make sure to update instance variables as needed. public Integer removeFront() { Remove from the front of the Deque and return the data that was there. Return null if empty. public Integer removeBack() { Remove from the back of the Deque and return the data that was there. Return null if empty. public Integer peekFront() { Return the element at the front of the Deque without removing it. Return null if empty. public Integer peekBack() { Return the element at the back of the Deque without removing it. Return null if empty. Part 2 – MyQueue Now that you have your Deque built and tested, you will use it to implement a Queue. Read and understand the specification in MyQueue.java. If Deque is already implemented and tested and debugged, defining MyQueue is quite easy. Note that the methods required by the MyQueue class are different from, though closely related to, the Deque methods. Use the Adapter Pattern! That is, in your MyQueue class, create an instance variable of type Deque (instantiated to a Deque) and use it to perform all of the necessary Queue methods. If this class is complicated, you’re overthinking it. As is often the case when the Adapter pattern is used, if the adapted class (Deque in this case) is tested and debugged, the adapting class shouldn’t need much testing, because almost all of the work is being handled by delegation to the adapted class’s methods. Here are the methods you need to write: public MyQueue() Creates a new instance of MyQueue using the class Deque. public MyQueue(int maxCap) Creates a new instance of MyQueue with the given size using the class Deque. public int capacity() Returns the capacity, similar to the method from Deque. public int size() Return the current size, similar to the method from Deque. public boolean isEmpty() Return true if MyQueue is empty public boolean isFull() Return true if MyQueue is full public boolean enqueue(Integer i) Adds the specified element to the tail of this queue using methods from Deque. public Integer dequeue() Removes the element at the head of the queue using methods from Deque. public Integer peek() Return the element at the hea
d. Part 3 – Deque (Queue) Application – Fitting Room Interesting read about real life queues: (Link) public static String timeInfo (int[][] customers, int numberOfChangingRooms, int closingTime) Method returns a string that contains information about total time for checking out all customers before bookstore closes, changing room idle time and wasted time of all rejected customers. Imagine you are managing the bookstore’s clothing section. Everything seems to be going well except there are a lot of people that are in love with your clothes and want to try them on. You can only have a limited number of fitting rooms in the store. People need to form a line and wait in line until it’s their turn to go in and try the clothes on. Because you love Java and DSC 30 (we love you too!), you decide to write some code in Java to simulate the process and see how long it takes for everyone in line to try their clothes on. To better understand how the logistics work, let’s go into details and do some examples: Details: ● There is one big line that all customers wait in. Each customer could bring shoes, shirts and pants to try on. They can have none or multiple of each. For example, a customer could bring 2 shoes, no shirts and 1 pants to the fitting room. ● It takes 1 minute to try a pair of shoes on, 2 minutes to try a shirt on, and 3 minutes to try a pair of pants on. It also takes 1 minute for a customer to go in and set up the fitting room for themselves. ● You could have 1 or more fitting rooms in the store. The number varies in different tests! ● The store has a closing time. At closing time, all fitting rooms must be empty. However, it’s impolite to ask customers to leave when they are in the fitting room. Therefore, if you know the customer cannot finish trying clothes by the closing time, you should not allow the customer to use the fitting room. In addition, you should reject all customers that are still waiting in the queue after the store closes. ● You need to keep track of three things: total time, idle time and wasted time. Total time is the amount of time that the store is open and operating for. Idle time is the summation of the time each room was empty. For example if room 1 has been empty for 4 minutes, room 2 has been empty for 3 minutes and room 3 has never been empty, idle time is 4+3+0 = 7 minutes. Wasted time is the summation of the expected time of all customers who are being rejected to use the fitting room. For example, if the closing time is 3 minutes, and customers in queue are expected to take 5, 6, 7, 8 minutes respectively, all customers in the queue will be rejected to enter the fitting room since they cannot finish before the store closes. In this case, the wasted time is 5+6+7+8 = 28 minutes. Examples (If you get confused, take out a piece of paper and draw these examples as you read them.) 1. Imagine there are only 2 customers in the line and there is only 1 fitting room with a closing time of 15 minutes. Customer one has 2 pairs of shoes, 1 shirt and 1 pair of pants. We will be writing this as [2,1,1]. Customer 2 has no shoes, 3 shirts and no pants, represented as [0,3,0]. Let’s begin: Customer 1 goes into the fitting room and sets up the room (1 minute). They try 2 pairs of shoes (2 minutes), 1 shirt (2 minutes) and 1 pair of pants(3 minutes). After being inside for 8 minutes, they come out. Customer 2 goes in since this customer can finish before the store closes. They set up the fitting room (1 minute) and try 3 shirts on (6 minutes). After 7 minutes, they come out. So it took 8+7 = 15 minutes for everyone in line to try their clothes on. Idle time is 0 minutes here as the only fitting room was never empty. Wasted time is also 0 minutes since no one was rejected. 2. Now imagine there are 2 fitting rooms and 3 customers, with a closing time of 10 minutes: customer1: [1,2,1], customer2: [2,2,0], customer3: [1,0,2] Customer 1 goes into the first fitting room and customer 2 goes into the second one. Customer 1 needs ( 1 (set up) + 1*1 (shoes) + 2*2 (shirts) + 1*3(pants) = 9) minutes. Customer 2 needs ( 1 (set up) + 2*1 (shoes) + 2*2 (shirts) + 0*3(pants) = 7) minutes. So let’s fast forward 7 minutes. Customer 1 still needs 2 more minutes and customer 2 is done. So now we need to handle customer 3. Customer 3 needs ( 1 (set up) + 1*1 (shoes) +0*2 (shirts) + 2*3(pants) = 8) minutes. However, we only have 10-7 = 3 minutes left, so this customer is rejected. Fitting room 2 is empty now since no more customers are waiting in the line. Let’s fast forward 2 minutes. Customer 1 is done and get out. There is no one in the line anymore, so fitting room 1 is empty now. Now we only have 1 minute left, and both fitting rooms are empty. The total time to have everyone try their clothes on is identical to the closing time, which is 10 minutes. The idle time is 4 minutes since fitting room 1 is empty for 1 minute (10 min) and fitting room 2 is empty for 3 minutes (8, 9, 10 min). The wasted time is 8 minutes, since customer 3 with 8 minutes was rejected. 3. As our last example, imagine there are 2 fitting rooms and 6 customers, with a closing time of 15 minutes. customer1: [1,1,2], customer2: [1,2,0], customer3: [1,1,5], customer4: [4,0,0], customer5: [1,1,0], customer6: [3,2,0] Output: With 3 rooms, the total time for everyone to try on their items was 15 time units with idle time of 5 time units and wasted time of 27 time units Here is the link that walks you through this example: https://drive.google.com/file/d/14_-dCMJMT0xV-Q02WW2m7WlEDKMcS9cD/view?usp =sharing Now that we know how the logic works, let’s see how we code it: ● Each fitting room is going to be a queue from the class MyQueue. So you would need an array of those queues to hold all the fitting rooms. There is a variable called changingRooms that would do this for you. Your method gets the number of fitting rooms as an input argument called numberOfChangingRooms. ● REMEMBER: Each fitting room queue needs to be initialized with a specific size value. If you don’t allow for enough space, your queue will be missing data. ● Each customer could bring shoes, shirts and pants to try on in the fitting rooms. So each customer is going to be an int array with 3 values that represent shoes, shirts and pants in this order. For example, one customer could be represented as [1,1,2]. This means, they are bringing 1 shoes, 1 shirt and 2 pants to try on. ● Your method will get all the customers in an array of int arrays (int[][]). ● Using the array of int arrays, you need to form the line. The variable customersQueue is there for you to use it! ● Now that you have the line of customers formed and you have all your fitting rooms created in an array, let’s start solving the problem: ○ At every minute, assign the next customers in line to the empty rooms if any rooms are empty. If you find this customer unable to finish before the store closes, reject this customer and proceed to the next customers in line. ○ Then take one minute from each customer in each room and add one minute to the total time. ○ For every empty room, make sure you add one minute to idle time ○ Do the above steps until there is no one else in the line and in the fitting rooms There are two helper methods for you to use. One finds the first empty room for you and returns null if all rooms are full and the other one returns true if the store if fully empty (meaning customers line and all fitting rooms are empty), false otherwise. You should return a String that matches the format “With {# rooms} rooms, the total time for everyone to try on their items was {total time} time units with idle time of {idle time} time units and wasted time of {wasted time} time units” Make sure this matches exactly. Ex: With 3 rooms, the total time for everyone to try on their items was 15 time units with idle time of
12 time units and wasted time of 19 time units More tests: Input Output Customers # Fitting rooms Closing time Total time Idle time Wasted time [ [1,0,4] , [0,2,0] , [0,1,2] , [3,2,0] ] 2 20 20 12 8 [ [1,0,4] , [0,2,0] , [0,1,2] , [3,2,0] ] 2 22 22 8 0 [ [1,0,4] , [0,2,0] , [0,1,2] , [3,2,0] ] 4 10 10 18 14 [ [1,1,2] , [1,2,0] , [1,1,5] , [4,0,0] , [1,1,0] , [3,2,0] ] 1 35 35 0 17 [ [1,1,2] , [1,2,0] , [1,1,5] , [4,0,0] , [1,1,0] , [3,2,0] ] 3 14 14 9 19 [ [1,1,2] , [1,2,0] , [1,1,5] , [4,0,0] , [1,1,0] , [3,2,0] ] 3 20 20 8 0 [ [1,1,2] , [1,2,0] , [1,1,5] , [4,0,0] , [1,1,0] , [3,2,0] ] 4 18 18 39 19 [ [1,1,2] , [1,2,0] , [1,1,5] , [4,0,0] , [1,1,0] , [3,2,0] ] 4 20 20 28 0 Part 4 – MyStack (ExtraCredit) Using the class MyQueue that you implemented before, you will be making the class MyStack which would work as you expect a stack to work. Here are the methods you need to implement: public MyStack() Creates a new instance of MyStack using the class MyQueue. public MyStack(int maxCap) Creates a new instance of MyStack with the given size using the class MyQueue. public int capacity() Returns the capacity, similar to the method from MyQueue. public int size() Return the current size, similar to the method from MyQueue. public boolean isEmpty() Return true if MyStack is empty public boolean isFull() Return true if MyStack is full public boolean push(Integer i) Adds the specified element to the top of this stack using methods from MyQueue. public Integer pop() Removes the element at the end of the queue using methods from MyQueue. public Integer peek() Return the element at the head. Submission Checkpoint Submission January 24th (Friday, midnight, 11:59 PM): Files to submit: ● Deque.java ● DequeTest.java Final Submission: Files to submit: ● Deque.java ● DequeTest.java ● MyQueue.java ● MyQueueTest.java ● BookstoreFittingRoom.java ● MyStack.java (optional) To submit your files, you will need to push your code to your private Github repo first, then turn in those files on GradeScope by selecting Github as the submission method. After you submit your files to GradeScope, wait for the output of submission script. Make sure you see this after your submission: THIS IS A SUCCESSFUL SUBMISSION. YOUR SCORE WILL BE UPDATED ONCE GRADED. Otherwise, please fix the error and resubmit your files.
