a solution from Ivan Zemlyanskiy

solution.java

import java.io.*;
import java.util.*;
import org.junit.*;
import org.junit.runner.*;


public class Solution {
    public Solution(){}

    /**
     * A Stack interface
     * @param <T> a concrete type
     */
    public interface Stack<T>{
        /**
         * Pop an element off the stack; return {@code null} if no element exists
         * @return an element or {@code null}
         */
        public T pop();

        /**
         * Push an element onto the stack
         * @param e an element
         */
        public void push(T e);

        /**
         * Return the size of the stack
         * @return size of stack
         */
        public int size();
    }

    /**
     * A Queue interface
     * @param <T> a concrete type
     */
    public interface Queue<T>{
        /**
         * Dequeue an element; return {@code null} if no element exists
         * @return element or {@code null}
         */
        public T dequeue();

        /**
         * Enqueue an element onto the queue
         * @param e an element
         */
        public void enqueue(T e);

        /**
         * Return the size of the queue
         * @return size of the queue
         */
        public int size();
    }

    /**
     * A very basic implmentation of {@link Stack}
     * @param <T> concrete type
     */
    public final class DefaultStack<T> implements Stack<T> {
        Node<T> top;
        @Override
        public T pop() {
            if(top == null){
                return null;
            }
            T r = top.value;
            top = top.next;
            return r;
        }

        @Override
        public void push(T e) {
            top = new Node<>(e, top);
        }

        @Override
        public int size() {
            int c = 0;
            Node<T> ptr = top;
            while(ptr != null){
                c++;
                ptr = ptr.next;
            }
            return c;
        }

        class Node<T> {
            Node(T value, Node<T> next){
                this.value = value; this.next = next;
            }
            T value;
            Node<T> next;
        }
    }


    /* assignment below */

    /**
     * A queue implementation that does not use any collections other than {@link Stack}
     * @param <T> concrete type
     */
    public final class MyQueue<T> implements Queue<T>{

        private final Stack<T> stackLeft = new DefaultStack<>();
        private final Stack<T> stackRight = new DefaultStack<>();


        @Override
        public  T dequeue() {
            synchronized (this) {
                if (stackRight.size() > 0) {
                    return stackRight.pop();
                } else  {
                    while (stackLeft.size() != 0) {
                        stackRight.push(stackLeft.pop());
                    }
                }

                if (stackRight.size() == 0) {
                    return null;
                }
            }
            return stackRight.pop();
        }

        @Override
        public synchronized void enqueue(T e) {
            stackLeft.push(e);
        }

        @Override
        public synchronized int size() {
            return stackLeft.size() + stackRight.size();
        }
    }

    /* tests below */

    @Test
    public void testSize(){
        Queue<String> myQueue = new MyQueue<>();
        Assert.assertEquals(0, myQueue.size());
        myQueue.enqueue("a");
        Assert.assertEquals(1, myQueue.size());
        myQueue.dequeue();
        Assert.assertEquals(0, myQueue.size());
    }

    @Test
    public void testBasicQueueBehavior(){
        Queue<String> myQueue = new MyQueue<>();
        myQueue.enqueue("a");
        myQueue.enqueue("b");
        myQueue.enqueue("c");
        Assert.assertEquals("a", myQueue.dequeue());
        Assert.assertEquals("b", myQueue.dequeue());
        Assert.assertEquals("c", myQueue.dequeue());
        Assert.assertEquals(null, myQueue.dequeue());
    }

    @Test
    public void testInterleavedQueueDeque(){
        Queue<String> myQueue = new MyQueue<>();
        myQueue.enqueue("a");
        myQueue.enqueue("b");
        myQueue.enqueue("c");
        Assert.assertEquals("a", myQueue.dequeue());
        Assert.assertEquals("b", myQueue.dequeue());
        myQueue.enqueue("d");
        myQueue.enqueue("e");
        Assert.assertEquals("c", myQueue.dequeue());
        Assert.assertEquals("d", myQueue.dequeue());
        Assert.assertEquals("e", myQueue.dequeue());
        Assert.assertEquals(null, myQueue.dequeue());
    }

    /**
     * A stack implementation that does not use any collections other than {@link MyQueue}
     * @param <T> concrete type
     */
    public final class QueueStack<T> implements Stack<T>{
        private final Queue<T> queue = new MyQueue<>();

        @Override
        public T pop() {
            synchronized (this) {
                for (int i = 0; i < queue.size() - 1; i++) {
                    T element = queue.dequeue();
                    queue.enqueue(element);
                }
            }
            return queue.dequeue();
        }

        @Override
        public synchronized void push(T e) {
            queue.enqueue(e);
        }

        @Override
        public synchronized int size() {
            return queue.size();
        }
    }

    /* stack tests */
    @Test
    public void testStackSize(){
        Stack<String> myStack = new QueueStack<>();
        Assert.assertEquals(0, myStack.size());
        myStack.push("a");
        Assert.assertEquals(1, myStack.size());
        myStack.pop();
        Assert.assertEquals(0, myStack.size());
    }

    @Test
    public void testBasicStackBehavior(){
        Stack<String> myStack = new QueueStack<>();
        myStack.push("a");
        myStack.push("b");
        myStack.push("c");
        Assert.assertEquals("c", myStack.pop());
        Assert.assertEquals("b", myStack.pop());
        Assert.assertEquals("a", myStack.pop());
        Assert.assertEquals(null, myStack.pop());
    }

    @Test
    public void testInterleavedStackPop(){
        Stack<String> myStack = new QueueStack<>();
        myStack.push("a");
        myStack.push("b");
        myStack.push("c");
        Assert.assertEquals("c", myStack.pop());
        Assert.assertEquals("b", myStack.pop());
        myStack.push("d");
        myStack.push("e");
        Assert.assertEquals("e", myStack.pop());
        Assert.assertEquals("d", myStack.pop());
        Assert.assertEquals("a", myStack.pop());
        Assert.assertEquals(null, myStack.pop());
    }

}