0. Complete the Prerequisites

Before continuing on, make sure you’re caught up on the lectures through 6/22 and have completed at least EX05.

1. Set-up!

Pull the starter code. Under the src directory under exercises, you should see a new ex07 package with a bunch of files. Take some time to look at all the files. The Node Interface, NodeImpl Class, and LinkedList Class should all be familiar. You will be doing your work in the StackSetImpl Class implementing the methods from the StackSet Interface. You are free to test your work in StackSetPlayground.

2. Implementing the StackSet ADT

You are going to build in Java an implementaion for what we will call a StackSet (SST) using linked cells to do it. By StackSet, you will see (hopefully) as we define its behavior that it is sort of a Stack, but with a uniqueness criterion on its elements, just as a Set contains unique elements. So the StackSet code will implement a Set (where order is not important, just membership and size) and it will also behave much as a Stack (LIFO order, sort of). We say “much as” a Stack because there is a small difference… or two.

It is your task to implement the methods specified by the StackSet Interface. Their expected behavior is described in detail below.

push:

• inputs: an element of type T

• returns: boolean (indicating success or not)

• effect: push will first ensure that at most one element with any specific value is ever stored in the LIFOset… so we say the stack implements a set.

  push will also make sure that the size of the stack never exceeds the limit() limit established by the constructor

  if we do push(n) for some value n here is what happens:

  – if n is already in the stack, return true. We move that existing element to be at the top; in this case the size of the stack does not change, but the state does… the element relative order will probably change (wont change is n is already the top)

  – if n is not already in the stack, then we have 2 subcases:

  1. if size ()==limit() return false, we make no changes to the stack since adding the new element would make the stack too big.

  2. if size() less than limit() return true. There is room for the new element, so we put the new element at the top, and the size increases by 1

pop:

• inputs : nothing

• returns: boolean… true if the top item is successfully removed, false if no change is made to the stack

• effect: there are cases to consider

  1. if the stack is not empty, the element at top is removed and the size reduced by one (true returned)

  2. if the stack is empty, then no change is made (false returned)

peek: (just a different name for top)

• inputs : nothing

• returns: T

• effect:

  1. if the stack size is 1 or more, then return the value of the top element

  2. if the stack is empty, then return null.

contains:

• inputs : an element of type T

• returns: boolean indicating if the value is in the stack

• effect: no change is made in state of the data structure

  1. return true if the given element is an element in the stack

  2. return false if it is NOT in the stack (including if the stack is empty)

size:

• inputs : nothing

• return: integer (the number of elements in the stack). this will be 0 or greater, and limit() or smaller

• effect: no change is made in state of the data structure

limit:

• inputs: nothing

• returns: integer, telling the maximum number of elements that can ever be in the stack… this is defined as a parameter to the constructor. it is also a constant, and 0 or greater.

• effect: no change is made in state of the data structure

isEmpty:

• inputs: nothing

• returns: boolean telling if the stack has no elements

• effect: shorthand for size() == 0. no change is made in state of the data structure

isFull:

• inputs: nothing

• returns: boolean telling if the stack may have no more elements added to it

• effect: shorthand for size() == limit(). no change is made in state of the data structure

Hints and Notes

• It may be useful to use some of the methods you implemented in EX05 to complete the exercise! We just included the base LinkedList implementation in the starter code, but feel free to copy in your work from the exercises here.

3. Make a Backup Checkpoint “Commit”

“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.

1. Select the Git menu along the top of your screen and then choose “Commit”.
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Ensure all the files that you’d like to backup are selected. Your cursor should be inside of a message box where you will write a nice description of the modifications you’ve made to your code, like “Finished EX07!”, and then hit the “Commit” button.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
   • IntelliJ might tell you there are some warnings or errors here, and you should just commit anyway!
4. If you open the Git at the bottom of your screen, you should see this commit added to your chain of git commits. However, it has just been added to your local main branch, and needs to be pushed to your remote backup.
5. Select the Git menu along the top of your screen again and then choose “Push”.
6. A pop-up should appear that displays: “main -> backup : main”, which means your latest local commit on the local main branch is going to be pushed to the main branch on the remote backup. If you see “main -> origin : main”, just click where it says origin and select backup. Hit the “Push” button.
7. If you want to see your backed up work on Github, navigate to the following URL but replace USERNAME with your GitHub username:
   • https://github.com/summer-210/summer210-workspace-USERNAME
   • You can also verify it was pushed successfully by opening the Git view along the bottom of your screen and verifying the latest commit appears on the local and remote branches. (The text next to the tag icons should say backup & main, next to the latest commit message)

4. Submit to Gradescope for Grading

All that’s left now is to hand-in your work on Gradescope for grading.

Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!

Login to Gradescope and select the assignment named “EX07 - StackSet” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.

Mac Users

Along the bottom of your window, you should see an option to open a terminal integrated into IntelliJ.

Type the following command (all on a single line):

./submit.sh ex07

In the file explorer pane, look to find the zip file named “ex07_submission.zip”. The script will call it an ex05 submission since that is the package we zipped. If you right click on this file “Open in -> Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.

Windows Users

We are working on rewriting the script to work for Windows! Until then, please navigate to your course workspace in a File Explorer window. Then right click on the src folder in your exercises directory and compress the directory into a zip folder. You can name it “ex07_submission.zip”

When you upload it to Gradescope, please delete any files that showed up in the src/ folder that were not actually part of ex07.