CSE 12 Spring 2024 PA6 - Stacks and Queues with a Deque

There is an FAQ post on Piazza. Due date: Thursday, May 16 @ 11:59 PM PST

Learning goals:

• Implement a Deque data structure with generic types
• Implement a Stack and Queue data structure using a Deque
• Write JUnit tests to verify proper implementation

Testing and Implementation of Deque, Stack, and Queue [100 points]

In this part of the assignment, you will implement a Deque, Stack, and Queue and write JUnit tests to ensure that your implementation functions correctly.

Read the entire write-up before you start coding.

Download the starter code and put it in a directory in your working environment. You will find the following files:

+-- PA6
|    +-- DequeInterface.java		
|    +-- StackInterface.java
|    +-- QueueInterface.java
|    +-- MyDeque.java            **You will CREATE this file**
|    +-- MyStack.java            **Edit this file**
|    +-- MyQueue.java            **Edit this file**
|    +-- MyAlgorithm.java        **Edit this file**
|    +-- PublicTester.java
|    +-- CustomTester.java       **You will CREATE this file**

You will be creating the MyDeque, MyStack, and MyQueue classes that implement the given DequeInterface, StackInterface, and QueueInterface interfaces. Additionally, you will utilize one of these classes in the MyAlgorithm class. Note, we did not provide starter code for MyDeque.

Part 1: MyDeque

Deque is pronounced like “deck” /dɛk/ not “dequeue”.

Once you understand what the behavior of Deque is supposed to be, your next task is to create your own implementation of the provided DequeInterface called MyDeque.

⚠️DO NOT IMPORT AND USE JAVA'S BUILTIN DEQUE!!! If we see that you do use these functions, you will receive a zero. Furthermore, if we see you import any of the built-in data structure implementations that are not permitted you will not receive any credit (i.e. ArrayLists, Stack, Queue etc.)⚠️

• Create a file named MyDeque.java. Make sure the MyDeque class implements DequeInterface. MyDeque is a generic class. You only need to implement the methods stubbed out in the interface (also listed in the table below). You may also refer to descriptions for the same methods provided by the Deque javadoc.

Instance Variables

Note: Do not make any instance variables private, they should have the default access modifier. Do not add any other instance variables and do not add any static variables (other than private static final variables to be used as constants).

Instance Variable	Description
Object[] data	The underlying data structure of the Deque. Treat this as a circular array. For your reference on the expected behavior, view the diagrams for the add/remove methods below. Note: You don't need to check if the data array is null in any of your code. Note: null cannot be a valid element in your Deque. It is used to represent an empty space in the array.
int size	This variable should be equal to the number of valid elements in your data array. A valid element in data is an element in your Deque. Note: You may assume that nothing (other than possibly your own code) would change size to be something out of bounds of data (i.e., size >= 0 && size <= data.length will always evaluate to true, unless your code manually sets it to be something else).
int rear	This variable should be equal to the index of the last element in the Deque. When the Deque is initialized, `rear` will start at index 0.
int front	This variable should be equal to the index of the first element in the Deque. When the Deque is initialized, front will start at index 0. Note: rear and front can be equal to each other. This will happen when the Deque is empty or only has one element.

Method Descriptions

Method Name	Description	Exceptions to Throw
public MyDeque(int initialCapacity)	Initialize the Object array data with length of initialCapacity. Note: The capacity of the Deque is the length of the array, while size is the number of valid elements in the array.	Throw an IllegalArgumentExceptionif the initialCapacity is negative (< 0).
public int size()	Returns the number of elements that exist in the deque.	None
public void expandCapacity()	Doubles the current capacity. If the capacity is 0, set the capacity to a default value of 10. This method should preserve the current size and elements in the list. Elements need to be contiguous after expanding. This means the front needs to be 0 and rear should be at size-1 or 0 if there are no elements present.	None
public void addFirst(E element)	Before trying to add the element, check if the deque is at capacity and call expandCapacity if necessary. Add the specified element to the front of the deque and update front. Updates size accordingly.	Throw NullPointerException when element is null.
public void addLast(E element)	Before trying to add the element, check if the deque is at capacity and call expandCapacity if necessary. Add the specified element to the rear of the deque and update rear. Updates size accordingly.	Throw NullPointerException when element is null.
public E removeFirst()	Removes and returns the element at the front of the deque if there is such an element. If there are no elements in the deque, return null. Updates the relevant instance variables accordingly.	None
public E removeLast()	Removes and returns the element at the rear of the deque if there is such an element. If there are no elements in the deque, return null. Updates the relevant instance variables accordingly.	None
public E peekFirst()	Returns the element at the front of the deque if there is such an element. If there are no elements in the deque, return null.	None
public E peekLast()	Returns the element at the rear of the deque if there is such an element. If there are no elements in the deque, return null.	None

