Question
In: Computer Science
0. Introduction. In this assignment you will implement a stack as a Java class, using a...
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 to store 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. Here are some
examples of how it works. 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. 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()
Constructor. Make a new, empty instance of RunnyStack.
-
public int depth()
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()
Test if the stack is empty.
-
public Base peek()
If the stack is empty, then throw an IllegalStateException. Otherwise, return the Base at the top of the stack.
-
public void pop()
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 Base’s on top of the stack, then remove that run.
-
public void push(Base base)
If the stack is empty, then add a new run of one Base at the top of the stack. If the stack is not empty, then test if base 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 base at the top of the stack. Note that base may be null.
-
public int runs()
Return the number of runs in the stack. This is not necessarily the same as its depth, which is returned by the method depth.
Important!！！！！！！！ 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.
You will receive no points for this assignment if you use loops
or recursions in any way!
Second, your RunnyStack class must
have a private nested class called Run. You must use instances of
Run to implement your stack. Each instance of Run represents a run
of Base’s. You will receive no points for this assignment if
you use arrays in any way! The class Run must have three
private slots that have the following names and types. The slot
base points to the Base that appears in the run. The slot length is
an int that is the length of the run. The slot next points to the
instance of Run that is immediately below this one on the stack, or
to null. It must also have a private constructor that initializes
these slots.
Third, your push method must test
non-null Base’s for equality using their equals methods. It must
use the Java ‘==’ operator only for testing null Base’s. It is
helpful to define an extra private method called isEqual that takes
two Base’s as arguments, and tests if they are equal. If either
Base is null, then isEqual uses ‘==’. If neither Base 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
if that larger program should print things.
TEST.JAVA FILE AS FOLLOW:
// The TRY-CATCH statements catch exceptions thrown by RUNNY STACK's methods,
// so that the program can continue to run even if a method fails.
//
// Tests have comments that show what they should print, and how many points
// they are worth, for a total of 40 points.
//
// Camembert is a soft French cheese. It may be runny. It can be stacked.
//
class Camembert
{
public static void main(String [] args)
{
RunnyStack<String> s = new RunnyStack<String>();
System.out.println(s.isEmpty()); // true 1 point
System.out.println(s.depth()); // 0 1 point
System.out.println(s.runs()); // 0 1 point
try
{
s.pop();
}
catch (IllegalStateException ignore)
{
System.out.println("No pop"); // No pop 1 point
}
try
{
System.out.println(s.peek());
}
catch (IllegalStateException ignore)
{
System.out.println("No peek"); // No peek 1 point
}
s.push("A");
System.out.println(s.peek()); // A 1 point
System.out.println(s.depth()); // 1 1 point
System.out.println(s.runs()); // 1 1 point
System.out.println(s.isEmpty()); // false 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 2 1 point
System.out.println(s.runs()); // 2 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 3 1 point
System.out.println(s.runs()); // 2 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 4 1 point
System.out.println(s.runs()); // 2 1 point
s.push("C");
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 5 1 point
System.out.println(s.runs()); // 3 1 point
s.push("C");
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 6 1 point
System.out.println(s.runs()); // 3 1 point
s.pop();
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 5 1 point
System.out.println(s.runs()); // 3 1 point
s.pop();
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 4 1 point
System.out.println(s.runs()); // 2 1 point
s.pop();
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 3 1 point
System.out.println(s.runs()); // 2 1 point
s.pop();
s.pop();
System.out.println(s.peek()); // A 1 point
System.out.println(s.depth()); // 1 1 point
System.out.println(s.runs()); // 1 1 point
s.pop();
System.out.println(s.isEmpty()); // true 1 point
System.out.println(s.depth()); // 0 1 point
System.out.println(s.runs()); // 0 1 point
try
{
System.out.println(s.peek());
}
catch (IllegalStateException ignore)
{
System.out.println("No peek"); // No peek 1 point
}
}
}Solutions
Expert Solution
The following java code does all the tasks. The key is to maintain two private variables DEPTH and RUNS, that store the sum of runs and number of runs inside the stack. This way, no loop is required to calculate them. They are updated during puch or pop acccordingly. Finally an inner Run class is used to represent each run inside the stack.
Read the comments inside the code:
class RunnyStack<Base> {
//Points to top of the stack
private Run top;
//Depth of the stack -- sum of runs
private int DEPTH;
//Number of runs
private int RUNS;
//Constructor
public RunnyStack() {
//Initialize empty stack
top = null;
DEPTH = 0;
RUNS = 0;
}
//Inner class
class Run {
//3 private variables
private Base base;
private int length;
private Run next;
//private constructor
private Run(Base v) {
this.base = v;
this.length = 1;
this.next = null;
}
}
public int depth() {
return this.DEPTH;
}
public boolean isEmpty() {
return top==null;
}
public Base peek() {
if(isEmpty()) throw new IllegalStateException("Empty Stack");
return top.base;
}
public void pop() {
if(isEmpty()) {
throw new IllegalStateException("Empty stack");
}
else {
//If the top run occurs more than 1 time
if(top.length > 1) {
top.length--;
DEPTH--;
}
//run of top is 1
//remove top
//Depth and number of runs both reduce
else {
top = top.next;
DEPTH--;
RUNS--;
}
}
}
//Helper function
private boolean isEqual(Base b1, Base b2) {
if(b1==null || b2==null) return b1==b2;
return b1.equals(b2);
}
public void push(Base base) {
//If stack is empty
if(isEmpty()) {
top = new Run(base);
DEPTH++;
RUNS++;
}
// If the base to be pushed is already at the top of stack
else if(isEqual(top.base, base)) {
top.length++;
DEPTH++;
}
//In other case, create a new run and make it the top of the stack
// Its next will point to top of the old stack
else {
Run b = new Run(base);
b.next = top;
top = b;
DEPTH++;
RUNS++;
}
}
public int runs() {
return RUNS;
}
}
public class Camembert
{
public static void main(String [] args)
{
RunnyStack<String> s = new RunnyStack<String>();
System.out.println(s.isEmpty()); // true 1 point
System.out.println(s.depth()); // 0 1 point
System.out.println(s.runs()); // 0 1 point
try
{
s.pop();
}
catch (IllegalStateException ignore)
{
System.out.println("No pop"); // No pop 1 point
}
try
{
System.out.println(s.peek());
}
catch (IllegalStateException ignore)
{
System.out.println("No peek"); // No peek 1 point
}
s.push("A");
System.out.println(s.peek()); // A 1 point
System.out.println(s.depth()); // 1 1 point
System.out.println(s.runs()); // 1 1 point
System.out.println(s.isEmpty()); // false 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 2 1 point
System.out.println(s.runs()); // 2 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 3 1 point
System.out.println(s.runs()); // 2 1 point
s.push("B");
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 4 1 point
System.out.println(s.runs()); // 2 1 point
s.push("C");
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 5 1 point
System.out.println(s.runs()); // 3 1 point
s.push("C");
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 6 1 point
System.out.println(s.runs()); // 3 1 point
s.pop();
System.out.println(s.peek()); // C 1 point
System.out.println(s.depth()); // 5 1 point
System.out.println(s.runs()); // 3 1 point
s.pop();
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 4 1 point
System.out.println(s.runs()); // 2 1 point
s.pop();
System.out.println(s.peek()); // B 1 point
System.out.println(s.depth()); // 3 1 point
System.out.println(s.runs()); // 2 1 point
s.pop();
s.pop();
System.out.println(s.peek()); // A 1 point
System.out.println(s.depth()); // 1 1 point
System.out.println(s.runs()); // 1 1 point
s.pop();
System.out.println(s.isEmpty()); // true 1 point
System.out.println(s.depth()); // 0 1 point
System.out.println(s.runs()); // 0 1 point
try
{
System.out.println(s.peek());
}
catch (IllegalStateException ignore)
{
System.out.println("No peek"); // No peek 1 point
}
}
}The class Camembert is for testing. Save the above file as Camembert.java and compile and run it:
The output:
true
0
0
No pop
No peek
A
1
1
false
B
2
2
B
3
2
B
4
2
C
5
3
C
6
3
C
5
3
B
4
2
B
3
2
A
1
1
true
0
0
No peekwhich is the required output.
venereology answered 2 years agoRelated Solutions
Define empty methods in Stack class using LinkedList class in Java ------------------------------------------------------------------------------- //Stack class public class...
In Java or C++, implement a stack and a queue using a linkedlist data structure. You may...
In simple Java language algorithm: Implement a static stack class of char. Your class should include...
Java programming! Implement a static stack class of char. Your class should include two constructors. One...
Code in Java Create a stack class to store integers and implement following methods: 1) void...
Program in Java Create a stack class to store integers and implement following methods: 1- void...
Create in Java Create a stack class to store integers and implement following methods: 1- void...
Using STL stack class, implement in C++ a function that checks for balanced braces { },...
Implement our own stack class patterned after Java's Stack class. Start with a generic class that...
StackBox Implement our own stack class patterned after Java's Stack class. Start with a generic class...
- I have a problem with my code. It does not run. Please can someone check the...
- As discussed in the text, in the absence of market imperfections and tax effects, we would...
- //This is an ArrayReverser Problem.. import java.util.Scanner; public class Main { public static void main(String[] args)...
- After completing its capital spending for the year, Carlson Manufacturing has $1,100 extra cash. Carlson’s managers...
- Question 2: How can we find the real root of a polynomial with one variable? Also...
- Apply the Cognitive/Affective/Behavior Attitude model to a day to day personal life experience at work, home...
- you may not use the Python ord() or chr() functions you may not use the Python...