Java Project

In this project, you will create the ADT Queue and the ADT Stack using Java's basic array data structure and a linked list, respectively. Both the Queue and Stack must implement the QueueInterface, which you will write.

The Queue should be implemented using a **Circular Buffer** (a.k.a. a **Ring Buffer**), which uses indices to mark the front and back of the queue that is stored in the array. You should also use a **dummy value** in this implementation, meaning an extra space that is a buffer between the front and the back of the queue.

If the indices used for the front and back of the Queue are equal, then the Queue is empty. If the back index + 1 would be equal to the front index of the Queue, then the Queue is full.

The Stack should be implemented using a Linked List with a dummy node at the head of the list. For the implementation, both add and remove from the front of the list.

You will create a small test tree and output the results of a BFS and DFS to make sure you understand the structure of a tree, traversal of the tree using either BFS or DFS, and to test your code.

You will use your Queue and Stack to traverse a tree that represents a Sudoku puzzle (which has been provided). Each node can have 0 to 9 children, depending on the size of the puzzle and the constraints of the specific puzzle. Children are stored in an `ArrayListNode Board`. While traversing the tree to find the solution, you will track the number of nodes visited to compare a BFS to a DFS. The code is identical for the 2 different searches, except that a BFS uses a Queue and the DFS uses a Stack.