In this post, we are going to talk about an interesting problem. As the title suggests, our goal is to implement a Queue using Stacks.
In case you are not familiar with stacks or queues or you want to refresh your memory, you can refer to the below posts.
Stack Implementation in Javascript
Queue Implementation in Javascript
We also a video describing this problem and discussing the possible solution.
1 – The Issue with the problem
Now, right off the bat, you might wonder as to how this is possible.
How can we possibly make a stack behave like a queue?
After all, both of these data-structures behave quite differently. Stacks are a LIFO or Last-In-First-Out data-structure. On the other hand, Queues are FIFO or First-In-First-Out. Their core behavior is vastly different from each other.
Our job is to find a way to make it possible.
Usually, to solve such problems, we have to get over our mental block and understand that one trick to solve them.
There is one thing that can help us solve this particular problem. And that’s the word stacks in our Queue using Stacks problem. In other words, we can use more than one stack to solve this problem.
So let’s see how we can go about this solution.
2 – The Push and Pop Stacks
Let’s consider we have one empty stack.
As you can see, this stack can take up to 5 elements. After we push the elements 1, 2, 3, 4, 5 into the stack, it will look like below:
Currently, the top most element in our stack is 5. In other words, if we use pop(), we will get 5.
However, for the consumer of our Queue, when they use dequeue, they expect to get the element 1 i.e. the first element that was inserted. But since we are using a single stack, we have no way to access the element 1 without popping all the elements above it.
So how can we solve the problem?
We need to use another stack where we push all the elements that we pop from the first stack. In other words, when a dequeue request is made by the client, we pop all the elements from the first stack and push them into the second stack. See below
If you see above, we have popped all the elements above 1 and pushed them into the second stack or the pop stack.
Our first stack (also known as the push stack) has only one element remaining. In other words, the first element. We can easily pop this element and return it when the client issues a dequeue function.
3 – Handling Dequeue Operations
There is another thing that you might have noticed already. Our pop stack now contains the elements in the order they were inserted into our imaginary queue implementation.
In other words, if there is another dequeue request now, we can easily pop the top element from the pop stack.
The pop request will go in the order 2, 3, 4, 5. All of these operations will run in the usual time complexity of O(1) while at the same time honoring the basic principle of Queue i.e. First-In-First-Out.
Only when the pop stack is empty and there is a dequeue request, we have to worry about shifting elements from the push stack to the pop stack.
4 – Handling Enqueue Operations
The Enqueue operation is responsible for pushing new elements into the Queue. In the case of our two-stack implementation, this means pushing new elements into the push stack.
Basically, we don’t touch the pop stack at all. We just push the elements into the push stack. Only when there is a dequeue request, we transfer all the elements to the pop stack from where they can be popped.
See below illustration:-
As you can see, the push stack is independent from the pop stack.
5 – The Implementation
Enough of the explanation. I think you want to look at some code now.
Below is how we have implemented it. It is also available as a Gist.
Here, we have implemented our Stack using Linked List. If you wish to have details about it, you can check out Stack Implementation in Javascript.
The code for our Queue using Stacks implementation is pretty self-explanatory. However, if you have any comments or queries, please do sound off in the comments section below.
0 Comments