1
\$\begingroup\$

I am taking a helper stack, which is used during dequeue. Kindly suggest improvement or some solution with less complexity.

import java.util.ArrayDeque;
import java.util.Deque;

public class MyQueueUsingTwoStack {

    Deque<Integer> mainStack = new ArrayDeque<>();
    Deque<Integer> helperStack = new ArrayDeque<>();

    public void enqueue(int x) {
        mainStack.push(x);
    }

    //popping up all the object from mainStack to helper stack(except the last one) and then putting all object
    //from helper stack to mainStack
    public int dequeue() {
        while(!mainStack.isEmpty()) {
            helperStack.push(mainStack.pop());
        }

        int pop = helperStack.pop();

        while(!helperStack.isEmpty()) {
            mainStack.push(helperStack.poll());
        }

        return pop;

    }

    public boolean isEmpty() {
        return mainStack.isEmpty();
    }


}
\$\endgroup\$
1
\$\begingroup\$

In dequeue, you do this:

  1. pop everything from main and push to helper
  2. pop one from helper
  3. pop everything from helper and push to main

Basically moving all elements, twice.

You can do better:

  1. if helper is empty: pop everything from main and push to helper
  2. pop one from helper

This will significantly reduce the number of times elements are moved.

Don't forget to adjust isEmpty accordingly.

\$\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.