# Implementing Queue with 2 Stacks

Posted on

BEGIN:

I’m assuming you are familiar with the vocabulary of

• Stack

POP = Get from end

• Queue

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) {
}

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.