Stack implementation using a queue I've implemented a stack using a queue.

Time complexity:

\$O(n)\$ - push(), where n is the number of elements in the queue

\$O(1)\$ - pop() 

Space complexity:

\$O(n)\$ - n is the number of elements in the queue.

I'm looking for optimizations, code review and best practices.

public class StackUsingQueue&lt;T&gt; {

    private Queue&lt;T&gt; queue1;
    private Queue&lt;T&gt; queue2;

    public StackUsingQueue() {
        queue1 = new LinkedList&lt;T&gt;();
        queue2 = new LinkedList&lt;T&gt;();
    }


    public synchronized void push(T x) {
        queue2.add(x);
        queue2.addAll(queue1);
        // swapping references rather than copying from q2 into q1.
        queue1 = queue2;
        queue2 = new LinkedList&lt;T&gt;();
    }

    public synchronized T pop() {
        return queue1.poll();
    }


    public static void main(String[] args) {
        StackUsingQueue&lt;Integer&gt; isuq = new StackUsingQueue&lt;Integer&gt;();
        isuq.push(10);
        isuq.push(20);
        isuq.push(30);

        System.out.println(isuq.pop());
        System.out.println(isuq.pop());
        System.out.println(isuq.pop());
    }
}
Why? Why use a Queue to implement a stack? A Queue, by definition, (Computer Science Definition, not Java interface) is a FIFO device. A Stack, by definition, is a LIFO device. They are significant opposites of each other. Doing it this way is .... silly.

Also, it is not using the features of a FIFO queue to do the work, it is using the features of a Collection (add, addAll, Iterable). The only methods you should be calling on the queue are add, and remove.

A native array with a size would be a much, much better implementation, and would have \$O(1)\$ add and remove complexity, with occasional \$O(n)\$ if a resize is needed.

Also, your code is buggy, three things:


You 'cheat' and use poll() for the pop, and poll() returns null if the queue is empty, but, you do not 'guard' against the null being used as a push(null) value. Thus, there is no way to test whether the stack is empty reliably.
You do not implement peek()
You leak the monitor. By using synchronized methods, you let other people control your locking system. If people want to lock their code on something, they may use your stack, and then your synchronization is not contained.


I don't like this question of yours. To me it looks like a step backwards compared to your other recent questions.

Edit: About Locking

Consider some user of your class, they want a stack that is thread safe.... and they need to coordinate between some threads.

They need a convenient object to synchronize on. STACK is there... so they use it.

Note, I would never normally write code like the following.... but, the following code will never finish... Even though, at face value, it looks fine? You understand now?

private static final ExecutorService THREAD_POOL = Executors.newFixedThreadPool(10);

private static final StackUsingQueue&lt;File&gt; STACK = new StackUsingQueue&lt;File&gt;();

private static final void myMethodProcessesFilesInParallel(File dir) {

    // this method processes Files in a folder.
    // only allow one folder to be processed at any one time. Synchronize on something: 
    synchronized(STACK) {
        List&lt;File&gt; files = dir.listFiles();
        final AtomicInteger counter = files.size();

        for (final File file : files) {
            THREAD_POOL.submit(new Runnable() {
                public void run() {
                    // STACK is thread-safe. pop() is good!
                    try {
                        File file = STACK.pop();
                        System.out.println(file.length());
                    } finally {
                        synchronized(counter) {
                            counter.decrementAndGet();
                            counter.notifyAll();
                        }
                    }
                }
            });
        }

        synchronized (counter) {
            while (counter.get() &gt; 0) {
                counter.wait();
            }
        }
    }
}