1
\$\begingroup\$

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<T> {

    private Queue<T> queue1;
    private Queue<T> queue2;

    public StackUsingQueue() {
        queue1 = new LinkedList<T>();
        queue2 = new LinkedList<T>();
    }


    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<T>();
    }

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


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

        System.out.println(isuq.pop());
        System.out.println(isuq.pop());
        System.out.println(isuq.pop());
    }
}
\$\endgroup\$
8
\$\begingroup\$

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:

  1. 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.
  2. You do not implement peek()
  3. 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<File> STACK = new StackUsingQueue<File>();

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<File> 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() > 0) {
                counter.wait();
            }
        }
    }
}            
\$\endgroup\$
  • \$\begingroup\$ Why? Why use a Queue to implement a stack? -- because it is an interview question. I agree its silly. but cant argue in an interview. stackoverflow.com/questions/688276/… \$\endgroup\$ – JavaDeveloper May 30 '14 at 17:27
  • \$\begingroup\$ I really need more understanding of your comment 'If people want to lock their code on something, they may use your stack, and then your synchronization is not contained. '. Could u supplement with a code sample ? \$\endgroup\$ – JavaDeveloper May 30 '14 at 17:49
  • 1
    \$\begingroup\$ @JavaDeveloper - included example usage that breaks your code. \$\endgroup\$ – rolfl May 30 '14 at 18:16
  • \$\begingroup\$ @JavaDeveloper The linked question is a famous exercise in TAOCP (vol1) and rather interesting because it shows that you can actually implement a queue efficiently using 2 stacks. The opposite is not true and hence much less interesting (there's just no clever trick here apart from the obvious). And yes you definitely can argue in an interview! How boring that'd be otherwise. \$\endgroup\$ – Voo Jun 1 '14 at 1:42
4
\$\begingroup\$

Implementation:

If you are implementing a Stack, why not implement it? (bad phrasing).

public class StackUsingQueue<T> {

Instead of that class signature I'd rather really explicitly implement Stack:

public class StackUsingQueue<T> extends Stack<T> {

On a sidenote: Stack is quite antique;) instead you should use Deque nowadays.

Naming:

queue1 and queue2 desperately scream for better names. Instead use something speaking like: dataHolderQueue, pushHelperQueue. While we're at it, on to the next point:

Scoping:

Your queue2 is only used in the push() method. as you create a new instance of it either way, why not take it away from class level and instead do:

public synchronized void push(T x) {
    Queue<T> helperQueue = new LinkedList<T>();
    helperQueue.add(x);
    helperQueue.addAll(dataHolderQueue);
    dataHolderQueue = helperQueue;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.