Skip to main content

Homework 3: Stacks and Queues

Due: 2025-10-10 23:59:00EDT

Overview

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

Requirements.

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.

  1. For every class, provide two constructors. One constructor should constructs an object (of the corresponding class) of a default size. The other should be a one-parameter constructor that constructs an object (of the corresponding class) of the parameter-specified size.
  2. Override 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.
  3. Testing: Every class that you implement must have a corresponding Test file that contains 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. Your tests will be graded on code coverage. Code coverage measures the percentage of the source code executed when your test suite runs. In general, try to write tests which execute every line in your program.

1. TwoStacksQueue

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.

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

2. ArrayDeque

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

3. Extra Credit: NewStack

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 on generic types.

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

Submitting

Submit the following files to the assignment called HW03 on Gradescope:

  1. TwoStacksQueue.java
  2. TestTwoStacksQueue.java
  3. ArrayDeque.java
  4. TestArrayDeque.java
  5. NewStack.java (optional)
  6. TestNewStack.java (optional)
  7. README.txt

Be sure to submit the README for this assignment as its worth significantly more points than in previous assignments.

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.

Copying the files

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.