0. Introduction. In this assignment, you will implement a stack as a Java class,
ID: 3681449 • Letter: 0
Question
0. Introduction.
In this assignment, you will implement a stack as a Java class, using a linked list of nodes. Unlike the stack discussed in the lectures, however, your stack will be designed to efficiently handle repeated pushes of the same element. This shows that there are often many different ways to design the same data structure, and that a data structure should be designed for an anticipated pattern of use.
1. Theory.
The most obvious way to represent a sequence of objects is simply to list them, one after the other, like this.
a
a
b
b
b
c
a
a
d
d
d
d
Note that the same objects often appear many times in a row. This is called a run of those objects. In the example sequence, there is a run of 2 a’s, a run of 3 b’s, a run of 1 c, a run of 2 a’s, and a run of 4 d’s. You can represent a sequence with runs by listing its objects, along with the number of times each object appears. For example, you can represent the sequence shown above like this.
a
b
c
a
d
2
3
1
2
4
Representing a sequence in this way is called run-length encoding. If a sequence has long runs, or many runs, then run-length encoding will represent it more efficiently than simply listing its objects. However, if a sequence has short runs, or few runs, then run-length encoding may represent it less efficiently, because extra space is needed for the lengths of the runs.
Since a stack is just a simple kind of sequence, you can use run-length encoding to implement it. In this assignment, you will write a Java class called RunnyStack that implements a stack which uses run-length encoding. For example, suppose you push an object a on an empty RunnyStack. Then the stack will look like this, with a run of 1 a.
a 1
Now suppose you push b. The stack now looks like this, with a run of 1 b, and a run of 1 a.
b 1
a 1
If you push another b on the RunnyStack, then the length of the run on top of the stack is incremented, so the stack looks like this.
b 2
a 1
If you push yet another b, then the length of the run at the top of the stack would increase to 3. However, suppose that you pop the RunnyStack instead. Then the length of the run at the top is decremented, so that the stack looks like this.
b 1
a 1
If you pop the RunnyStack one more time, then the length of the run on top of the stack is decremented to 0. However, a run of 0 objects is like no run at all, so it vanishes, and the stack looks as it did after the first push.
a 1
Stacks with run-length encoding are used internally by some compilers and interpreters, because they often push the same objects over and over again.
2. Implementation.
You must write a class called RunnyStack that represents a stack of objects. Your class must implement run-length encoding, as described previously. It must also hold objects of type Base, so it will look like this.
class RunnyStack<Base>
{
}
Your class must define at least the following methods, as described below. To simplify grading, your methods must have the same names as the ones shown here.
public RunnyStack()
(5 points.) Constructor. Make a new, empty instance of RunnyStack.
public int depth()
(5 points.) Return the depth of the stack: the sum of the lengths of all the runs it holds. This is not necessarily the same as the number of runs it holds, which is returned by the method runs.
public boolean isEmpty()
(5 points.) Test if the stack holds no objects.
public Base peek()
(5 points.) If the stack is empty, then throw an IllegalStateException. Otherwise, return the object at the top of the stack.
public void pop()
(5 points.) If the stack is empty, then throw an IllegalStateException. Otherwise, decrement the length of the run on top of the stack. If this leaves a run of zero objects on top of the stack, then remove that run.
public void push(Base object)
(10 points.) If the stack is empty, then add a new run of one object at the top of the stack. If the stack is not empty, then test if object is equal to the object in the run at the top of the stack. If it is, then increment the length of that run. If it isn’t, then add a new run of one object at the top of the stack. Note that object may benull.
public int runs()
(5 points.) Return the number of runs in the stack. This is not necessarily the same as its depth, which is returned by the method depth.
Here are some hints, requirements, and warnings. First, all these methods must work using O(1) operations, so they are not allowed to use loops or recursions. That means you may need to introduce extra private variables.
Second, your RunnyStack class must have a private nested class called Run. It must have three private slots that have the following names and types. The slot object points to the Base object that appears in the run. The slot length is an int that is the length of the run. The slot next points to the Run that is immediately below this one on the stack, or to null. It must also have a private constructor that initializes these slots. Each instance of Run represents a run of objects. You must use instances of Run to implement your stack. You will receive no points for this assignment if you use arrays in any way!
Third, your push method must test non-null objects for equality using their equals methods. It must use the Java ‘==’ operator only for testing null objects. It is helpful to define an extra private method called isEqual that takes two objects as arguments, and tests if they are equal. If either object is null, then isEqual uses ‘==’. If neither object is null, then isEqual uses equals.
Fourth, RunnyStack’s methods are not allowed to print things. If you were writing RunnyStack in the Real World, then it might be part of some larger program. You don’t know whether the larger program should print things (maybe it’s operating a toaster).
In addition to RunnyStack, you should also write a driver class that tests if RunnyStack’s methods work correctly. You will receive no points for the driver class. However, if you don’t write it, then you probably will not be able to find mistakes in your methods. Here is an example driver class; the comments show what it should print.
class RunnyDriver
{
public static void main(String[] args)
{
RunnyStack<String> s = new RunnyStack<String>();
s.push("A");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // A 1 1
s.push("B");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 2 2
s.push("B");
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 3 2
s.pop();
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // B 2 2
s.pop();
System.out.println(s.peek() + " " + s.depth() + " " + s.runs()); // A 1 1
}
}
This driver class does not necessarily implement a complete set of tests for RunnyStack’s methods. You should also do tests of your own.
a
a
b
b
b
c
a
a
d
d
d
d
Explanation / Answer
RunnyStack.java
class RunnyStack<Base>
{
private Base [] runs; // Array of Base objects, each element is an object which has a corresponding run length. Each object is a "run".
private int [] runLength; // Array of integers, each element corresponds to an objects run length. "A runs length".
private int count; // Index of first unused element in runs. This and runsPresent should have the same values the entire time.
private int runsPresent; // Number of runs on stack. Gets incremented if new type of object is added.
private int objectsPresent; // Depth of stack. The number of objects it holds. Gets incremented if new type or same type.
public RunnyStack(int depth)
{
if (depth < 0)
{
throw new IllegalArgumentException("Stack cannot have a depth that is less than zero.");
}
else
{
runs = (Base []) new Object[depth]; // Set runs array to hold (depth) objects.
runLength = new int[depth]; // Sets runLength to hold (depth) integers.
count = 0; // The first index of an unused element is zero in empty array.
runsPresent = 0; // The number of runs on stack is initially zero.
}
}
public int depth() // Return depth of stack (how many objects it holds). Not necessarily same as the number of runs it holds.
{
return objectsPresent;
}
public int runs() // Return number of runs in stack. Not necessarily same as its depth.
{
return runsPresent;
}
public boolean isEmpty() // Test if stack holds no objects.
{
return (objectsPresent == 0);
}
public boolean isFull() // Test if stack cannot hold any more objects.
{
return (count >= runs.length);
}
public Base peek()
{
if (isEmpty())
{
throw new IllegalStateException("Stack is empty. No objects to return.");
}
else
{
return runs[runsPresent - 1];
}
}
// If stack empty, throw IllegalStateException.
// Else remove object at top of stack.
// If this leaves a run of 0 objects on top of stack, remove that run, dont leave a pointer to an inaccessible object.
public void pop()
{
if (isEmpty())
{
throw new IllegalStateException("Stack is empty. No more objects can be popped.");
}
else
{
if (runLength[runsPresent - 1] == 1) // There is going to be a run of 0 objects on top of the stack case.
{
runLength[runsPresent - 1]--; // Length at top of stack is now 0.
runs[runsPresent - 1] = null; // Delete run on top of the stack.
count--; // Decrement count. We just deleted a run on top of the stack so the next available index is 1 less than before.
runsPresent--; // Just deleted a run, run count needs to decrement by 1.
objectsPresent--; // Popping a run of 1 object means object count needs to decrement by 1.
}
else
{
runLength[runsPresent - 1]--; // Decrement runLength of run on top of stack since we know the runLength is greater than 1 and we are deleting an object from the top run.
objectsPresent--; // Decrement objectsPresent since there is now 1 less object present on the stack than before.
}
}
}
public void push(Base object)
{
if (!(isEmpty()) && isEqual(object, peek())) // Had to add the check to make sure the stack isnt empty otherwise peek() will throw an exception.
{
runLength[runsPresent - 1]++; // Increment runLength of the run on top of the stack since the object being pushed is equal to the object on top of the stack already.
objectsPresent++; // Increment number of object present on the stack.
}
else if(isFull())
{
throw new IllegalStateException("Stack is full. No more objects can be pushed.");
}
else
{
if (isEmpty()) // This case & the following 1 are redundant.
{
runs[runsPresent] = object; // runs[runsPresent] = object >> runLength[0] = object.
runLength[runsPresent]++; // runLength[runsPresent]++ >> runLength[0]++ >> 0++ >> 1.
count++; // Next available index is 1.
runsPresent++; // There is now 1 run present on the stack.
objectsPresent++; // There is now 1 object present on the stack.
}
else if (!(isEqual(object, peek())))
{
runs[runsPresent] = object; // runs[runsPresent] = object >> runLength[x] = object where x is greater than 0.
runLength[runsPresent]++; // runLegnth[runsPresent]++ >> runLength[x]++ = x + 1.
count++;
runsPresent++;
objectsPresent++;
}
}
}
private boolean isEqual(Base kobe, Base shaq)
{
if (kobe == null || shaq == null)
{
return kobe == shaq;
}
else
{
return kobe.equals(shaq);
}
}
}
StackDriver.java
class StackDriver
{
public static void main(String [] args)
{
// PROGRAM & ERROR TESTING. (Uncomment commented lines 1 at a time to produce the expected error).
//RunnyStack<String> stackShouldFail = new RunnyStack<String>(-1); // Stack cannot have a depth that is less than zero.
RunnyStack<String> stack = new RunnyStack<String>(5);
//System.out.println("Stack empty?" + stack.isEmpty()); // Stack empty? true
//stack.peek(); // Stack is empty. No objects to return.
//stack.pop(); // Stack is empty. No more objects can be popped.
stack.push("A");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 1 1
stack.push("A");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 2 1
stack.push("A");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 3 1
stack.pop();
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 2 1
stack.pop();
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 1 1
/*stack.pop();
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // A 1 1 // Creates stack is empty error.*/
stack.push("B");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // B 2 2
stack.push("B");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // B 3 2
stack.push("C");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // C 4 3
stack.push("C");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // C 5 3
stack.push("C");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // C 6 3
stack.push("D");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // D 7 4
stack.push("D");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // D 8 4
stack.push("D");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // D 9 4
stack.push("D");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // D 10 4
stack.push("E");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // E 11 5
stack.push("E");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // E 12 5
stack.push("E");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // E 13 5
stack.push("E");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // E 14 5
stack.push("E");
System.out.println(stack.peek() + " " + stack.depth() + " " + stack.runs()); // E 15 5
stack.push("F"); // "Stack is full. No more objects can be pushed."
}
}
sample output
A 1 1
A 2 1
A 3 1
A 2 1
A 1 1
B 2 2
B 3 2
C 4 3
C 5 3
C 6 3
D 7 4
D 8 4
D 9 4
D 10 4
E 11 5
E 12 5
E 13 5
E 14 5
E 15 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.