Implementing Queue using Stack

Queue and Stack are fairly Simple Data Structures that we use in our daily coding. As a matter of fact, they can be thought of the easiest of structures to maintain data.

Throughout the article, I'll be using DS to refer to Data Structure.

Queue is a DS that works on FIFO principle. The data that comes first is allowed to go out first. There are many ways of implementing queues. We are free to use arrays, linked list, and many others. But here, I am about to discuss the implementation of Queue using another DS called Stack.

Now, we all know, Stack is a DS that works on LIFO principle. I always think about stacking books one above the other so feel free to use that analogy if it helps you visualize.

I came across this question in hackerrank where they required us to implement Queue using 2 Stacks. Sounds simple right? Take a moment to think how would we be able to achieve this.

You might have come up with some solutions because there are plenty ways to do this. So why dont you try it directly?

As you can see, I have implemented stack using a list. Initially the constructor initializes an empty list. We push data by appending it to the end of the list. While popping, if we don't provide an index it pops from the end of the list. Thus, the last element to be inserted is the first one to be popped out.

Now, In the similar manner for queue we have initialized two different stacks. One for enqueue and one for dequeue.

We use enqueueStack similar to stack just for pushing data at the end of list. But for dequeueStack, we know the pop function of stack removes element from the last so what we do is; we reverse the enqueueStack and put it in dequeueStack.Thus, first element of enqueueStack becomes the last element of dequeueStack, second of enqueueStack becomes second last of dequeueStack and so on. So now if we use pop function for dequeueStack then it will remove the first element that we pushed, thus, mimicking queue.

Don't worry if this sounds confusing right now! Once you see the code you'll realize what I am talking about. In fact take a look at it right now!

And Complete main function is:

I have tried implementing this in as easy way as possible. There might be several other and better ways of implementing this. One of them is presented here!