OUTPUT #42 implementing method toString() in LinkedStack class MyStack: C B A My
ID: 3832957 • Letter: O
Question
OUTPUT
#42 implementing method toString() in LinkedStack class
MyStack: C B A
MyStack after pop: B A
MyIntegerStack: 9 7
MyEmptyStack: Stack is empty
#46a.implementing sizeIs() in ArrayStack class and testing in Driver class
myStackArray size is: 0
myStackArray after pushing A, B, C, size is: 3
MyStackArray after pop, size is: 2
46b.implementing sizeIs() in LinkedStack class and testing in Driver class(walk)
Just after creation myStack2 size is: 0
MyStack2: G F D
myStack2 size is: 3
MyStack2 after pop: F D
myStack2 size is: 2
...................................
import support.LLNode;
public class LinkedStack<T> implements UnboundedStackInterface<T>
{
protected LLNode<T> top; // reference to the top of this stack
public LinkedStack()
{
top = null;
}
public void push(T element)
// Places element at the top of this stack.
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(top);
top = newNode;
}
public void pop()
{
if (!isEmpty())
{
top = top.getLink();
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
{
if (!isEmpty())
return top.getInfo();
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}
public boolean isEmpty()
{
if (top == null)
return true;
else
return false;
}
public String toString()
{
LLNode<T> temp=top;
String result="{";
while(temp!=null)
{
result+=temp.getInfo();
temp=temp.getLink();
if(temp==null)
result+="} ";
else
result+=", ";
}
return result;
}
}
............................
//----------------------------------------------------------------
// ArrayStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements BoundedStackInterface using an array to hold the
// stack elements.
//
// Two constructors are provided: one that creates an array of a
// default size and one that allows the calling program to
// specify the size.
//----------------------------------------------------------------
package ch03.stacks;
public class ArrayStack<T> implements BoundedStackInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected T[] stack; // holds stack elements
protected int topIndex = -1; // index of top element in stack
public ArrayStack()
{
stack = (T[]) new Object[DEFCAP];
}
public ArrayStack(int maxSize)
{
stack = (T[]) new Object[maxSize];
}
public void push(T element)
// Throws StackOverflowException if this stack is full,
// otherwise places element at the top of this stack.
{
if (!isFull())
{
topIndex++;
stack[topIndex] = element;
}
else
throw new StackOverflowException("Push attempted on a full stack.");
}
public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
stack[topIndex] = null;
topIndex--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
{
T topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (topIndex == -1)
return true;
else
return false;
}
public boolean isFull()
// Returns true if this stack is full, otherwise returns false.
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
//ToDo $46b
public int sizeIs()
{
return -200;
}
}
................................
import ch03.stacks.*;
import support.*;
public class Driver
{
public static void main(String[] args)
{ //#42
System.out.println("#42 implementing method toString() in LinkedStack class");
UnboundedStackInterface<String> myStack;
myStack = new LinkedStack<String>();
myStack.push("A");
myStack.push("B");
myStack.push("C");
System.out.print("MyStack: ");
System.out.println(myStack);
myStack.pop();
System.out.print("MyStack after pop: ");
System.out.println(myStack);
UnboundedStackInterface<Integer> myIntegerStack;
myIntegerStack = new LinkedStack<Integer>();
myIntegerStack.push(7);
myIntegerStack.push(9);
System.out.print("MyIntegerStack: ");
System.out.println(myIntegerStack);
UnboundedStackInterface<Integer> myEmptyStack;
myEmptyStack = new LinkedStack<Integer>();
System.out.print("MyEmptyStack: ");
System.out.println(myEmptyStack);
//#46
//a.
System.out.println("#46a.implementing sizeIs() in ArrayStack class and testing in Driver class ");
BoundedStackInterface<String> myStackArray;
myStackArray = new ArrayStack<String>();
System.out.println("myStackArray size is: "+myStackArray.sizeIs());
myStackArray.push("A");
myStackArray.push("B");
myStackArray.push("C");
System.out.println("myStackArray after pushing A, B, C, size is: " + myStackArray.sizeIs());
myStackArray.pop();
System.out.print("MyStackArray after pop, ");
System.out.println("size is: "+myStackArray.sizeIs());
System.out.println("46b.implementing sizeIs() in LinkedStack class and testing in Driver class(walk)");
UnboundedStackInterface<String> myStack2;
myStack2 = new LinkedStack<String>();
System.out.println("Just after creation myStack2 size is: "+myStack2.sizeIs());
myStack2.push("D");
myStack2.push("F");
myStack2.push("G");
System.out.print("MyStack2: ");
System.out.println(myStack2);
System.out.println("myStack2 size is: "+myStack2.sizeIs());
myStack2.pop();
System.out.print("MyStack2 after pop: ");
System.out.println(myStack2);
System.out.println("myStack2 size is: "+myStack2.sizeIs());
}
}
Explanation / Answer
The classes ArrayStack and LinkedStack are updated to implement question 42, 46a and 46b. Please don't forget to rate the answer if it helped. Thank you very much.
Since the code for the 2 interfaces are not given here, you will have to update both interfaces and add the following line in both UnboundedStackInterface and BoundedStackInterface.
public int sizeIs();
ArrayStack.java
//----------------------------------------------------------------
// ArrayStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements BoundedStackInterface using an array to hold the
// stack elements.
//
// Two constructors are provided: one that creates an array of a
// default size and one that allows the calling program to
// specify the size.
//----------------------------------------------------------------
package ch03.stacks;
public class ArrayStack<T> implements BoundedStackInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected T[] stack; // holds stack elements
protected int topIndex = -1; // index of top element in stack
public ArrayStack()
{
stack = (T[]) new Object[DEFCAP];
}
public ArrayStack(int maxSize)
{
stack = (T[]) new Object[maxSize];
}
public void push(T element)
// Throws StackOverflowException if this stack is full,
// otherwise places element at the top of this stack.
{
if (!isFull())
{
topIndex++;
stack[topIndex] = element;
}
else
throw new StackOverflowException("Push attempted on a full stack.");
}
public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
stack[topIndex] = null;
topIndex--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element from this stack.
{
T topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (topIndex == -1)
return true;
else
return false;
}
public boolean isFull()
// Returns true if this stack is full, otherwise returns false.
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
// $46a
public int sizeIs()
{
return topIndex+1;
}
}
LinkedStack.java
package ch03.stacks;
import support.LLNode;
public class LinkedStack<T> implements UnboundedStackInterface<T>
{
protected LLNode<T> top; // reference to the top of this stack
public LinkedStack()
{
top = null;
}
public void push(T element)
// Places element at the top of this stack.
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(top);
top = newNode;
}
public void pop()
{
if (!isEmpty())
{
top = top.getLink();
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
{
if (!isEmpty())
return top.getInfo();
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}
public boolean isEmpty()
{
if (top == null)
return true;
else
return false;
}
//$42
public String toString()
{
if(top == null)
return "Stack is empty";
LLNode<T> temp=top;
String result="";
while(temp!=null)
{
result+=temp.getInfo();
temp=temp.getLink();
if(temp==null)
result+="";
else
result+=" ";
}
return result;
}
//46b
@Override
public int sizeIs() {
int size = 0;
LLNode<T> temp = top;
while(temp!=null)
{
size++;
temp = temp.getLink();
}
return size;
}
}
Answer for Question 46.c
If we want to use a instance variable say size inside ListStack , we will have to modify the
following methods to maintain the correct value
1. constructor : set size = 0
2. push: increment size when new item is pushed
3. pop: decrement size when top is poped
If these changes are made, the LinkedStack would like following...(named the changed class as LinkedStack46c)
LinkedStack46c.java
package ch03.stacks;
import support.LLNode;
public class LinkedStack46c<T> implements UnboundedStackInterface<T>
{
int size;
protected LLNode<T> top; // reference to the top of this stack
public LinkedStack46c()
{
top = null;
size = 0;
}
public void push(T element)
// Places element at the top of this stack.
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(top);
top = newNode;
size++;
}
public void pop()
{
if (!isEmpty())
{
top = top.getLink();
size--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public T top()
{
if (!isEmpty())
return top.getInfo();
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}
public boolean isEmpty()
{
if (top == null)
return true;
else
return false;
}
//$42
public String toString()
{
if(top == null)
return "Stack is empty";
LLNode<T> temp=top;
String result="";
while(temp!=null)
{
result+=temp.getInfo();
temp=temp.getLink();
if(temp==null)
result+="";
else
result+=" ";
}
return result;
}
//46c
@Override
public int sizeIs() {
return size;
}
}
Answer for Question 46.d
1. For the method implemented in 46a, sizeIs in ArrayStack , it is of O(1) since its a constant time and just
uses the value of topIndex
2. For the method implemented in 46b, sizeIs (walk version) in LinkedStack, it is of O(n) since it needs to
traverse the entire stack elements to compute size.
3. For the method implemented in 46c, sizeIs (instance variable version) , it is of O(1) i.e. constant time since
it just returns the instance variable and is not access all elements in stack.
Output of driver class after changes
#42 implementing method toString() in LinkedStack class
MyStack: C B A
MyStack after pop: B A
MyIntegerStack: 9 7
MyEmptyStack: Stack is empty
#46a.implementing sizeIs() in ArrayStack class and testing in Driver class
myStackArray size is: 0
myStackArray after pushing A, B, C, size is: 3
MyStackArray after pop, size is: 2
46b.implementing sizeIs() in LinkedStack class and testing in Driver class(walk)
Just after creation myStack2 size is: 0
MyStack2: G F D
myStack2 size is: 3
MyStack2 after pop: F D
myStack2 size is: 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.