Removing the Final Element

Do not explicitly reset rear or front to 0 when removing the final element in the Deque.

Examples

Example of Circular Behavior

As stated earlier, the element is inserted into the next available space in the array. In this example, integers are elements in the deque (valid elements of data) and null represent unoccupied spots in data.

Statements on the left-hand side of the array should evaluate to expressions on the right-hand side.

deque.data -> [1, 2, 3, 4, 5] // capacity is 5
deque.size -> 5 
deque.front -> 0
deque.rear -> 4

deque.addFirst(0);
deque.data -> [1, 2, 3, 4, 5, null, null, null, null, 0] // capacity is 10
deque.size -> 6
deque.front -> 9
deque.rear -> 4

deque.removeFirst();

deque.data -> [1, 2, 3, 4, 5, null, null, null, null, null] // capacity is still 10
deque.size -> 5
deque.front -> 0
deque.rear -> 4

deque.removeFirst();
deque.data -> [null, 2, 3, 4, 5, null, null, null, null, null] // capacity is still 10
deque.size -> 4
deque.front -> 1
deque.rear -> 4

deque.addLast(6);
deque.data -> [null, 2, 3, 4, 5, 6, null, null, null, null] // capacity is still 10
deque.size -> 5
deque.front -> 1
deque.rear -> 5

Note: This example only shows how front wraps around. rear should wrap around too!

Tip: When determining the index for front and rear, you can try using the modulus operator % to wrap around to the next available space. You are not required to handle the wrapping in this way, you may use whichever implementation as long as the behavior is correct.

Example of Adding the First Element and Removing the Final Element

deque.data -> [null, null, null, null, null] // Deque initialized with a capacity of 5
deque.size -> 0
deque.front -> 0
deque.rear -> 0

deque.addLast(0);
deque.data -> [0, null, null, null, null]
deque.size -> 1  // size updated
deque.front -> 0 // front and rear unchanged
deque.rear -> 0

deque.addFirst(10);
deque.data -> [0, null, null, null, 10]
deque.size -> 2
deque.front -> 4  // front wraps around
deque.rear -> 0

deque.removeLast();
deque.data -> [null, null, null, null, 10]
deque.size -> 1
deque.front -> 4  
deque.rear -> 4   

deque.removeLast();
deque.data -> [null, null, null, null, null]
deque.size -> 0
deque.front -> 4  // removing the final element
deque.rear -> 4   // front and rear are NOT reset to 0

deque.addFirst(5);
deque.data -> [null, null, null, null, 5]
deque.size -> 1
deque.front -> 4  // we add at index 4
deque.rear -> 4

Example of ExpandCapacity

deque.data -> [3, 4, 5, 1, 2] // capacity is 5
deque.size -> 5 
deque.front -> 3
deque.rear -> 2

deque.expandCapacity();
deque.data -> [1, 2, 3, 4, 5, null, null, null, null, null] // capacity is 10
deque.size -> 5
deque.front -> 0
deque.rear -> 4

Diagrams for MyDeque

The following diagram shows one case where only 4 spaces in the array are occupied in the middle of the array. In this case, when we call addFirst, the element will be added to index 0. When we call removeFirst, we will remove the element at index 1. When we call addLast, the element will be added to index 5. And when we call removeLast, we will remove the element at index 4.

Note: Blue boxes represent a stored value while white boxes represent null.

MyDeque can also run into the situation where front > rear. This means that the front has wrapped around to the end of the array OR the rear has wrapped around to the beginning of the array. The following diagrams show how addFirst, removeFirst, addLast, and removeLast should behave in this situation.

addFirst when front > rear

removeFirst when front > rear

addLast when front > rear

removeLast when front > rear

Part 2: MyStack

An Abstract Data Type (ADT) only describes the functionality required and not how the implementation is to be accomplished. Since an ADT is implementation-independent, your next task is to implement the Stack ADT by using a Deque for your underlying data structure.

You will accomplish this in MyStack.java, which contains generic class MyStack that implements the Stack ADT. Our Stack ADT is defined in the generic interface, StackInterface.java.

Instance Variables

