Question

Suppose we decide to add a new operation to our Stack ADT called sizeIs, which returns a value of primitive type int equal to the number of items on the stack. The method signature for sizeIS is

public int sizeIs()

a.) Write the code for sizeIs for the ArrayStack class

b.) Write the code for sizeIs for the LinkedStack class (do not add any instance variables to the class; each time sizeIs is called you must "walk" through the stack and count the nodes.

//----------------------------------------------------------------
// 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;
}
}

//----------------------------------------------------------------------
// LinkedStack.java by Dale/Joyce/Weems Chapter 3
//
// Implements UnboundedStackInterface using a linked list
// to hold the stack elements.
//-----------------------------------------------------------------------

package ch03.stacks;

import support.LLNode;

public class LinkedStack implements UnboundedStackInterface
{
protected LLNode 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 newNode = new LLNode(element);
newNode.setLink(top);
top = newNode;
}   

public void pop()

// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (!isEmpty())
{
top = top.getLink();
}
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.
{   
if (!isEmpty())
return top.getInfo();
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}

public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
if (top == null)
return true;
else
return false;
}
@Override
//ToDo #42
public String toString ()
{   
   return "Need to Implement in LinkedStack class";
}
//ToDo #46a "walk"
public int sizeIs()
{
   return -100;
}
}

Answer 1

#ArrayStack

public int sizels()

{

return topIndex; // topIndex represents the top of the array stack which is equal to number of elements in it

}

#LinkedStack

public int sizels()

{

for(i=1;top.getLink();i++)

top=top.getLink();

return i;

}