Java代写：CSE12StacksandQueueswithaDeque

实现数据结构中的Stack和Queue, 并实现 [ BFS ](https://www.geeksforgeeks.org/breadth-first-
search-or-bfs-for-a-graph/ “BFS”) 和 DFS
算法。
![BFS and DFS](https://www.thecrazyprogrammer.com/wp-
content/uploads/2017/06/Difference-between-BFS-and-DFS.jpg)

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 MyDeque object) to manage your data.
  Note: null cannot be a valid element in the MyDeque 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
object created in your constructor.
There are a couple of ways to implement each method using the MyDeque object.

Method Name	Description	Exceptions to Throw
public MyStack (int initialCapacity)	Initialize a MyDeque 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 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 to implement the given QueueInterface interface in
QueueInterface.java.

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 MyDeque object) to manage
  your data.
  Note: null cannot be a valid element in the MyDeque 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 object created in your constructor. Again, there are a couple
ways to use the MyDeque 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 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 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.