SetOfStacks data structure

Question

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<ArrayList<StackNode>> setOfStacks;
 private int stackCapacity;
 public StackOfPlates(int c){
 setOfStacks = new ArrayList<ArrayList<StackNode>>();
 stackCapacity = c;
 }
 void push(int item){
 StackNode s = new StackNode(item);
 if(setOfStacks.isEmpty()){
 ArrayList<StackNode> st = new ArrayList<StackNode>();
 st.add(s);
 setOfStacks.add(st);
 }
 else{
 int index = setOfStacks.size() - 1;
 int currStackSize = setOfStacks.get(index).size();
 if(currStackSize == stackCapacity){
 ArrayList<StackNode> st = new ArrayList<StackNode>();
 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<StackNode> lastStack = setOfStacks.get(setOfStacksSize - 1);
 int lastElmtIndex = lastStack.size() - 1;
 StackNode end = lastStack.get(lastElmtIndex);
 lastStack.remove(lastElmtIndex);
 return end;
 }
 }

Answer 1

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<T>
{
 private Deque<Deque<T>> setOfStacks;
 private int maxStackCapacity;
 public StackOfPlates( int maxStackCapacity )
 {
 setOfStacks = new ArrayDeque<>();
 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<T> newStack = new ArrayDeque<T>();
 setOfStacks.add( newStack );
 }
 }
 private Deque<T> 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();
 }
 }
}

• Coder007: Thank you very much for your clean and thorough feedback, it helped me a lot :)
• Coder007: As an aside I am just wondering, if I wanted to index into a specific index in setOfStacks in order to push onto a particular stack within the set, could I still use an AarrayDeque or would an ArrayList be better in that case?
• Rob Audenaerde: You're welcome. If you want to index in a specific stack, you change the entire problem :) You need indexed access, so probably theList interface fits better.