Stack implementation in Java using Array

By Atul Rai | Last Updated: August 12, 2019 Previous       Next

This page will walk through custom Stack implementation in Java using Array. The Stack is a linear data structure which works on the LIFO (last-in, first-out) or FILO (first-in, last-out) operation. The last element inserted into the Stack will retrieve first and the first element inserted into the Stack will retrieve in the last.

We can perform the multiple operations on a Stack like push, pop, peek, empty, search but here we can only implement these 3 API’s:

• Push
• Pop
• Peek

Pseudo Code

Since we will use the Array to implement our custom Stack and Array is index-based which keeps the thing simple. Before starting the implementation, we need to identify the pre-requisites:

1. The suitable data structure

• we used an Array because it is index-based.

2. What will be the type of element?

• type of an element which pushed into the Stack. We used int to keep it simple.

3. What will be the capacity or initial capacity of the Stack?

• initialize the initial capacity using a constructor argument.

4. And a pointer to point the top of the Stack.

int array[];
int capacity;
int top;

StackImplementaion(int capacity) {
	this.array = new int[capacity];
	this.capacity = capacity;
	this.top = -1;
}

Why we initialize top= -1?

Because we haven’t hit the 0^th element yet. The top is to get the 0^th element when the first element pushed into the array.

Push

The push API will take an element and push that item to the Stack. It doesn’t return anything.

public void push(int item) {

	array[++top] = item;
}

Pop

Pop doesn’t take any element but it returns the item which is top of the Stack. The pop modifies the Stack and removes the top element from the Stack.

public void pop() {

	return array[top--];
}

Peek

Peek also doesn’t take any element and returns the item which is top of the Stack. The peek doesn’t modify the Stack just return the top element from the Stack.

public void peek() {

	return array[top];
}

Handle the error for Push, Pop, and Peek

Well, there will be a chance that the above API’s can throw an exception like:

Error for Push – Try to push an element into the Stack and Stack is already full.

Error for Pop and Peek – Try to get an element from the Stack but Stack is empty.

These are the basic exception that can be thrown by the API. To handle we need to check:

1. the current capacity of the Stack before pushing an element

private boolean isFull() {

	return top == capacity - 1;
}

2. and is Stack empty before pop or peek.

private boolean isEmpty() {

	return top == -1;
}

Let’s check the complete code.

package org.websparrow;

public class StackImplementaion {

	private int array[];
	private int capacity;
	private int top;

	public StackImplementaion(int capacity) {
		this.array = new int[capacity];
		this.capacity = capacity;
		this.top = -1;
	}

	public static void main(String[] args) {
		StackImplementaion stackImpl = new StackImplementaion(3);

		stackImpl.push(5);
		stackImpl.push(2);
		stackImpl.push(4);
		for (int i = 0; i < 1; i++) {

			System.out.println("Peek return the top element of the Stack: " + stackImpl.peek());

			System.out.println(
					"Pop also return the top element of the Stack but also remove the element: " + stackImpl.pop());

			System.out.println("Peek after Pop: " + stackImpl.peek());
		}

	}

	public void push(int item) {

		if (isFull()) {
			throw new RuntimeException("Stack is full.");
		}
		array[++top] = item;
	}

	public int pop() {

		if (isEmpty()) {
			throw new RuntimeException("Stack is empty.");
		}

		return array[top--];
	}

	public int peek() {

		if (isEmpty()) {
			throw new RuntimeException("Stack is empty.");
		}
		return array[top];

	}

	private boolean isFull() {

		return top == capacity - 1;
	}

	private boolean isEmpty() {

		return top == -1;
	}
}

Output:

Peek return the top element of the Stack: 4
Pop also return the top element of the Stack but also remove the element: 4
Peek after Pop: 2

References

1. Stack- Wikipedia