How to Implement Fixed Size Stack in Java

Connect with

Oracle JavaStack is ADT type of data structure which has different implementation for different purpose for fulfilling of different contextual requirement. In this article tried to implement how to implement by using fixed size array based implementation. If you want to know something basic about Stack, you can visit What is Stack Data structure.

In demonstration there are different class involved:

  1. Stack Interface which contains all the methods.
  2. Implementation of Fixed Size Stack class.
  3. Main class for demonstration of Stack implementation.

1. Stack Interface with All Methods

This is Stack interface which contains all the methods which we need to implement in its various implementation.



package com.mysoftkey.ds.stack;

/**
 * this is interface/contract for stack basic and suppliment methods.
 * @author ranjeet
 *
 */
public interface Stack {

	/**
	 * This push method used to add element.
	 * 
	 * @param data
	 */
	void push(int data)  throws Exception;

	/**
	 * This method remove top element and return that.
	 * throws exception if empty stack 
	 * @return
	 */
	int pop() throws Exception;

	/**
	 * return top element, throws if stack is empty.
	 * @return
	 */
	int top() throws Exception;

	/**
	 * This is helping method to find whether stack is empty or not.
	 * if empty return true else false.
	 * 
	 * @return
	 */
	boolean isEmpty();

	/**
	 * this method return stack length at present.
	 * 
	 * @return
	 */
	int size();

}


2. Fixed Size Stack Implementation class

package com.mysoftkey.ds.stack;

import java.util.NoSuchElementException;


/**
 * This Data structure class is used to for fixed size implementation of Stack.
 * For the simplicity, data type is here int else you can 
 * another data type of your choice.
 * 
 * @author ranjeet
 *
 */
public class FixedArrayStack implements Stack {
	
	// Length of the array used to implement the stack.
	protected int capacity;

	// Default array capacity, its better to choose power of 2.
	public static final int CAPACITY = 16;	

	// Array used to implement the stack.
	protected int[] stack;

	// Index/position of top element of stack in array.
	protected int top = -1;

	/**
	 * Initializes the stack to use an array of default length.
	 */
	public FixedArrayStack() {
		 // initialize with default capacity
		this(CAPACITY);
	}

	/**
	 * parameterized constructor to accept capacity of array. 
	 * Initializes the stack to use an array of given length.
	 * 
	 * @param capacity
	 */
	public FixedArrayStack(int length) {
		this.capacity = length;
		stack = new int[this.capacity]; 
	}

	

	@Override
	public void push(int data) throws Exception {
		if (size() == capacity){
			throw new IndexOutOfBoundsException("StackOrverflowException.");
		} else {
			stack[++top] = data;
		}
	}

	@Override
	public int top() throws Exception {
		if (isEmpty())
			throw new NoSuchElementException("Stack is empty.");
		return stack[top];
	}

	// Removes the top element from the stack. This method runs in O(1) time.
	public int pop() throws Exception {
		int data;
		if (isEmpty())
			throw new NoSuchElementException("Stack is empty.");
		data = stack[top];
		
		// dereference S[top] for garbage collection.
		stack[top--] = Integer.MIN_VALUE; 
		return data;
	}

	@Override
	public int size() {
		return (top + 1);
	}

	@Override
	public boolean isEmpty() {
		return (top < 0);
	}
	
	/* 
	 * Returns a string representation of the stack as a list of elements, with
	 * the top element at the end: [  prev, top ].
	 * 
 	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String s = "[";
		if (size() > 0)
			s += stack[0];
		if (size() > 1)
			for (int i = 1; i <= size() - 1; i++) {
				s += ", " + stack[i];
			}
		return s + "]";
	}
}

3. Main class for Stack Demo

package com.mysoftkey.ds.stack;

import java.util.Scanner;

/**
 * This is Fixed Size array implementation demo client.
 * 
 * @author ranjeet.kr@gmail.com
 *
 */
public class FixedStackMain {

  // this class is for reading input from keyboard.
  static Scanner scanner = new Scanner(System.in);
	
  // this is Stack implemented class, here fixed array size implementation.
  //static Stack stack = new FixedArrayStack();
	
  public static void main(String[] args) {
     System.out.println("Enter size of stack :");
     int lengthOfStack =  scanner.nextInt();
     Stack stack = new FixedArrayStack(lengthOfStack);
     System.out.println("Stack created with size :" + lengthOfStack);
	 
     while(true){
  	 System.out.println("\nEnter 1 for push() ");
	 System.out.println("Enter 2 for pop() ");
	 System.out.println("Enter 3 for top() ");
	 System.out.println("Enter 4 for iterate() ");
	 System.out.println("Enter 5 for exit(1) ");
		
	 int choice = scanner.nextInt();
		
	 try {
		
	    switch(choice) {
		case 1:
		   System.out.println("Enter a number to push.");
		   stack.push(scanner.nextInt());
		   break;
		
		case 2:
		   System.out.println("popped element : " + stack.pop());
		   break;
		   
		case 3:
		   System.out.println("top element : " + stack.top());
		   break;
		   
		case 4:
		    System.out.println(" elements are : " + stack.toString());
		    break;
		 
		case 5:
		    System.out.println("exit the sytem: ");
		    System.exit(1);
			break;
				
		default :
		  System.out.println("invalid option..........");
			
	  }
		
	} catch (Exception e) {
		System.err.println("error message : " + e.getMessage());
	}
    } 
	
 }

}

4. Console output of fixed Size Array based Stack Implementation

Enter size of stack :
5
Stack created with size :5

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
1
Enter a number to push.
11

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
1
Enter a number to push.
22

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
1
Enter a number to push.
33

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
3
top element : 33

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
3
top element : 33

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
4
 elements are : [11, 22, 33]

Enter 1 for push() 
Enter 2 for pop() 
Enter 3 for top() 
Enter 4 for iterate() 
Enter 5 for exit(1) 
5
exit the sytem: 

your comments/suggestions are welcome to improve this post.


Connect with

Leave a Reply

Your email address will not be published. Required fields are marked *