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

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:

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

END.

原文链接：Implementing Queue with 2 Stacks