Question

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

Answer 1

Problem 3 and 4 :

Note these methods are not tested . You can test and let me know if there is anything. I will be able to fix it if there is any gap.

private boolean isTooBig() {

       if (topIndex + 1 < stack.length / 2 && stack.length > 20)

           return true;

       else

           return false;

   }

Problem 4:

   private void reduceArray() {

       int newcapacity = 3 * stack.length / 4;

       stack = Arrays.copyOf(stack, newcapacity);

   }


This can be used in follwing way in Pop

See This is how it is used in POP

public T pop()

{

T top = null;

if(isTooBig())

   reduceArray();

if (!isEmpty()) {

   top = stack[topIndex];

   stack[topIndex] = null;

   topIndex--;

} // end if

return top;

} // end pop

Thanks, let me know if there is any issues/concern. I will be happily solving those.