Skip to content
Home » Posts » What is a stack?

What is a stack?

    Stack is a data structure which works on LIFO (Last In First Out) pattern. Elements in a stack can be inserted or taken out from one side only. Inserting an element in the stack is referred to as pushing on the stack. Similarly, deleting or taking an element out from the stack is called as popping from the stack.

    Stack

    Let’s try to create our own stack and implement its basic operations. We will be using an array to mimic a stack and maintain a variable “top” which will store the index of the latest element added to the stack.

     Push

    	public void push(T item) throws StackOverflowException {
    		if (top == (stack.length - 1)) {
    			throw new StackOverflowException();
    		}
    
    		stack[++top] = item;
    	}

    In push method, if the top is pointing to the last element of the array, we will throw a Stack Overflow Exception. Otherwise, we will add the element to the stack.

    Overflow condition

    Pop

    	public T pop() throws StackUnderflowException {
    		if (top == -1) {
    			throw new StackUnderflowException();
    		}
    
    		return (T) stack[top--];
    	}

    In pop method, if the stack if empty, we throw a Stack Underflow Exception. Otherwise, we return the element at the top of the stack and reduce the top index.

    Underflow condition

    Peek

    	public T peek() throws StackUnderflowException {
    		if (top == -1) {
    			throw new StackUnderflowException();
    		}
    
    		return (T) stack[top];
    	}

    In this method, we return the top element of the stack but do not pop it. It also throws Stack Underflow Exception.

    Complete stack class implementation

    Below is a class representing stack in Java.

    package com.theeaconitedev;
    
    public class Stack<T> {
    	private Object[] stack = null;
    	private int top = -1;
    
    	public Stack(int size) {
    		stack = new Object[size];
    	}
    
    	public void push(T item) throws StackOverflowException {
    		if (top == (stack.length - 1)) {
    			throw new StackOverflowException();
    		}
    
    		stack[++top] = item;
    	}
    
    	public T pop() throws StackUnderflowException {
    		if (top == -1) {
    			throw new StackUnderflowException();
    		}
    
    		return (T) stack[top--];
    	}
    
    	public T peek() throws StackUnderflowException {
    		if (top == -1) {
    			throw new StackUnderflowException();
    		}
    
    		return (T) stack[top];
    	}
    
    	public boolean isEmpty() {
    		return top == -1;
    	}
    }
    package com.theeaconitedev;
    
    public class StackUnderflowException extends Exception {
    	private static final long serialVersionUID = 1L;
    
    	public StackUnderflowException() {
    		super("Stack Underflow Exception");
    	}
    }
    package com.theeaconitedev;
    
    public class StackOverflowException extends Exception {
    	private static final long serialVersionUID = 1L;
    
    	public StackOverflowException() {
    		super("Stack Overflow Exception");
    	}
    }

    Testing our stack class

    Let’s try out our stack by doing some operations on it.

    package com.theeaconitedev;
    
    public class StackImplementation {
    	public static void main(String[] args) {
    		Stack<String> stack = new Stack<>(5);
    
    		try {
    			stack.push("Tony");
    			stack.push("Steve");
    			stack.push("Natasha");
    			stack.push("Clint");
    			stack.push("Bruce");
    			stack.push("Thor");
    		} catch (StackOverflowException ex) {
    			ex.printStackTrace();
    		}
    
    		try {
    			System.out.println(String.format("%s is on top of the stack.", stack.peek()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    			System.out.println(String.format("Popping %s from stack", stack.pop()));
    		} catch (StackUnderflowException ex) {
    			ex.printStackTrace();
    		}
    	}
    }
    
    com.theeaconitedev.StackOverflowException: Stack Overflow Exception
    	at com.theeaconitedev.Stack.push(Stack.java:13)
    	at com.theeaconitedev.StackImplementation.main(StackImplementation.java:13)
    Bruce is on top of the stack.
    Popping Bruce from stack
    Popping Clint from stack
    Popping Natasha from stack
    Popping Steve from stack
    Popping Tony from stack
    com.theeaconitedev.StackUnderflowException: Stack Underflow Exception
    	at com.theeaconitedev.Stack.pop(Stack.java:21)
    	at com.theeaconitedev.StackImplementation.main(StackImplementation.java:25)

    In the above code, if you observe the output, we get a Stack Overflow Exception when we try to push “Thor” in our stack. Then, items from the stack are popped in the reverse order they were added (LIFO). In the last, we get a Stack Underflow Exception when we try to pop from an empty array.

    Leave a Reply

    Your email address will not be published.