Implement MyQueue using two stacks

Posted on

Problem

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


}

Solution

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.

Leave a Reply

Your email address will not be published. Required fields are marked *