Queue with GetMin

http://www.keithschwarz.com/interesting/code/?dir=min-queueDesign a queue that supports push_rear, pop_front, and get_min in O(1). Would that be elegantly possible too?

* The construction that enables the min-queue to work is based on a classic
 * construction for creating a queue out of two stacks. 

 * The idea behind the queue-from-stacks construction is to maintain two
 * stacks, an "old" stack and a "new" stack.  Graphically, the stacks are
 * shown here:
 *
 *                  10      1
 *                   9      2
 *                   8      3
 *                   7      4
 *                   6      5
 *                  ---    ---
 *                  new    old

* O(n) time to move over every element from the new array into the old.
 * However, in an amortized sense, the runtime of these operations is quite
 * fast.  We can show, using a proper analysis, that the amortized complexity
 * of any one operation is O(1).  To do this, we define a potential function
 * over the data structure such that P(q) is equal to the number of elements
 * in the 'new' stack.  From here, we get the following:
 *
 * 1. The actual complexity of enqueuing an element is 1 unit of work (pushing
 *    onto a stack), and it raises the potential by one.  This means that the
 *    amortized cost of the operation is 1 + DP(q) = 2 = O(1).
 * 2. The actual complexity of dequeuing an element depends on whether the old
 *    stack is empty or not:
 *
 *    *  If the old stack is empty, the actual complexity is 1 unit of work
 *       (popping off a stack) and there is no change in potential.  The
 *       amortized cost is thus 1 + DP(q) = 1 + 0 = O(1).
 *    *  If the old stack is not empty, the actual complexity is n units of
 *       work (popping n elements off one stack and moving them), plus one
 *       extra unit of work for the final pop for an actual complexity of
 *       n + 1 units of work.  However, this drops the potential by n, so the
 *       amortized complexity is n + 1 + DP(q) = n + 1 - n = 1 = O(1)
 *
 * Consequently, each operation takes amortized O(1) to complete.
 *
 * In order to use this solution to build a min-queue from two min-stacks, we
 * apply this construction to two min-stacks instead of two regular stacks.
 * The minimum element of the queue can then be found by looking at the
 * minimum element of the two stacks taken together.

Implement a queue using 2 stacks

public class StackQueue<T> {
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();

    void push(T obj) {
        s1.push(obj);
    }

    T pop() {
        if (s2.isEmpty()) {
            if (s1.isEmpty()) {
                return null;
            }
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}

Also check http://massivealgorithms.blogspot.com/2014/07/design-and-implement-special-stack-data.html