Implementing Queue with 2 Stacks

BEGIN:

I'm assuming you are familiar with the vocabulary of

• Stack

  PUSH = Add to end
  POP = Get from end

• Queue

  ENQUEUE = Add to end
  DEQUEUE = Return from beginning

Prerequisite: You only need to know this

• In Java when you "ADD" to ArrayList, it adds in the end.
• Similarly, if you use Javascript, you "PUSH" to an array, it adds the value in the end of the array.

So, I came across this simple yet interesting topic of implementing a Simple Queue (FIFO) with 2 Stacks (LIFO)

Having done this program in university (where I used scratch implementation in C++), I believe now more conciseness is required for interview preparations - and hence I'm using JAVA's native ArrayList to implement my own Stack and Queues.

import java.util.ArrayList;
import java.util.List;

public class MyStack {

    private final List<Integer> stack = new ArrayList<>();

    void push(int item) {
        stack.add(item);
    }

    int pop() {
        if (!stack.isEmpty()) {
            return stack.remove(stack.size() - 1);
        }
        return -1;  // if nothing found
    }

    int size() {
        return stack.size();
    }

    boolean isEmpty() {
        return stack.isEmpty();
    }
}

So, now we have our Stack - it's that simple ;)

And here's our Queue

public class MyQueueWithTwoStacks {

    private final MyStack firstStack;
    private final MyStack secondStack;

    public MyQueueWithTwoStacks() {
        this.firstStack = new MyStack();
        this.secondStack = new MyStack();
    }

    boolean isEmpty() {
        return firstStack.isEmpty() && secondStack.isEmpty();
    }

    int size() {
        return firstStack.size() + secondStack.size();
    }

    void enqueue(int item) {
        firstStack.push(item);
    }

    /**
     * We will use the second stack to out the values, if the second bucket is
     * empty that means we need to copy over all stack1 entries to it
     *
     * @return returns the value
     */
    int dequeue() {
        if (secondStack.isEmpty()) {
            while (!firstStack.isEmpty()) {
                secondStack.push(firstStack.pop());
            }
        }

        return secondStack.pop();
    }
}

Reference:

• If you like theoretical overview, here's a super nice Post by @jellybee

END.

Comments

[pentacular]

The nice thing is that you get an amortized O(1) TC and using linked lists for the stacks makes it appropriate for a purely functional implementation, if you're into that kind of thing.

[Alain Van Hout]

Isn't dequeue O(n) here?

[Saurabh Kumar]

A very good point.

If you consider the worse case where we add and remove alternatively, we perform 2 operations (one push and then one pop)
AFAIK The problem of O(n) lies with the use of ArrayList where the remove() takes O(n) to find the index.
This post was supposed to give a starting point for how the concept is done.

Can you walk through your process - maybe there's a more efficient way without adding complex logic?