Implementing Queue with 2 Stacks

Posted on

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

Exit fullscreen mode

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

Enter fullscreen mode

Exit fullscreen mode

Reference:

END.

Leave a Reply

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