Custom Stack Implementation in Java

In this article, we will be discussing implementing stack data structure in Java and perform multiple stack operations such as pop(), push() and peek(). We will also take a look at the time complexity for these operations. We will be using LinkedList for our stack implementation.

What is Stack

Stack is a linear data structure in which insertion and deletion are done at one end, called as top. The last element inserted is the first one to be deleted. Hence, it is called Last in First Out(LIFO) or First in Last Out(FILO) list.

When an element is inserted in a stack, the concept is called a push, and when an element is removed from the stack, the concept is called pop. A stack throws EmptyStackException when we try to pop elements from an empty stack commonly known as underflow situations. Overflow is a situation when we try to push an element in a full stack.

Common Stack operations

push(): Inserts data onto stack.

pop(): Removes and returns the last inserted element from the stack.

peek(): Returns the last inserted element without removing it.

Now, let us start implemnting a custom stack and perform all the stack operations discussed above. We will be using LinkedList to implement our Stack. You can visit my another article about implementing Linked List in Java.

Advantages of Using LinkedList for Stack Implemenation

• Grows and shrinks gracefully.
• Every operation takes constant time O(1).
• Every operation uses extra space and time to deal wih references.

Stack Node Implementation

As we will be using linked list to implement our stack, we need to define our Node first. This is the same Node class that we used in our LinkedList implementation.

public class Node {

    private int data;
    private Node nextNode;

    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

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

    public Node getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }
}

It contains a reference of another node called as nextNode and the data as a member variable which can be of any other data type.

Different Stack Operations Implementation

Below is the skeleton of our Stack class.

public class CustomStack {

    int length = 0;
    Node top = null;

    public CustomStack(){
    }

...
...

    public int size(){
        return length;
    }

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

Stack Push Operation

Push operation is implemented by inserting an element at the beginning of the list. Below push operation adds the specified data to the top of the stack

public void push(int data) {
        Node tempNode = new Node(data);
        tempNode.setNextNode(top);
        top = tempNode;
        length++;
    }

Stack Pop Operation

Pop operation is implemented by deleting the head node.

public int pop() {
        if(isEmpty()){
            throw new EmptyStackException();
        }
        Node node = top;
        top = top.getNextNode();
        length--;
        return node.getData();
    }

Stack Peek Operation

This implementation returns a reference to the data at the top of the stack but it is not removed from the stack.

public int peek(){
        if(isEmpty()){
            throw new EmptyStackException();
        }
        return top.getData();
    }

Stack Performance

Let n be the number of elements in the stack.

Space Complexity : O(n)
Time complexity of push() : O(1)
Time complexity of pop() : O(1)
Time complexity of isEmpty() : O(1)
Time complexity of push() : O(1)

Conclusion

In this article, we discussed implementing stack data structure in Java with LinkedList and perform multiple stack operations such as pop(), push() and peek(). We also looked at the time complexity for these operations.