loading...
Cover image for Implementing Queue with 2 Stacks

Implementing Queue with 2 Stacks

saurabhpro profile image Saurabh Kumar ・2 min read

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:

END.

Discussion

pic
Editor guide
Collapse
alainvanhout profile image
Alain Van Hout

Isn't dequeue O(n) here?

Collapse
saurabhpro profile image
Saurabh Kumar Author

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?

Collapse
pentacular profile image
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.