SetOfStacks data structure The data structure question I was trying to solve is as follows:


  Stack of Plates:
  
  Imagine a (literal) stack of plates. If the stack gets too high, it
  might topple. Therefore, in real life, we would likely start a new
  stack when the previous stack exceeds some threshold. Implement a data
  structure SetOfStacks that mimics this. SetOfStacks should be
  composed of several stacks and should create a new stack once the
  previous one exceeds capacity. SetOfStacks.push() and
  SetOfStacks.pop() should behave identically to a single stack (that
  is, pop() should return the same values as it would if there were
  just a single stack).


I am trying to practice better data structure design, so I was looking for some feedback on my code as well as tips for going forward:

import java.util.*;

 public class StackOfPlates {

   public class StackNode {
     private int data;

     public StackNode(int d){
       data = d;
     }

     public int getData(){
       return data;
     }
   }

   List&lt;ArrayList&lt;StackNode&gt;&gt; setOfStacks;
   private int stackCapacity;

   public StackOfPlates(int c){
     setOfStacks = new ArrayList&lt;ArrayList&lt;StackNode&gt;&gt;();
     stackCapacity = c;
   }


   void push(int item){
     StackNode s = new StackNode(item);

     if(setOfStacks.isEmpty()){
       ArrayList&lt;StackNode&gt; st = new ArrayList&lt;StackNode&gt;();
       st.add(s);
       setOfStacks.add(st);
     }
     else{
       int index = setOfStacks.size() - 1;
       int currStackSize = setOfStacks.get(index).size();
       if(currStackSize == stackCapacity){
         ArrayList&lt;StackNode&gt; st = new ArrayList&lt;StackNode&gt;();
         st.add(s);
         setOfStacks.add(st);
         setOfStacks.get(index + 1).add(s);
       }
       else{
         setOfStacks.get(index).add(s);
       }
     }
   }

   StackNode pop(){
     int setOfStacksSize = setOfStacks.size();
     if(setOfStacksSize == 0) return null;

     ArrayList&lt;StackNode&gt; lastStack = setOfStacks.get(setOfStacksSize - 1);
     int lastElmtIndex = lastStack.size() - 1;
     StackNode end = lastStack.get(lastElmtIndex);
     lastStack.remove(lastElmtIndex);
     return end;
   }
 }
Good start! There are some things that can be simplified.

Reuse of Java classes

Java provides the very helpful class Deque which can behave like a stack. So you can reuse this for easier coding :). There is also a Stack class, but that one is synchronized. 

StackNode

There is no real need for StackNode. Just use generics to store the specified item directly into the Stack/Deque. This also prevents pushing and int and popping a StackNode, which is inconsistent. 

Split checking capacity, current stack to separate methods

For readability, I would try to split the handling of multiple stacks from popping and pushing, increasing readability. The push() only needs to know that there is room and pop() needs to clean up after getting the element from the stack. 

Also, if there is a method of keeping track of the current stack, the logic for checking also becomes easier.

Something like this:

public void push( T item )
{
    //Make room if needed
    ensureRoom();

    //The current stack has enough room to push the item
    currentStack().push( item );
}


(note that this is not thread-safe)

Besides easier to read, it also becomes easier to refactor. For example, if you decide not to use Deque but Stack or your own implementation, it is easier to change.

Error handling

What happens when an empty SetOfStacks gets a pop()? You should throw a nice exception to make sure that both your SetOfStacks stays consistent and make use the caller gets a nice exception. 

Variable names

int c and int d are not that great for passing on information about what the integer means. Is c capacity? And the initial capacity? Or the maximum capacity? 

Access modifiers

Make sure to apply public, protected and private to make sure you only expose functionality that needs to be exposed, and keep private stuff private.

Proposed solution

public class StackOfPlates&lt;T&gt;
{
    private Deque&lt;Deque&lt;T&gt;&gt; setOfStacks;
    private int     maxStackCapacity;

    public StackOfPlates( int maxStackCapacity )
    {
        setOfStacks = new ArrayDeque&lt;&gt;();
        this.maxStackCapacity = maxStackCapacity;
    }

    public void push( T item )
    {
        //Make room if needed
        ensureRoom();

        //the current stack has enough room to push the item
        currentStack().push( item );
    }

    private void ensureRoom()
    {
        if( setOfStacks.isEmpty()  || currentStack().size() == maxStackCapacity);
        {
            Deque&lt;T&gt; newStack = new ArrayDeque&lt;T&gt;();
            setOfStacks.add( newStack );
        }
    }

    private Deque&lt;T&gt; currentStack()
    {
        return setOfStacks.peek();
    }

    public T pop()
    {
        if (setOfStacks.isEmpty())
        {
            throw new NoSuchElementException();
        }

        //Remove top element of last sack
        T elem = currentStack().pop();

        //And remove the last stack if it is emty
        maybeRemoveLastStack();

        return elem;
    }

    private void maybeRemoveLastStack()
    {
        if (currentStack().isEmpty())
        {
            //remove empty stack
            setOfStacks.pop();
        }
    }

}