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.
As we saw in class, a Stack is commonly implemented as an array, or as a sequence of linked cells. We are doing the later in this assignment, so that you get some practice in manipulating linked data structures in Java.
Using linked cells means do not use arrays to contain the elements stored in the List. It also means do not use any of the code from the Java Collections library to get your work done. In this assignment we want you to learn how make this data structure work more than how to use it to solve a problem.
The class Node below shows how we do linked cells in Java.
A linked cell is an object (class instance) that has one (or more)
references to other objects of the same class.
So a list cell refers to another list cell (the next one in the
linked sequence ).
Our implementation will be a singly linked list.
This means there is just one link in each cell, and in
our Node that link points to the cell that follows the one
contining the link (points to the "next" cell in the chain).
As you see in the Node class, there is a next field to
hold this reference.
A link in Java is just a reference to an object ( a memory address where the object storage is found). When we do something like this in Java code
Node myObj = New Node(); myObj = myObj.next;we think of storing the object itself into the variable or field, but what we really store is the reference... the object address in memory. To get to the fields of the object, we have to "dereference" the reference... meaning we have to go to the address and get the data stored at that address. The Java complier handles "dereferencing" automatically so we think of manipulating objects rather than memory locations.
In older languages (like C) references are called pointers and they are basic types; a variable containing a pointer can be manipulated with various operations like "+" and different memory locations can be accessed via an explicit dereferenceing operator. Java was created to (among other things) try to use objects in a less error prone way than by explicitly manipulating memory references. Ok... history lesson over.. now on to this assignment.
We ask that you use the boilerplate code provided and work from it. You should copy and paste the boilerplate below int Eclipse and then fill in the blanks by implementing the methods of the interfaces.
For uniformity, to aid grading, you must write your program with these specific structures.
/**
* COMP 410
*
* Make your class and its methods public!
* Don't modify this file!
*
* Your StackSet implementation will implement this interface.
*
*/
package assignment1;
/*
Interface: The StackSet will provide this collection of operations:
push:
in: double
return: boolean (indicating success or not)
effect:
push will first of all ensure that at most one element with any specific integer
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:
.. if size()==limit() return false
we make no changes to the stack since adding the new element
would make the stack too big
.. if size() less than limit() return true
there is room for the new element, so we put the new element at the top,
the size increases by 1
pop:
in: nothing
return: boolean... true is the top item is successfully removed
false if no change is made to the stack
effect: there are cases to consider
if the stack is not empty, the the element at top is removed
and the size reduced by one (true returned)
if the stack is empty, then no change is made (false returned)
peek: (just a different name for top)
in: nothing
return: double
effect: if the stack size is 1 or more, then return the value of the top element
if the stack is empty, then return Double.NaN
contains:
in: double
return: boolean indicating if the value is in the stack
effect: no change is made in state of the data structure
return true if the double given is an element in the stack
return false if it is NOT in the stack (including if the stack is empty)
size:
in: 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:
in: 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:
in: nothing
return: boolean telling if the stack has no elements
effect: shorthand for size() == 0
no change is made in state of the data structure
isFull:
in: nothing
return: 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
*/
// ADT operations
public interface StackSet_Interface {
public boolean push(double elt);
public boolean pop();
public double peek();
public boolean contains(double elt);
public int size();
public int limit();
public boolean isEmpty();
public boolean isFull();
}
/**
* COMP 410
* See inline comment descriptions for methods we need that are
* not described in the interface.
*
*/
package assignment1;
public class StackSet implements StackSet_Interface {
private Node head; //this will be the entry point to your linked list
//( it points to the first data cell, the top for a stack )
private final int limit; //defines the maximum size the stackset may contain
private int size; //current count of elements in the stackset
public StackSet( int maxNumElts ){ //this constructor is needed for testing purposes.
head = null; //Please don't modify what you see here!
limit = maxNumElts; //you may add fields if you need to
size = 0;
}
//implement all methods of the interface, and
//also include the getRoot method below that we made for testing purposes.
//Feel free to implement private helper methods!
//you may add any fields you need to add to make it all work...
public Node getRoot(){ //leave this method as is, used by the grader to grab
return head; //your data list easily.
}
}
package assignment1;
public interface Node {
public double getValue();
public void setNext(Node next);
public Node getNext();
}
/**
* COMP 410
* Don't modify this file!
*/
package assignment1;
public class NodeImpl implements Node {
private final double val;
private Node next;
public NodeImpl(double val) { this(val, null); }
public NodeImpl(double val, Node next) {
this.val = val;
this.next = next;
}
@Override
public double getValue() { return val; }
@Override
public void setNext(Node next) { this.next = next; }
@Override
public Node getNext() { return next; }
}
package assignment1;
public class StackSetPlayground {
public static void main(String[] args) {
/*
here you can instantiate your StackSet and play around with it to check correctness.
We've graciously also provided you a bit of extra test data for debugging.
It doesn't matter what you have in here. We will not grade it.
This is for your use in testing your implementation.
*/
StackSet set = new StackSet(3);
System.out.println(set);
set.push(1);
set.push(2);
System.out.println(set);
set.push(1);
System.out.println(set);
System.out.println(set.pop());
set.push(1);
set.push(2);
set.push(3);
System.out.println(set);
set.push(4);
System.out.println(set);
}
}
/**
* COMP 410
* Don't modify this file!
* This file is optional and is only needed to run the Oracle if
* it is in your build path and the jar is in your project.
*/
package assignment1;
import gradingTools.comp410f20.assignment1.testcases.Assignment1Suite;
public class RunTests {
public static void main(String[] args){
Assignment1Suite.main(args);
}
}
Push is where the action is in this ADT. Push acts like stack push when an element is added that is not already in the stack. The new element goes on as a new top.
The difference from normal stack push arises when the element being pushed is already in the stack. In this case the element is moved from where it is in the cell sequence to the top. Either way, when the push is done, the element is on top; the difference is whether the stack size grows by 1, or stays the same.
Also, this behavior presumes the stack is not full when the push is done. A full stack causes extra checks to be done. If the stack is full and the item being pushed is not in the stack then there is no room for the new item... so push fails. If the item being pushed is in the stack, then it can be move to the top, since the size wont change.
We have chosen to have pop always return a boolean (success or failure) rather than having pop return the value that is removed (as is done in many stack implementations). It is simply a design choice, and it ok since peek will produce the top element if needed. In our design, pop only fails (returns false) if you try to pop an empty stack; in this case the stack stays empty so it has a no-op effect. We think this is less disruptive than doing something like raising an exception.
We have a similar issue with peek, as in what to do when an "error" condition arises. For peek, we have a problem if you try to peek at an empty stack; since there is no data, what shall we say is the value on top? Do we have peek return two different kinds of data... like sometimes a double and other times raise an exception? In our design, we have peek return the "non value" Double.NaN, which is type compatible with the double data that will be on a non-empty stackset.
The peek operation is the same as the top operation in our discussion; the name is in keeping the the Java collections library.
For testing, use your own test cases in the StackSetPlayground class. Think in detail about what tests will cover the full range of behavior your stackset might go through in use, and make sure your code handles those situations correctly. We also encourage using the oracle for incremental development. Instructions on using the oracle will be in the form of the ppt presented in class (and posted online).
There is no specific output or runnable class required for this assignment. We assume you will use the "print" capability provided, or the debugger, to assist you in seeing how your code is working. When we grade it, we will provide our own runnable main, and it will do what we have suggested you do... it will create instanced of StackSet and manipulate them, and check the structures your implementation leaves to see if they are structured properly.
Be sure to test beyond the scope of the Oracle as mentioned in class! The order in which ADT operations are performed and what data is entering your stacksets will be different in the official grading script from what you see done in the oracle. There will be behavior that is required (in the interface you are implementing) but that is not tested in the oracle we gave you. The oracle is an assist, but it is not a complete set of tests.
Hand in your code via Sakai, and follow the instructions there for how to remove various parts and zip it all up.