Facebook interview question: Implementing a queue with two stacks

Here’s the problem statement:

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.

int pop() Removes the element from the front of the queue and returns it.

int peek() Returns the element at the front of the queue.

boolean empty() Returns true if the queue is empty, false otherwise.

Background

We can’t solve this question without first understanding what a stack and queue are. You can think of a stack as a list of numbers like [1,2,3,4], and there’s a special operation, pop() , that gives you the *last* element of the list (4 in this example). If you call pop() again, you would get 3, then 2, then 1.

You can also think of a queue like a list of numbers, but the difference is pop() will give you *1* (not 4). If you call it again, then you get 2, then 3, then 4.

So a simple trick for remembering is you can visualize a “stack” as literally a stack of plates. If you add a plate to the top, and then you want to remove a plate, you’d take from the top because it’s easier! This is what’s known as “LIFO”, or “last in first out.”

A queue literally means “line” — people in Europe will tell you to go to “form a queue” or “queue up”! And how does a line work? People at the front of the line get to go first and all the way back to the last person who just joined the line. This is what’s known as “first in first out.”

Problem Explanation

So now we have an understanding of a queue and a stack, how do we implement a queue with *two* stacks?

The key insight here is that a queue and stack are kind of opposites, right? If I could reverse the order of the stack, then call pop() , that’d basically be as if I had called that on a queue!

Then I’ll have one stack just be a regular stack that I’ll add elements to, and then one stack be a queue. I’ll call the stack S and the queue Q.When I call:

push(x) : I’ll add the element to S.

peek() :I’ll see if Qhas anything in it. If not, I’ll keep callingpop() on S , and appending to Q . Then I’ll return the last element in Q.

pop() : Same thing as peek() but I’ll also *remove* the last element in Q.

empty() : Same as peek() but I’ll return if the length of Q is 0.

So, for simplicity’s sake, let’s assume that calls to pop() and peek() are valid (as in, we won’t call those when no elements are in the queue). This is how the code looks:

We define a helper function load_queue() to move everything in the stack into the queue, but in reverse order. The rest should be pretty straightforward, but if something isn’t clear, feel free to leave a question in the comments!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!