{{title_post}}

Problem Description:

In this problem, we have to implement a first in first out (FIFO) queue using only two stacks (LIFO). The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Basically, we have to implement some statements – PUSH, POP, PEEK, Empty. When we get “push” we have to perform PUSH operation, “pop” for POP operation. If we get “peek”, then we have to return the front of the queue, that means, the element we pop in next POP instruction. And we have to check whether the stacks are empty or not for the “empty” function.

Ideological Analysis:

We have to implement FIFO (First In First Out) using LIFO (Last In First Out). In python, actually, we don’t need two stacks and for the solution you may click here.

Today we are trying to solve this problem using two stacks. Before going deeper, let’s see a figure.

In the beginning, both stacks are empty. So, we PUSH into stack 1 until the POP request comes. When we get a POP request, we POP all elements from Stack 1 and PUSH them into Stack 2 and then we POP an element from stack 2. That means, when a POP request comes, we make Stack 1 empty and then POP from stack 2. But what if we get another PUSH request and Stack 2 is not empty? Well, according to our logic, we PUSH it to Stack 1, and then, when a POP request comes we move them to Stack 2. And POP from Stack 2, right? Okay, then let’s check the situation with a figure.

Now, if we POP, then get 7 instead of 3 (!). So, when we PUSH into Stack 1, we have to check whether Stack 2 is empty or not. If Stack 2 is not empty, then we have to retransfer those elements into Stack 1 and then PUSH the new element.

This is how we can implement Queue (FIFO) using two Stacks (LIFO).

Click here for Source Code.