Instance Variable	Description
MyDeque<E> theStack	The underlying data structure of MyStack. You will use your implementation of the Deque ADT (in the form of a MyDeque<E> object) to manage your data. Note: null cannot be a valid element in the MyDeque<E> object, which is your underlying data structure. As such, null cannot be a valid element for theStack either.

Public Methods

Each of these non-constructor methods are already defined in StackInterface.java. You need to implement these methods using the MyDeque<E> object created in your constructor. There are a couple of ways to implement each method using the MyDeque<E> object. As long as the implementation you choose is consistent with all the other MyStack methods and the MyStack works as you would expect an implementation of the Stack ADT to work (LIFO ordering), you can choose anyway to use the MyDeque<E> object.

Method Name	Description	Exceptions to Throw
public MyStack (int initialCapacity)	Initialize a MyDeque<E> object with the parameter initialCapacity.	None
public boolean empty()	Checks whether or not the stack is empty. If it is empty, return true.	None
public void push(E e)	Pushes the specified element to the top of the stack.	None
public E pop()	Removes an element from the top of the stack. Returns the removed element, or null if there was no such element.	None
public E peek()	Returns the element at the top of the stack.	None
public int size()	Returns the number of elements in the stack	None

Note: When using a method from the MyDeque class, only use the methods outlined in the DequeInterface.java (i.e. removeFirst, addLast, size, etc). If you wrote helper methods in MyDeque, refrain from using them when implementing MyStack.

Part 3: MyQueue

Similar to the Stack ADT, the Queue ADT is implementation-independent. We can also implement a Queue using our Deque. In MyQueue.java, write the generic class MyQueue<E> to implement the given QueueInterface<E> interface in QueueInterface.java.

Instance Variables

Instance Variable	Description
MyDeque<E> theQueue	The underlying data structure of MyQueue. You will again use your implementation of the Deque ADT (in the form of a MyDeque<E> object) to manage your data. Note: null cannot be a valid element in the MyDeque<E> object, which is your underlying data structure. As such, null can't be a valid element for theQueue either.

Public Methods

Each of these methods are already defined in QueueInterface.java. You only need to complete implementation for these methods in your MyQueue class using the MyDeque<E> object created in your constructor. Again, there are a couple ways to use the MyDeque<E> object to implement each of these methods. Make sure whatever implementation you choose ensures that the proper behavior outlined by the Queue ADT is adhered to (i.e., FIFO ordering).

Method Name	Description	Exceptions to Throw
public MyQueue (int initialCapacity)	Initialize a MyDeque<E> object with the parameter initialCapacity.	None
public boolean empty()	Checks whether or not the stack is empty. If it is empty, return true.	None
public void enqueue(E e)	Adds the specified element to the back of the queue.	None
public E dequeue()	Removes an element from the front of the queue. Returns the removed element, or null if there was no such element.	None
public E peek()	Returns the element at the front of the queue.	None
public int size()	Returns the number of elements in the queue.	None

Note: When using a method from the MyDeque class, only use the methods outlined in the DequeInterface.java (i.e. removeFirst, addLast, size, etc). If you wrote helper methods in MyDeque, refrain from using them when implementing MyQueue.

Part 4: MyAlgorithm

Next let's use the Data Structures we've implemented in parts 2 and 3. In MyAlgorithm.java, implement the following method using MyStack or MyQueue.

Public Methods

Method Name	Description	Exceptions to Throw
public double avgDiffMonotonicIncreasing(int[] arr)	Returns the average difference between consecutive elements in the monotonically increasing subsequence starting from the first element in the array. This method should run in O(n) and pass through arr only once.	Throw NullPointerException when arr is null.

Monotonically Increasing Subsequence Examples

The monotonically increasing subsequence will always contain the first element of the array, if it exists. Later elements in the array are added to the subsequence if they are larger than the element last added to the subsequence. Follow this logic when adding elements to your Data Structure representing the subsequence.

arr = [4, 1, 3, 5, 7];            // Monotonically increasing subsequence is [4, 5, 7]
avgDiffMonotonicIncreasing(arr);  // ((5 - 4) + (7 - 5)) / 2 = (1 + 2) / 2 = 1.5

arr = [1, 2, 3, 3, 4, 5, 4, 5];   // Monotonically increasing subsequence is [1, 2, 3, 4, 5]
avgDiffMonotonicIncreasing(arr);  // ((2 - 1) + (3 - 2) + (4 - 3) + (5 - 4)) / 4 = (1 + 1 + 1 + 1) / 4 = 1

arr = [4, 3, 2, 1, 4, 3, 3, 3];   // Monotonically increasing subsequence is [4]
avgDiffMonotonicIncreasing(arr);  // Only 1 element, return 0

