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.

Blog

Implementing Queue with 2 Stacks

Saurabh Kumar

Join Our Newsletter. No Spam, Only the good stuff.

Related