Java Coding Challenge - Stack of Plates

Introduction

In this Java coding challenge, we will simulate a stack of plates by managing multiple stacks. When one stack reaches a predefined capacity, a new stack is created. This is similar to handling real plates, where you can't stack an infinite number of plates in one pile. This problem can be solved using multiple stacks, each with a fixed size.

In this blog post, we will use multiple stacks to simulate this problem and implement basic stack operations such as push, pop, and popAt (to pop from a specific stack).

Problem Statement

You need to implement a stack of plates using multiple stacks, where each stack has a maximum size. The operations include:

• push(value): Add a new value to the stack of plates.
• pop(): Remove the top value from the stack.
• popAt(index): Remove a value from a specific stack (indicated by index).

Example:

• Input:
  • Push 25, 35, 15, -1, -3, 6, 2, 12.
  • Pop from stack 1.
  • Pop from stack 0.
• Output:
  • Stack 0: [25, 35, 15]
  • Stack 1: [-1, -3, 6]
  • Stack 2: [2, 12]
  • After pop from stack 1: 6
  • After pop from stack 0: 15

Approach

We will implement the solution using:

1. Multiple Stacks: A LinkedList of Stack<Integer> objects will be used to hold the plates. Each stack will have a fixed size, and once a stack is full, a new one is created.
2. Fixed Capacity: The capacity of each stack is limited to a constant (in this case, 3).
3. Operations:
   • push(value): Push a value to the last stack if it has space, otherwise create a new stack.
   • pop(): Pop a value from the last stack.
   • popAt(index): Pop a value from a specific stack and shift the values from subsequent stacks.

Java Code Implementation

import java.util.EmptyStackException; 
import java.util.LinkedList;
import java.util.Stack;

public class MyStack {

    private static final int STACK_SIZE = 3;  // Fixed size for each stack
    private final LinkedList<Stack<Integer>> stacks = new LinkedList<>();

    // Push a value into the set of stacks
    public void push(int value) {
        // If no stacks or last stack is full, create a new stack
        if (stacks.isEmpty() || stacks.getLast().size() >= STACK_SIZE) {
            Stack<Integer> stack = new Stack<>();
            stack.push(value);
            stacks.add(stack);
        } else {
            // Add the value to the last stack
            stacks.getLast().push(value);
        }
    }

    // Pop a value from the last stack
    public Integer pop() {
        if (stacks.isEmpty()) {
            throw new EmptyStackException();
        }

        // Find the last stack
        Stack<Integer> lastStack = stacks.getLast();
        int value = lastStack.pop();

        // If the last stack is empty, remove it
        removeStackIfEmpty();

        return value;
    }

    // Pop a value from a specific stack
    public Integer popAt(int stackIndex) {
        if (stacks.isEmpty()) {
            throw new EmptyStackException();
        }

        if (stackIndex < 0 || stackIndex >= stacks.size()) {
            throw new IllegalArgumentException("The given index is out of bounds");
        }

        // Get the value from the specific stack
        int value = stacks.get(stackIndex).pop();

        // Shift remaining elements to fill the gap
        shift(stackIndex);

        // Remove the last stack if it becomes empty
        removeStackIfEmpty();

        return value;
    }

    // Shift elements to maintain the order after a popAt operation
    private void shift(int index) {
        for (int i = index; i < stacks.size() - 1; ++i) {
            Stack<Integer> currentStack = stacks.get(i);
            Stack<Integer> nextStack = stacks.get(i + 1);

            // Move the bottom element from the next stack to the current stack
            currentStack.push(nextStack.remove(0));
        }
    }

    // Remove the last stack if it's empty
    private void removeStackIfEmpty() {
        if (stacks.getLast().isEmpty()) {
            stacks.removeLast();
        }
    }

    // Print all stacks
    public void printStacks() {
        for (int i = 0; i < stacks.size(); i++) {
            System.out.println("\nStack " + i + ": ");
            System.out.print("BOTTOM -> ");
            for (int value : stacks.get(i)) {
                System.out.print(value + " ");
            }
            System.out.print(" <- TOP\n");
        }
    }
}

Explanation

1. push(int value)

The push() method adds a value to the last stack if the stack has space, otherwise, it creates a new stack.

public void push(int value) {
    if (stacks.isEmpty() || stacks.getLast().size() >= STACK_SIZE) {
        Stack<Integer> stack = new Stack<>();
        stack.push(value);
        stacks.add(stack);
    } else {
        stacks.getLast().push(value);
    }
}

2. pop()

The pop() method removes the top value from the last stack. If the stack becomes empty, it is removed from the list.

public Integer pop() {
    if (stacks.isEmpty()) {
        throw new EmptyStackException();
    }
    int value = stacks.getLast().pop();
    removeStackIfEmpty();
    return value;
}

3. popAt(int stackIndex)

The popAt() method removes the top value from a specific stack, identified by its index. It also ensures that elements from subsequent stacks are shifted to maintain balance.

public Integer popAt(int stackIndex) {
    if (stackIndex < 0 || stackIndex >= stacks.size()) {
        throw new IllegalArgumentException("The given index is out of bounds");
    }
    int value = stacks.get(stackIndex).pop();
    shift(stackIndex);
    removeStackIfEmpty();
    return value;
}

4. shift(int index)

The shift() method ensures that the elements are balanced across stacks after an element is removed from a specific stack. It moves the bottom element from the next stack to the current one.

private void shift(int index) {
    for (int i = index; i < stacks.size() - 1; ++i) {
        Stack<Integer> currentStack = stacks.get(i);
        Stack<Integer> nextStack = stacks.get(i + 1);
        currentStack.push(nextStack.remove(0));  // Shift element
    }
}

Main Class to Test the Implementation

package coding.challenge;

public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack();

        stack.push(25);
        stack.push(35);
        stack.push(15);
        stack.push(-1);
        stack.push(-3);
        stack.push(6);
        stack.push(2);
        stack.push(12);

        stack.printStacks();
        
        System.out.println("\n\nPop from stack 1: " + stack.popAt(1));
        stack.printStacks();
        
        System.out.println("\n\nPop from stack 0: " + stack.popAt(0));
        stack.printStacks();
    }
}

Example Output:

Stack 0: 
BOTTOM -> 25 35 15  <- TOP

Stack 1: 
BOTTOM -> -1 -3 6  <- TOP

Stack 2: 
BOTTOM -> 2 12  <- TOP


Pop from stack 1: 6

Stack 0: 
BOTTOM -> 25 35 15  <- TOP

Stack 1: 
BOTTOM -> -1 -3 2  <- TOP

Stack 2: 
BOTTOM -> 12  <- TOP


Pop from stack 0: 15

Stack 0: 
BOTTOM -> 25 35 -1  <- TOP

Stack 1: 
BOTTOM -> -3 2 12  <- TOP

Conclusion

In this blog post, we designed a Stack of Plates in Java using multiple stacks with fixed capacities. The solution handles pushing, popping, and popping from a specific stack, while maintaining the balance between stacks. This approach can be extended to handle more complex use cases where managing a large number of items across multiple stacks is necessary.