实现数据结构中的Stack和Queue, 并实现BFS和DFS算法。
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
Overview
There are 3 parts to this assignment. All are required before the deadline and should be submitted on Gradescope:
- Part 1: Testing and implementation of Deque, Stack, and Queue
- Testing
- Implementation of Deque, Stack, and Queue
- Coding Style
- Part 2: Conceptual Quiz
- Part 3: Weekly reflection survey (Google Form)
Each part corresponds to its own Canvas “assignment” where your grade on that part will be recorded. More information on submission is given in the Submission Instructions section.
Part 1: Testing and Implementation of Deque, Stack, and Queue (pair programming allowed)
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.
You will be creating the MyDeque, MyStack, and MyQueue classes that implement the given DequeInterface, StackInterface, and QueueInterface interfaces. Note, we did not provide starter code for MyDeque.
Part 1a - Testing
We provide two test files:
- PublicTester.java
- Contains all the public test cases we will use to grade your Deque, Stack and Queue (visible on Gradescope).
- CustomTester.java
- This file contains 10 generic method headers. You will edit this file. Points will be deducted if method header descriptions are not completed.
Your task in this part is to implement the tests that are stubbed out in the custom testers. Here are the rules for how you must follow:
- Your tests must test the method they are named for, but they may test any aspect of that method’s behavior that is not already covered by a test in the public tester. Points are awarded only if your test cases cover cases that the public tester file does not take into account.
- There is no restriction on what error message you use as your string input.
- You MUST NOT copy code from the public tester file.
- You may add additional test methods, but you are not required to do so.
- Make sure all the test cases in the custom tester file pass. Otherwise, you would receive 0 points for the test case that fails.
The table below gives the list of public tests that we will run against your solution. We will also test your code on additional hidden tests, but we will not tell you what the hidden tests will do. Note that some methods are not tested in the public tester, but will be tested using the hidden tests. It is your responsibility to write your tests to thoroughly test your code, including all edge cases.
| MyDeque Test Cases | Public Cases |
|---|---|
| Constructor | initialize MyDeque with capacity 10 |
| expandCapacity | expandCapacity with several elements at the start of the array |
| addFirst | deque containing several elements in the middle of the array |
| addLast | deque containing several elements in the middle of the array |
| removeFirst | deque containing several elements in the middle of the array |
| removeLast | deque containing several elements in the middle of the array |
| peekFirst | deque containing several elements at the start of the array |
| peekLast | deque containing several elements at the start of the array |
| MyStack Test Cases | Public Cases |
|---|---|
| Constructor | initialize stack with capacity 10 |
| empty | check stack with size 0 |
| push | empty stack |
| Constructor | initialize queue with capacity 10 |
| empty | check queue with size 0 |
| push | empty queue |
| pop | queue with several elements |
| peek | queue with several elements |
How to compile and run the public tester:
on UNIX based systems (including macOS):
$ javac -cp libs/junit4.12.jar:libs/hamcrest-core-1.3.jar:.PublicTester.java
$ java -cp libs/junit4.12.jar:libs/hamcrest-core-1.3.jar:. org.junit.runner.JUnitCore PublicTester
on Windows systems:
$ javac -cp ".;libs\junit4.12.jar;libs\hamcrest-core-1.3.jar" PublicTester.java
$ java -cp ".;libs\junit4.12.jar;libs\hamcrest-core-1.3.jar" org.junit.runner.JUnitCore PublicTester
Part 1b - MyDeque
Deque is pronounced like “deck” /dk/ 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).
- 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.
Public methods
| 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 IllegalArgumentException if the initialCapacity is negative |
| 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. | 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.
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.
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.
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.
Part 1c - 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
- MyDeque
theStack:
The underlying data structure of MyStack. You will use your implementation of the Deque ADT (in the form of a MyDequeobject) to manage your data.
Note: null cannot be a valid element in the MyDequeobject, 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
There are a couple of ways to implement each method using the MyDeque
| Method Name | Description | Exceptions to Throw |
|---|---|---|
| public MyStack (int initialCapacity) | Initialize a MyDeque | 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 1d - 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
Instance variables
- MyDeque
theQueue:
The underlying data structure of MyQueue. You will again use your implementation of the Deque ADT (in the form of a MyDequeobject) to manage your data.
Note: null cannot be a valid element in the MyDequeobject, 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
| Method Name | Description | Exceptions to Throw |
|---|---|---|
| public MyQueue (int initialCapacity) | Initialize a MyDeque | 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 Google 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 1e - MazeSearchGUI [Used for Conceptual Quiz]
After you finished implementing the Deque, Stack, and Queue, you can see how they are used in a simple maze search program we provided. You do not need to understand how the entire file works, but you should understand the similarities and differences between BFS and DFS, as well as how to play around with the file using your own custom mazes.
To get started, look for all the TODOs in the file, and write in the appropriate line based on the comment. Notice that the provided BFS and DFS code are almost identical aside from the TODOs.
We provided 3 preset mazes for you to test, feel free to modify them or create your own.
To run the program:
java MazeSearchGUI <preset maze number: 1-3> <"BFS" or "DFS">
For instance:
java MazeSearchGUI 2 DFS
runs the second preset using DFS as its algorithm.
Note that the yellow cell represents the start (S), grey represents empty cells (no text), blue represents walls (X), light green represents the finish cell (F), dark green represents the found finish cell (F), white represents visited cells (V), and red represents the path found (P). Your code is not graded and you do not need to submit it. However, there are several questions related to this portion on the conceptual quiz.
Part 1f - Coding Style [0.5 points]
We will grade your code style based on the guidelines posted on Canvas. If you need any clarifications, feel free to ask on Piazza. All submitted files will be graded for style.
Note: Any tester file(s) will not be graded for magic numbers. In tester file(s), Javadoc tags such as @param or @return are not required, and variable names such as [name]1, [name]2, etc. do not count as non-descriptive.
Single character variable names are still considered non-descriptive if not referring to an index.
Part 2: Conceptual Quiz (individual)
You are required to complete the Conceptual Quiz on Gradescope. There is no time limit on the Quiz but you must submit the Quiz by the PA deadline. You can submit multiple times before the deadline. Your latest submission will be graded.
Part 3: PA Reflection (individual)
Complete the weekly reflection here. There is an automatic 36-hour grace period for this part.
Submission
Turning in your code
Submit all of the following files
- MyDeque.java
- MyStack.java
- MyQueue.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.