Due: 2024-02-22 23:59:00EDT
In this assignment, we’ll explore Stacks and Queues.
All files that you need can be downloaded with
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw03/ArrayStack.java
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw03/Deque.java
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw03/IntStack.java
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw03/Queue.java
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw03/Stack.java
These requirements apply to the implementations of all parts of the assignment (or two parts, if you are not doing extra credit).Unless specified, you cannot use any built-in java data structures.
toString
to return a String
that contains the contents of the
data structure in the following format, starting from the first-in element as
(elment1, element2, ..., elementN)
.
Note that in case of a stack, this means top is printed last.JUnit
tests. Be sure to test all methods and all exceptions as well. Note that it is
not enough to have just one test case for each method; there are plenty of complex interactions between the methods that should be covered as well. (And yes, you need to test toString as well.)
The name of test file should be Test<ClassName>.java
.A TwoStacksQueue
object is a Queue
, meaning that we insert and remove
items based on FIFO - first in first out.
Write a class called TwoStacksQueue
that implements the Queue
interface as follows.
Your class will store two ArrayStack
objects (given in the ArrayStack file you downloaded) as instance variables.
It cannot have any other instance variables.
Since you are using two stacks to simulate a queue, it will certainly not be the most efficient implementation of a queue and that’s ok - just as long as you know that and can analyze the runtime appropriately in the README - see below. There should not be any other array/ArrayList/linked list used within your implementation.
In your README
, provide a discussion on the design of your data
structure.
Make sure to describe how you implemented enqueue
and dequeue
operations. In addition, you should provide a worse-case big-O analysis
of each of these operations.
You should use
ArrayStack.java
and Stack.java
and Queue.java
Queue.java
is an interface which you must implement. Follow the instructions in that interface file for intended behavior.
You should have two constructors. One which takes a max capacity and one which takes no arguments and sets the array’s capacity to a size 100.
Testing: Name the test file TestTwoStacksQueue.java
In a class called ArrayDeque
, implement the Deque
data structure (double-ended queue where we can insert
and delete at both ends) with an array used in a circular fashion.
Dequeue.java
specifies the
Deque interface that you must implement.
The discussion in Section 6.3 of the textbook will be very helpful.
You should have two constructors. One which takes a max capacity and one which takes no arguments and sets the array’s capacity to a size 100.
If your deque is full and the user tries to add another element, throw a RuntimeException
. If the user tries to remove from an empty deque, return null.
Testing: Name the test file TestArrayDeque.java
In a file callled NewStack.java
,
implement a stack data structure called NewStack
which implements the Stack
interface and supports
that supports the usual operations size
, isEmpty
, push
,
pop
, top
.
NewStack
must support an
additional operation minElement
, which returns (but does
not remove) the smallest element currently in the stack.
All operations
(except for toString
) should run in O(1)
worst case time - note that this
means no loops of any kind.
There are different designs to achieve the O(1)
minElement
, differing mainly in the amount of additional space.
Two common approaches are O(1)
space or O(n)
space. Explain how your data structure
works in your README
and justify the O(1)
runtime of minElement
, together with
the amount of space used.
Testing: Name the test file TestNewStack.java
Submit the following files to the assignment called HW03
on Gradescope:
TwoStacksQueue.java
TestTwoStacksQueue.java
ArrayDeque.java
TestArrayDeque.java
NewStack.java
(optional)README.txt
Make sure to name these files exactly what we specify here. Otherwise,
our autograders might not work and we might have to take points off.
DO NOT submit a .docx or .pdf file.
DO NOT submit any .class
files or any of the csv
files.
DO NOT submit any of the provided interfaces. We will use the ones
we provide for testing.
You will likely want to submit the files from your own laptop/computer.
To copy the files from goldengate
to your own machine,
open up a terminal on your own computer. If you have a mac or linux, you can use the
Terminal application, if you have a windows you can use the Powershell app.
Run the following command:
$ scp <username>@goldengate.cs.brynmawr.edu/home/<username>/cs151/homeworks/hw03/*
Make sure to replace <username>
with your username. scp
is a command to secure-copy files
from one server to another. In this case, from goldengate
to your own machine.