### DS and Algorithms in Java

In this article, we will learn how to implement a Dynamic Stack using an Array. In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays.
First, let’s consider how we implemented a simple array based stack in our previous article Stack Implementation using Array in Java. We took one index variable top which points to the index of the most recently inserted element in the stack. To insert (or push) an element, we increment top index and then place the new element at that index.
Similarly, to delete (or pop) an element we take the element at top index and then decrement the top index. We represent an empty queue with a top value equal to –1.
Now, let's implement Stack using a dynamic array that is if the array is full, create a new array of twice the size, and copy the items. With this approach, pushing n items takes time proportional to n (not n2).
If you are new to Stack Data Structure then read our Stack related articles on Stack Data Structure in Java

## Dynamic Stack Implementation using Array

The input to below program
• Stack size: : 2
• Push elements to stack: 5, 8, 2, 9
```/**
* This class implements a Dynamic Stack using a regular array
*
*/
public class StackImplUsingDynamicArray {
/** The max size of the Stack */
private int maxSize;
/** The array representation of the Stack */
private int[] stackArray;
/** The top of the stack */
private int top;

/**
* Constructor
*
* @param size
*            Size of the Stack
*/
public StackImplUsingDynamicArray(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}

/**
* Adds an element to the top of the stack
*
* @param value
*/
public void push(int value) {
if (!isFull()) { // Checks for a full stack
top++;
stackArray[top] = value;
} else {
resize(maxSize * 2);
push(value);// don't forget push after resizing
}
}

/**
* Removes the top element of the stack and returns the value you've removed
*
* @return value popped off the Stack
*/
public int pop() {
if (!isEmpty()) { // Checks for an empty stack
return stackArray[top--];
}

if (top < maxSize / 4) {
resize(maxSize / 2);
return pop();// don't forget pop after resizing
} else {
return -1;
}
}

/**
* Returns the element at the top of the stack
*
* @return element at the top of the stack
*/
public int peek() {
if (!isEmpty()) { // Checks for an empty stack
return stackArray[top];
} else {
System.out.println("The stack is empty, cant peek");
return -1;
}
}

private void resize(int newSize) {
int[] transferArray = new int[newSize];

for (int i = 0; i < stackArray.length; i++) {
transferArray[i] = stackArray[i];
stackArray = transferArray;
}
maxSize = newSize;
}

/**
* Returns true if the stack is empty
*
* @return true if the stack is empty
*/
public boolean isEmpty() {
return (top == -1);
}

/**
* Returns true if the stack is full
*
* @return true if the stack is full
*/
public boolean isFull() {
return (top + 1 == maxSize);
}

/**
* Deletes everything in the Stack
*
* Doesn't delete elements in the array but if you call push method after
* calling makeEmpty it will overwrite previous values
*/
public void makeEmpty() { // Doesn't delete elements in the array but if you
top = -1; // push method after calling makeEmpty it will overwrite
// previous values
}

public static void main(String args[]) {
StackImplUsingDynamicArray myStack = new StackImplUsingDynamicArray(2); // Declare a stack of
// Populate the stack
myStack.push(5);
myStack.push(8);
myStack.push(2);
myStack.push(9);

System.out.println("*********************Stack Array Implementation*********************");
System.out.println(myStack.isEmpty()); // will print false
System.out.println(myStack.isFull()); // will print true
System.out.println(myStack.peek()); // will print 9
System.out.println(myStack.pop()); // will print 9
System.out.println(myStack.peek()); // will print 2
}
}```
Output:
``````*********************Stack Array Implementation*********************
false
true
9
9
2``````

## Performance

Let n be the number of elements in the stack. The complexities for operations with this representation can be given as:
• Space Complexity (for n push operations) O(n)
• Time Complexity of create Stack: DynArrayStack () O(1)
• Time Complexity of push() O(1) (Average)
• Time Complexity of pop() O(1)
• Time Complexity of top() O(1)
• Time Complexity of isEmpty() O(1)
• Time Complexity of isStackFull () O(1)
• Time Complexity of deleteStack() O(1)
Note: Too many doublings may cause memory overflow exception.