Top 5 Stack Interview Questions in Java

Exercise 1: Implementing a Basic Stack

Exercise 1: Implementing a Basic Stack

Objective: Implement a basic stack with push, pop, and peek methods.

public class BasicStack {
    private Node top;

    public BasicStack() {
        this.top = null;
    }

    public void push(int data) {
        Node node = new Node(data);
        node.next = top;
        top = node;
    }

    public int pop() {
        if (top == null) throw new IllegalStateException("Stack is empty");
        int data = top.data;
        top = top.next;
        return data;
    }

    public int peek() {
        if (top == null) throw new IllegalStateException("Stack is empty");
        return top.data;
    }

    private static class Node {
        int data;
        Node next;

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

Exercise 2: Checking Balanced Parentheses

Objective: Write a method to determine if a string of parentheses is balanced using a stack.

public boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            if (stack.isEmpty()) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();
}

Exercise 3: Reverse a String using a Stack

Objective: Create a method to reverse a string using stack operations.

public String reverseString(String str) {
    Stack<Character> stack = new Stack<>();
    for (char ch : str.toCharArray()) {
        stack.push(ch);
    }

    StringBuilder reversed = new StringBuilder();
    while (!stack.isEmpty()) {
        reversed.append(stack.pop());
    }

    return reversed.toString();
}

Exercise 4: Implement Max Stack

Objective: Extend the stack to include a max method that returns the maximum element in the stack.

public class MaxStack {
    private Node top;
    private int max = Integer.MIN_VALUE;

    public void push(int data) {
        if (data > max) max = data;
        Node node = new Node(data, max);
        node.next = top;
        top = node;
    }

    public int pop() {
        if (top == null) throw new IllegalStateException("Stack is empty");
        int data = top.data;
        top = top.next;
        max = (top != null) ? top.max : Integer.MIN_VALUE;
        return data;
    }

    public int max() {
        if (top == null) throw new IllegalStateException("Stack is empty");
        return top.max;
    }

    private static class Node {
        int data, max;
        Node next;

        Node(int data, int max) {
            this.data = data;
            this.max = max;
        }
    }
}

Exercise 5: Evaluate Postfix Expression

Objective: Write a function to evaluate a postfix expression (reverse Polish notation) using a stack.

public int evaluatePostfix(String expression) {
    Stack<Integer> stack = new Stack<>();

    for (char c : expression.toCharArray()) {
        if (Character.isDigit(c)) {
            stack.push(c - '0');
        } else {
            int val1 = stack.pop();
            int val2 = stack.pop();
            switch (c) {
                case '+': stack.push(val2 + val1); break;
                case '-': stack.push(val2 - val1); break;
                case '*': stack.push(val2 * val1); break;
                case '/': stack.push(val2 / val1); break;
            }
        }
    }
    return stack.pop();
}

These exercises cover fundamental operations of a stack, offering a mix of implementation details and practical applications. They are suitable for educational purposes, helping students understand and practice stack operations and their usage in different scenarios.