Java data structures Suppose that in the arraybased stack t

Java - data structures

Suppose that in the array-based stack, the array doubles in size after multiple push operations. But later on, fewer than half of the array’s locations might actually be used by the stack due to pop operations.

Revise the implementation so that its array also can shrink in size as objects are removed from the stack. Accomplishing this task will require two new private methods, as follows:

The first new method checks whether we should reduce the size of the array:

private boolean isTooBig()

This method returns true if the number of entries in the stack is less than half the size of the array and the size of the array is greater than 20.

The second new method creates a new array that is three quarters the size of the current array and then copies the objects in the bag to the new array:

private void reduceArray()

Implement each of these two methods, and then use them in the definition of pop()

Arraystack2:

import java.util.Arrays;
public class ArrayStack2<T> implements StackInterface<T>
{
private T[] stack; // array of stack entries
private int topIndex; // index of top entry
private static final int DEFAULT_INITIAL_CAPACITY = 50;

public ArrayStack2()
{
this(DEFAULT_INITIAL_CAPACITY);
} // end default constructor

public ArrayStack2(int initialCapacity)
{
// the cast is safe because the new array contains null entries
@SuppressWarnings(\"unchecked\")
T[] tempStack = (T[])new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
} // end constructor

public void push(T newEntry)
{
ensureCapacity();
topIndex++;
stack[topIndex] = newEntry;
} // end push

private void ensureCapacity()
{ if (topIndex == stack.length - 1) // if array is full, double size of array
   stack = Arrays.copyOf(stack, 2 * stack.length);
} // end ensureCapacity

public T peek()
{
T top = null;
if (!isEmpty())
   top = stack[topIndex];
return top;
} // end peek

public T pop()
{
T top = null;

if (!isEmpty()) {
   top = stack[topIndex];
   stack[topIndex] = null;
   topIndex--;
} // end if

return top;
} // end pop

public boolean isEmpty()
{
return topIndex < 0;
} // end isEmpty

public void clear()
{
for(int i = 0; i <= topIndex; ++i)
stack[i] = null;
topIndex = -1;
}

} // end ArrayStack

Stackinterface

public interface StackInterface<T>
{
/** Adds a new entry to the top of this stack.
@param newEntry an object to be added to the stack */
public void push(T newEntry);

/** Removes and returns this stack\'s top entry.
@return either the object at the top of the stack or, if the
stack is empty before the operation, null */
public T pop();

/** Retrieves this stack\'s top entry.
@return either the object at the top of the stack or null if
the stack is empty */
public T peek();

/** Detects whether this stack is empty.
@return true if the stack is empty */
public boolean isEmpty();

/** Removes all entries from this stack */
public void clear();
} // end StackInterface

linkedStack:

public class LinkedStack<T> implements StackInterface<T>
{
private Node topNode; // references the first node in the chain

public LinkedStack()
{
topNode = null;
} // end default constructor

public void push(T newEntry)
{
Node newNode = new Node(newEntry, topNode); topNode = newNode;
} // end push

public T peek()
{
T top = null;
if (topNode != null)
   top = topNode.getData();
return top;
} // end peek

public T pop()
{
T top = peek();
if (topNode != null)
topNode = topNode.getNextNode();
return top;
} // end pop

public boolean isEmpty() {
return topNode == null;
}
public void clear() {
topNode = null;
}

private class Node
{
private T data; // entry in stack
private Node next; // link to next node

private Node(T dataPortion)
{
this(dataPortion, null);
} // end constructor

private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor

private T getData()
{
return data;
} // end getData

private void setData(T newData)
{
data = newData;
} // end setData

private Node getNextNode()
{
return next;
} // end getNextNode

private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedStack