CSE12 – PR#3 Deques, Stacks, Queues and Search


5/5 - (2 votes)

CSE12 – PR#3
Deques, Stacks, Queues and Search
(100 points)

In this assignment you will implement data structures that provide an implementation for three
abstract data types: A double-ended queue using a circular array, a stack and a queue. In
addition, these data structures will be used in a game of Minesweeper (provided for you). Also,
along the way you will get more experience with implementing Java interfaces, writing JUnit test
cases, and using the Adapter design pattern.
This assignment is an individual assignment. You may ask Professors/TAs/Tutors for some
guidance and help, but you can’t copy code. You can, of course, discuss the assignment with
your classmates, including discussing testing strategies, concepts, implementation strategies,
and bugs you ran into and how you fixed them. But don’t look at or copy each other’s code or
written answers.
START EARLY and remember the following rules for tutor hours:
● You must not put your name in the tutor queue more than once. If tutors find your name
in the queue more than once, ALL instances of your name will be removed.
● You must indent your code correctly in order to get help from a tutor. If you code is not
properly indented when the tutor comes to help you, you’ll lose your spot and have to go
to the end of the queue.
The following files are provided for you and can be found on the HW page:
● Javadocs for BoundedDeque, BoundedStack, and BoundedQueue
You will submit the following files for this assignment:
● HW3.pdf: This is a PDF file where you will place answers to questions throughout the
● A Java class that implements the BoundedDeque interface using a
circular array.
● A Java class that implements the BoundedQueue interface
● A JUnit tester for the Deque12 class.
In EACH AND EVERY FILE that you turn in, we need the following in comments at the top of
each file.
NAME: <your name>
ID: <your student ID>
LOGIN: <your class login>
Part 1: Deque12 and BoundedDequeTester [75 points]
Read the documentation in the source code file for the BoundedDeque<E> interface, or view
the javadoc page for BoundedDeque which is included in the PR3 resources. Understand the
responsibilities of each method required by the interface. Sketch a test plan for a class that
implements this interface. Define a class named BoundedDequeTester that extends
junit.framework.TestCase and that implements your test plan, using an Deque12 object as a
test fixture.
We will run your tester as shown in lecture notes:
The class you will be testing is Deque12. Deque12 implements the BoundedDeque interface.
There is NO starter code for this particular class so you must write it yourself. You should have
at least one test for every method, but it is better form to create multiple tests for some methods
depending on the condition you are testing. For example, you’ll probably want a separate test
for adding to a full Deque from the test for adding to a non-full Deque.
As a practical matter, you do not need to completely write your BoundedDequeTester program
before starting to define Deque12. In fact, an iterative test-driven development process can
work well: write some tests in BoundedDequeTester, and implement the functionality in
Deque12 that will be tested by those tests, test that functionality with BoundedDequeTester,
write more tests, etc. The end result will (hopefully!) be the same: A good tester, and a good
implementation of the class being tested.
As for previous (and future) assignments, make sure that your BoundedDequeTester does not
depend on anything not specified by the documentation of the BoundedDeque interface and the
Deque12 class. For example, do not make use of any other constructors or instance or static
methods or variables that the ones required in the documentation.
Define a public generic class Deque12<E> that implements the BoundedDeque<E>
interface. Besides the requirements for the methods and constructor documented in that
interface, for this assignment there is the additional requirement that this implementation
must use a circular array to hold its elements. (Note also that, as for other assignments,
your Deque12 should not define any public methods or constructors other than those in the
interface specification.)
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 length equal to the capacity of the Deque12
object. Because raw arrays don’t play nicely with generics, you should use an ArrayList
object for this purpose. 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
BoundedDeque’s capacity. Once your Deque12 instance has been properly
constructed, 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 Deque12 (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 Deque12 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, and with the requirements of the interface you are implementing.
Part 2: Queue12 [15 points]
Now that you have your Deque built and fully tested, you will use it to implement a Stack and a
We have provided a full implementation of that adapts Deque12 using the adapter
design pattern. It is liberally documented so that you can see what a fully-documented code
really looks like. Read and understand the interface specification in (or view
the javadoc page for BoundedStack which is included in the PR3 resources). We’ve provided
you with some unit tests that you can use to test that Stack12 behaves properly with YOUR
implementation of Deque12. Note that the methods required by the BoundedStack interface are
different from, though closely related to, the BoundedDeque interface methods.
Read and understand the interface specification in (or view the javadoc
page for BoundedQueue which is included in the PR3 resources) and then define a generic
class Queue12<E> that implements the BoundedQueue<E> interface. Use the existing Stack12
as a guide and adapt Deque12 to Implement Queue12. Again note that the methods required by
the BoundedQueue interface are different from, though closely related to, the BoundedDeque
interface methods, and so the Adapter pattern is applicable here as well.
As is often the case when the Adapter pattern is used, if the adapted class (Deque12 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. We provide you
with a few simple tests which should be sufficient.
You must properly document your using javadoc in a similar manner to the
provided Stack12. Including pre-conditions and the like is good practice in writing “real
Part 3: Minesweeper, Depth First Search and Breadth First
Search [10 points]
The last part of this assignment is to make sure that YOUR implementation of Deque12 and the
adapted classes Stack12 and Queue12 work properly from an application’s viewpoint. Provided
to you in the implementation of a program that implements the popular game of Minesweeper
( If you’ve never played Minesweeper take a few minutes to
familiarize yourself with the game by playing a little bit. But just a little bit… try not to get too
We’ve provided to you a very basic implementation of Minesweeper that is reasonably
complete. When you click on a cell with 0 mined neighbors, the game is supposed to
automatically expose all of the surrounding neighbors of that cell, and then if any of those have
no neighbors, it auto-exposes all of its neighbors, etc, until all of the connected cells with no
mined neighbors and all of their connected neighbors are exposed.
Implementing this functionality is done by searching outward from the first exposed cell,
expanding the search until all connected neighbors that should be exposed have been explored.
As we saw/will see in class on Thursday/Friday, this can be done using depth first search or
breadth first search, and the only difference between the two algorithms is whether you use a
stack or a queue as your data store during the search.
We have provided an implementation of both DFS and BFS for you. Once you have your
Queue12 class working, you can run and play the game STUDY the difference between the
behavior of the two algorithms (DFS vs. BFS).
Part A
The first step is to understand the provided code. In your PR3.pdf file, Answer the following
1. Which method is called when the user clicks on one of the cells in the grid?
2. What are the two central classes used to implement Minesweeper? Roughly, what
does each do?
3. What class implements the necessary MouseListener methods that are attached to each
of the cells in the board?
4. What does the exposeSlowly method do? How do you control the animation speed?
5. What is the purpose of the actionPerformed method implemented in the
MineSweeperGUI class?
These questions are a minimum starting point. If you don’t understand what’s happening in the
code, talk about it with your classmates (this is allowed) or go see a tutor, TA or professor.
Part B
Finally, explore the difference between the two algorithms. Play the game with each algorithm,
and notice how the animation changes. In your PR3.pdf file in a section labeled Part B
describe the difference you see between how the cells are exposed when you use depth first
search vs. breadth first search.
Just for fun!
Our version of Minesweeper is very basic, lacking creativity and many of the bells and whistles
of the original game or improvements that you could imagine. If you’re interested, improve on
the game. This is a boundlessly open ended extension, so have fun!
Turn in
Instructions will be provided

PlaceholderCSE12 – PR#3 Deques, Stacks, Queues and Search
Open chat
Need help?
Can we help?