Code Destine

Problem Statement

Design a Stack (LIFO) data structure using Dynamic Array. The Stack data structure will supports the following operations:

1. push(N) :- It insert element N onto the top of the stack.
2. pop() :- It removes and returns the element from the top of the stack.
3. peek() :- It returns (not remove) the element from the top of the stack.
4. isEmpty() :- It checks whether the stack is empty or not.
5. size() :- It return the total number of elements.
6. iterator() :- It returns the java iterator object for iterating through the elements of the stack.

Example 

Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.peek(); -- value: 30
stack.pop();  -- value: 30
stack.isEmpty(); -- value: false
stack.size(); -- value: 2

Solution

Dynamic array is an array whose size automatically increased when it gets too full and, its size gets decreased when it is too empty.

We have to implement a dynamic array using an array object provided in java language. For this first create the following three variables, these variables will help us to decide when the size of the array should be increased and when it should be decreased.

1. Initial capacity:- Size of the array during its creation.
2. Increase Factor:- Multiplication factor by which the array size is increased, for example, increase factor 2 means the size of the array is double every time it gets too full.
3. Decrease factor:- It decides when the size of the array should be decreased.

In the context of the stack data structure, the increment and decrement of array size work in the following way:

1. Increase size :- During the push, operation checks if an array is 3/4 (75%) full if yes, then create a new array of size (the current size of array multiply by increase factor) and copy the elements from the old array to a new array.
2. Decrease size :- During the pop, operation check if the total number of elements in the array are less than the size of the array/the decrease factor, then create a new array of size (the current size of array multiply by increase factor) and copy the elements from the old array to a new array.

Each operation of the stack will work in the following way:

1. push(N) :- It assign the element N at counter index and increase its value by 1.
2. pop() :- It decrease the value of counter variable by 1 and returns its value after making it null.
3. peek() :- It returns the value at counter-1 index.
4. isEmpty() :- If value of counter variable is 0, then returns true otherwise returns false.
5. size() :- It returns the value of counter variable.
6. iterator() :- It returns the object of StackIterator class.

Stack Interface

public interface Stack<T> extends Iterable<T> {

	public void push(T t);
	
	public T pop();
	
	public T peek();
	
	public boolean isEmpty();
	
	public int size();
	
}

Stack Implementation

import java.util.Iterator;

public class DynamicArrayStack<T> implements Stack<T> {
	
	private T[] arr;
	private int counter;
	private final int intialSize = 10; 
	private final int increasefactor = 2; 
	private final int decreasefactor = 4; 
	
	public DynamicArrayStack() {
		this.arr = (T[])new Object[intialSize];
	}
	
	@Override
	public void push(T t) {
		if(counter == (this.arr.length*3)/4){
			amortisedArray(increasefactor*this.arr.length);
		}
		arr[counter++] = t;
	}
	
	@Override
	public T pop() {
		if(counter == 0){
			System.out.println("Stack is empty");
		}else{
			if(counter < this.arr.length/decreasefactor && this.arr.length > intialSize){
				amortisedArray(this.arr.length/increasefactor);
			}
			T temp = arr[--counter];
			arr[counter] = null;
			return temp;
		}
		return null;
	}
	
	@Override
	public T peek() {
		if(counter == 0){
			System.out.println("Stack is empty");
			return null;
		}
		return arr[counter-1];
	}
	
	private void amortisedArray(int size){
		T[] newArray = (T[])new Object[size];
		for(int i=0;i<counter;i++){
			newArray[i] = this.arr[i];
		}
		this.arr = newArray;
	}

	@Override
	public boolean isEmpty() {
		return counter == 0;
	}

	@Override
	public int size() {
		return counter;
	}

	@Override
	public Iterator<T> iterator() {
		return new StackIterator<T>(counter,arr);
	}
	
	private class StackIterator<T> implements Iterator<T>{

		private int counter;
		private T[] arr;
		
		public StackIterator(int counter,T[] arr) {
			super();
			this.counter = counter;
			this.arr = arr;
		}

		@Override
		public boolean hasNext() {
			return counter > 0;
		}

		@Override
		public T next() {
			if(counter == 0){
				System.out.println("Stack is empty");
			}else{
				return arr[--counter];
			}
			return null;
		}		
	}
}

Similar Post

1. Find Words That Can Be Formed by Characters
2. Day of the Week
3. Rotate Array

That’s all for Design Stack using Dynamic Array in Java, If you liked it, please share your thoughts in a comments section and share it with others too.