arr = [1];                        // Monotonically increasing subsequence is [1]
avgDiffMonotonicIncreasing(arr);  // Only 1 element, return 0

arr = [];                         // Monotonically increasing subsequence is []
avgDiffMonotonicIncreasing(arr);  // No elements, return 0

Part 5: Testing (10 points)

We provide PublicTester.java. This contains all the public test cases we will use to grade your Deque, Stack, Queue, and Algorithm (visible on Gradescope).

Your task: create CustomTester.java and implement tests that can correctly distinguish between good and bad implementations.

• Your tests will be graded by checking if they pass on a good implementation and fail on a bad implementation. If a test fails on a good implementation, then the test is written incorrectly. If a test passes on a bad implementation, it may be written incorrectly or may be not be rigorous enough (try adding more asserts).
• Gradescope will report whether your CustomTester fails on our good implementation (solution code) as a way to sanity check some of your test cases. However, you will not be able to see whether your tests pass/fail on the bad implementations until the PA is graded. Do your best to write comprehensive test asserts based on the write-up description and public tester examples.
  • ⚠️If you fail TestCustomTesterSanity you will receive a 0 on this section! Please read the Gradescope output carefully.⚠️
• Any test you write in CustomTester.java will be run against all bad implementations. You will receive 1.25 points for every bad implementation your test is expected to fail, up to 10 points (if your test also passes on the good implementation).
• There is a total of 11 bad implementations: 8 for MyDeque, 1 for MyStack, 1 for MyQueue, and 1 for MyAlgorithm.
• For MyDeque, the following methods have bad implementations:
  • MyDeque Constructor
  • expandCapacity
  • addFirst
  • addLast
  • removeFirst
  • removeLast
• For MyStack and MyQueue, the stack and queue behavior have bad implementations.
• For MyAlgorithm, avgDiffMonotonicIncreasing has a bad implementation.
• Hint: a tricky part of this PA is the behavior of circular arrays. Make sure you test cases where the array wraps around!

How to compile and run the testers:

Running the tester on UNIX based systems (including a mac):

• Compile: javac -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. PublicTester.java
• Execute: java -cp ../libs/junit-4.13.2.jar:../libs/hamcrest-2.2.jar:. org.junit.runner.JUnitCore PublicTester

Running the tester on Windows systems:

• Compile: javac -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" PublicTester.java
• Execute: java -cp ".;..\libs\junit-4.13.2.jar;..\libs\hamcrest-2.2.jar" org.junit.runner.JUnitCore PublicTester

Part 6: Coding Style (5 points)

Coding style is an important part of ensuring readability and maintainability of your code. We will grade your code style in all submitted code files according to the style guidelines. Namely, there are a few things you must have in each file/class/method:

• File header
• Class header
• Method header(s)
• Inline comments
• Proper indentation
• Descriptive variable names
• No magic numbers (Exception: Magic numbers can be used for testing.)
• Reasonably short methods (if you have implemented each method according to the specification in this write-up, you’re fine). This is not enforced as strictly.
• Lines shorter than 80 characters
• Javadoc conventions (@param, @return tags, /** comments */, etc.)

A full style guide can be found here and a sample styled file can be found here. If you need any clarifications, feel free to ask on Piazza.

Submission Instructions

Turning in your code

Submit all of the following files to Gradescope

• MyDeque.java
• MyStack.java
• MyQueue.java
• MyAlgorithm.java
• CustomTester.java

Important: Even if your code does not pass all the tests, you will still be able to submit your homework to receive partial points for the tests that you passed. Make sure your code compiles in order to receive partial credit.

How your assignment will be evaluated [100 points]

• Correctness [95 points] You will earn points based on the autograder tests that your code passes. If the autograder tests are not able to run (e.g., your code does not compile or it does not match the specifications in this writeup), you may not earn credit.
  • Tester [10 points]
    • The autograder will test your implementation of the JUnit tests.
    • This section has a maximum of 10 pts. This means if you pass at least 8 out of 11 custom tester cases, you will get full points for the Testing portion.
  • Deque/Stack/Queue/Algorithm Implementation [85 points]
    • The autograder will test your implementation on the public test cases given in PublicTester.java and hidden test cases not described in this PA writeup.
• Coding Style [5 points]
  • MyDeque.java, MyStack.java, MyQueue.java, and MyAlgorithm.java will be graded on style. CustomTester.java will be graded on file, class, method headers and indentation.