Stack with getMin method

Question

This should implement a stack that has a \$O(1)\$ getMin method. I used an auxiliary stack. Please provide comments on my solution.

import org.junit.Test;

public class Solution {

  @Test
  public void testEmptyStack(){
    StackMin<Integer> s = new StackMin<Integer>();
    System.out.println("----------------------");
    System.out.println("Empty stack");
    System.out.println(s.getMin());
  }

  @Test
  public void testRandomStack(){
    System.out.println("----------------------");
    StackMin<Integer> s = new StackMin<Integer>();
    s.push(2);
    s.push(-1);
    s.push(0);
    s.push(7);
    s.push(22);
    System.out.println("Random stack");
    s.printStack();
    System.out.println("Min element");
    System.out.println(s.getMin());
  }

  @Test
  public void testEqualities(){
    System.out.println("----------------------");
    StackMin<Integer> s = new StackMin<Integer>();
    s.push(2);
    s.push(-1);
    s.push(0);
    s.push(0);
    s.push(0);
    s.push(7);
    s.push(22);
    s.push(-1);
    s.push(-1);
    s.push(33);
    System.out.println("Stack with equalities");
    s.printStack();
    System.out.println("Min element");
    System.out.println(s.getMin());
  }

  public static void main(String[] args) {
    Solution e = new Solution();
    e.testEmptyStack();
    e.testRandomStack();
    e.testEqualities();
  }
}

class NodeV2<T> {
  private final T data;

  private final NodeV2<T> next;

  public NodeV2(T d, NodeV2<T> n) {
    data = d;
    next = n;
  }

  public NodeV2(T d) {
    this(d, null);
  }

  public T getData() {
    return data;
  }

  public NodeV2<T> getNext() {
    return next;
  }

}

class StackMin<T extends Comparable<T>> extends StackV2<T> {
  StackV2<T> auxiliaryStack = new StackV2<T>();

  void push(T element) {
    if (auxiliaryStack.isEmpty() || element.compareTo(auxiliaryStack.top.getData()) <= 0) {
      auxiliaryStack.push(element);
    }

    super.push(element);
  }

  T pop() {
    if (this.peek().compareTo(auxiliaryStack.peek()) <= 0) {
      auxiliaryStack.pop();
    }

    return super.pop();
  }

  public T getMin() {
    return auxiliaryStack.peek();
  }

}

class StackV2<T extends Comparable<T>> {
  NodeV2<T> top;

  void push(T element) {
    NodeV2<T> t = new NodeV2<T>(element, top);
    top = t;
  }

  T pop() {
    if (top != null) {
      T item = top.getData();
      top = top.getNext();
      return item;
    }
    return null;
  }

  T peek() {
    return top == null ? null : top.getData();
  }

  boolean isEmpty() {
    return top == null ? true : false;
  }

  public void printStack() {
    NodeV2<T> current = top;
    while (current != null) {
      System.out.println(current.getData());
      current = current.getNext();
    }
  }
}

Answer 1

Yay, you use tests!

Darn it, you don't use tests.

Confusing? Allow me to explain. While I totally approve of you using tests, there is a lot more to it than simply putting the @Test annotation above them.

A test is comprised of 3 aspects: Arrange, Act and Assert. Typically a test (whether it's unit, integration, functional, end-to-end, etc) will have these aspects in explicit or implicit form. Personally I like to explicitly separate them with comments (// Arrange).

Why do I mention this? Note the last aspect of AAA: Assert. This tells us that, as the last step in our test, we will verify the result we have and assert that it is what we expected.

Doing this allows us to run the tests and automatically compare the result of each test with the expected outcome. In your situation you have to manually verify that each test works as expected; can you see yourself doing that when you have 300 tests instead of 3?

This brings us to another point: all modern IDE's have integrated test runners. If you have tests, you can just run these using that instead of having to use a main() method as entrypoint for your tests.

By adapting these changes you also won't need those println's anymore which takes away focus from your actual content.

• Junit documentation
• Junit tutorial

Answer 2

  @Test
  public void testRandomStack(){
    System.out.println("----------------------");
    StackMin<Integer> s = new StackMin<Integer>();
    s.push(2);
    s.push(-1);
    s.push(0);
    s.push(7);
    s.push(22);
    System.out.println("Random stack");
    s.printStack();
    System.out.println("Min element");
    System.out.println(s.getMin());
  }

What's random about this stack? I'm reminded of this.

Perhaps a better name for this would be "PsuedoRandomStack".

---

Also, may I ask what the V2 in NodeV2 and StackV2 represent? It's not clear to me. As far as I can tell, these should simply be Node and Stack.

---

If I'm reading this correctly, there's no reason for a ternary condition here.

  boolean isEmpty() {
    return top == null ? true : false;
  }

Why not just return the result of the expression?

boolean isEmpty() {
    return top == null; 
}

If you don't like that, perhaps add the parenthesis to make it a bit more clear and explicit what is being returned.

boolean isEmpty() {
    return (top == null); 
}

Answer 3

NodeV2 should really be inner static class within StackV2, since it it not expected to be used standalone.

Also, assuming you do not want to modify your existing APIs for StackV2, consider writing helper methods for unit testing to facilitate the repetitive pushing of values into your StackMin instances:

private static <T> StackV2<T> push(final StackV2<T> stack, T... values) {
    for (final T value : values) {
        stack.push(value);
    }
    return stack;
}

Here, I also return stack so that callers of this method can daisy-chain it for other purposes if required.