How can I implement a Dynamic Array Stack in Java?

Question

I need to modify a class to create a dynamic array stack. My code at this point looks something like this:

public class DynamicArrayStack<E> implements Stack<E> {                                                                                                                                                                                                                                                                                                                                      

  private E[] elems;  //used to store the elements
  public static final int defaultIncrement = 25;
  private final int increment;

  private int top;  

  @SuppressWarnings( "unchecked" )  
  public DynamicArrayStack( int increment ) {
     this.increment = increment;

     elems = (E[]) new Object[ increment ];
     top = 0;

  }


  /** 
   * Constructor with no parameter that will initialize
   * the stack to have an array whose size is the value
   * of increment and memorise that value as the value
   * of increment.
   */  
  public void ArraySize() { }

  public boolean isEmpty() {
      return top == 0;
  }  

  public E peek() {
      return elems[ top-1 ];
  }  

  public E pop() {
      // save the top element
      E saved = elems[ --top ];
      // scrub the memory, then decrements top
      elems[ top ] = null;
      return saved;
  }  

  public void push( E elem ) {
      // stores the element at position top, then increments top
      elems[ top++ ] = elem;
  }  

  public String toString() {

      StringBuffer b;
      b = new StringBuffer( "DynamicArrayStack: {" );

      for ( int i=top-1; i>=0; i-- ) {
          if ( i!=top-1 ) {
              b.append( "," );
          }
          b.append( elems[ i ] );
      }

      b.append( "}" );

      return b.toString();
  }  
}

How do I edit the first constructor to set increment as the initial size of the stack and that same value to be used when increasing or decreasing the size of the array. My method for doing this seems way too simple. Parameter must be > 0 and a fixed number of cells are added or removed when the size of the array changes.

The second constructor should set the stack to have an array whose size is the value of increment. I keep getting errors here because I can't figure out how to do that because I thought that was already set in the first constructor. Also the size of the array as the value of increment.

Also how do I make this class capable of changing the capacity of the stack and into which method should I place that code?

The method with the javadoc is not a constructor - the name does not match the class and it returns void. Won't the while loop within the actual constructor continue forever if increment > 0? It is unclear how it would ever exit. — Richard Miskin
– Richard Miskin, Commented Mar 14, 2014 at 21:27
Additionally, what is the Stack interface you're attempting to implement. java.util.Stack is a class which you would need to extend rather that implement. — Richard Miskin
– Richard Miskin, Commented Mar 14, 2014 at 21:30
public DynamicArrayStack is the first constructor and public void ArraySize() is the second. The void is only there to keep the class compiling until I get the body. The body of the class should be correct (it was provided to me as a frame). It is the rest I need guidance with. — user3400021
– user3400021, Commented Mar 14, 2014 at 21:44

Prateek Joshi · Accepted Answer · 2016-01-03 20:34:47Z

Here is the simple java code to implement it:

1)Stack based:

  public class DynamicArrayStack {
    public static void main(String[] args) {

        DynamicStack dstack=new DynamicStack(2);
        System.out.println("--Pushing--");
        dstack.push(1);
        dstack.push(2);
        dstack.display();
        dstack.push(3);
        dstack.push(2);
        dstack.push(5);
        dstack.display();
        System.out.println("--Popping--");
        dstack.pop();
        dstack.pop();
        dstack.pop();
        dstack.display();

    }

}

class DynamicStack {
    private int top;
    private int capacity;
    private int[] array;

    public DynamicStack(int cap) {
        capacity = cap;
        array = new int[capacity];
        top = -1;
    }

    public void push(int data) {
        if (isFull()){
            expandArray();      //if array is full then increase its capacity
        }
        array[++top] = data;    //insert the data
    }

    public void expandArray() {
        int curr_size = top + 1;
        int[] new_array = new int[curr_size * 2];
        for(int i=0;i<curr_size;i++){
            new_array[i] = array[i];
        }
        array = new_array;              //refer to the new array 
        capacity = new_array.length;
    }

    public boolean isFull() {
        if (capacity == top+1)
            return true;
        else
            return false;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        } else {
            reduceSize();                 //function to check if size can be reduced
            return array[top--];
        }
    }

    public void reduceSize() {
        int curr_length = top+1;
        if (curr_length < capacity / 2) {
            int[] new_array = new int[capacity / 2];
            System.arraycopy(array, 0, new_array, 0, new_array.length);
            array = new_array;
            capacity = new_array.length;
        }
    }

    public boolean isEmpty() {
        if (top == -1)
            return true;
        else
            return false;
    }

    public void display() {
        for (int i = 0; i <= top; i++) {
            System.out.print(array[i] + "=>");
        }
        System.out.println();
        System.out.println("ARRAY SIZE:" + array.length);
    }

}

OUTPUT:

--Pushing--

1=>2=>

ARRAY SIZE:2

1=>2=>3=>2=>5=>

ARRAY SIZE:8

--Popping--

1=>2=>

ARRAY SIZE:4

2)Link List based:

   public class LinkListStack {
    public static void main(String[] args) {

        StackList stack = new StackList();
        System.out.println("--Pushing--");
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.display();
        System.out.println("--Popping--");
        stack.pop();
        stack.pop();
        stack.display();

    }
}

class Node {
    private int data;
    private Node next;

    public Node(int d) {
        data = d;
        next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}

class StackList {
    private Node top;
    private int length;

    public StackList() {
        length = 0;
        top = null;
    }

    public void push(int data) {
        Node temp = new Node(data);
        if (top == null) {
            top = temp;
        } else {
            temp.setNext(top);
            top = temp;
        }
        length++;
    }

    public int pop() {
        Node temp=top;
        int data = top.getData();
        top = top.getNext();
        temp=null;
        length--;
        return data;
    }

    public void display() {
        Node temp = top;
        if (isEmpty()) {
            System.out.println("Stack is empty");
        } else {
            while (temp != null) {
                System.out.print(temp.getData() + "=>");
                temp = temp.getNext();
            }
        }
        System.out.println();
    }

    public boolean isEmpty() {
        return (top == null);
    }

}

OUTPUT:

--Pushing--

6=>5=>4=>3=>2=>1=>

--Popping--

4=>3=>2=>1=>

Richard Miskin · Accepted Answer · 2014-03-15 08:18:15Z

Default constructor

Your default constructor could simply call your other constructor with a default increment value. For example:

public DynamicArrayStack() {
    this(defaultIncrement);
}

Expanding the array

The correct place to expand the array is within the push method. When attempting to add a new element you can check if the array is large enough, and if not create a new larger array. For example you could do the following:

@Override
public E push(final E elem) {
    // Check if we need to expand the array
    if (elems.length - 1 == top) {
        @SuppressWarnings("unchecked")
        final E[] newElems = (E[]) new Object[elems.length + increment];
        System.arraycopy(elems, 0, newElems, 0, elems.length);
        elems = newElems;
    }
    // stores the element at position top, then increments top
    elems[top++] = elem;
    return elem;
}

If you want to shrink the array the sensible place to do this would be in the pop() method. You might want to consider only reducing the length when (top + (increment*2))<elems.length to avoid repeatedly copying arrays when you're on the boundary.

Collectives™ on Stack Overflow

How can I implement a Dynamic Array Stack in Java?

2 Answers 2

Comments

Default constructor

Expanding the array

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Default constructor

Expanding the array

Comments

Your Answer

Sign up or log in

Post as a guest

Related