See the original problem on HackerRank.
This is a typical challenge where the environment we have to work in is constrained and we have to find a solution under some conditions. Same story when we are not allowed to allocate extra space, or when some basic operation is disabled (e.g. for loop).
Why “constrained” challenges make perfect sense
Although such challenges could seem senseless, they are instead very useful to improve our ability to adapt. In the real life this skill is generally very important. Suppose, for example, our company builds software to view and process data. Our users can create their own analysis tools and post-processing scripts by coding in a custom language (generally called DSL - Domain Specific Language). In this case users cannot use anything but such a custom language. They have to implement their scripts in terms of the available constructs.
Actually, this always applies, even when we code in our favourite fully-fledged programming language. We generally don’t perceive any limitations just because we are very familiar with it. Ability to adapt, that’s the point.
Clearly, another good reason to face with this kind of problems is to challenge ourselves and practice.
Queue using Two Stacks Solutions
The key to solving this problem is to understand that stacks and queues are opposite in terms of their access, and that there is no mechanism by which a single stack alone can implement a queue.
Our solution uses an input stacks and an output stack. The enqueue operation is just a stack push (constant), whereas in the dequeue operation we need to transfer the elements of the input stack into the output. We do transfer only when the output stack is empty.
A common error is to transfer data back to the input stack, this could lead to timeout.
Here is a C++ implementation:
In languages like Python you should solve this problem by only using lists,
In this solution we decided to make
pop “expensive” and
push “cheap”. We can do the opposite, for example if we know that for our scenario
pop is called much more than
That’s a typical tradeoff we can play with.