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?

Question

Now, for those who tried and got a "time-out error" and for those who did not bother trying, let me explain to you the most simplest and easiest solution to this problem.

First take a look at how stack can be implemented.

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!

You might wonder what are those additional checks for. Like checking the the dequeueStack is empty or not. If we dont initially check for it. The enqueueStack's elements by reversal will sit into the dequeueStack and what happens is the dequeue Stacks element which was supposed to be on first now ends up being the last. So first dequeueStack has to be emptied like shown in the code.

Similar to this, printFront prints the item which is supposed to be at the front of queue.

After this implementation, we read input from STDIN and print output to STDOUT.

Our Input is somewhat like this:

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!

The above is the detailed content of Implementing Queue using Stack. For more information, please follow other related articles on the PHP Chinese website!