Task sounded simple. Implement a queue with 2 stacks, which as the methods Push(), Pop() and Front().
Well, the fundamental problem here is stack cannot give me the element at the bottom in a neat way. It has to be dirty. Also, how do I keep track of Pop() operations on the queue? 2 stacks. I need to keep track of elements in the inverse order of my stack.
Okay here's something: what if the reason we require two stacks is that we maintain, for each operation, a stack which is the right way up, and a second stack which has elements in the reverse order as the first? The first stack helps us push elements into the queue. The second stack helps with Pop() and Front(). I will call the first stack as the front stack, and second as the rear stack
Let's be naive first. Let us update the two stacks every single time any of the queue methods are called. The major testcase eater here is that there is no way to nicely invert a stack. I went with declaring a temporary stack, copying the elements of the front stack to it (std::stack has a nice copy constructor for this), and then running a while loop and pushing the top of the temporary stack to the rear stack and then popping the temporary stack, so that elements of the front stack get pushed onto the rear stack in reverse order. That was a mouthful. A lot of pushes and pops. But hopefully you got the idea.
If we do all this, and repeat it (update both stacks for every queue method call) this eats up a LOT of time. Half the testcases pass with this one.
I couldn't figure this part out, so I went to the discussion section. There I found what I had been missing. In order to explain this, I must make an analogy with what we do for dynamic arrays.
Dynamic Arrays, as you might know, are resizable arrays (std::vector for C++). Now note the parallel. There is no neat way of resizing a proper C++ array. It has to be dirty. We are going to have to re-allocate a new array, copy all the elements to the new array. There is simply no other way, as that is how the data structure works fundamentally.
So what do we do? We do it less often. Only when necessary.
Dynamic Arrays achieve a PushBack() complexity of amortized O(1) by doubling the array capacity when it is full. Similarly, we must do this reversal of stack and copying of stack elements only when it is needed.
What can change given this idea?
First, the rear stack need not be updated if it is not empty! The only time it needs to update is if it is empty. Because if we have elements left in the rear stack, the top() is still correct, no matter what we have pushed. Similarly the front stack doesn't need to still contain all the pushed elements. Once it updates rear stack, the front stack's job is essentially nothing, apart from storing the new incoming elements. Once it pushes those to the rear stack, it doesn't need to care about the elements that were transferred to the rear stack.
Therefore, that the temporary stack was unnecessary. We can directly pop from the front stack while updating the rear, instead of first making a copy.
We update the rear stack only on calls to Pop() or Front(). We needn't do so for Push(). Similarly we need to update the front stack only on calls to Push().
With all this done, the solution now passes all the testcases.
The lesson I learned was this: If there is doesn't exist any neat way of doing something. If there is something you just cannot bypass due to the fundamental nature of the tools you use to solve it, it has to be dirty. It can be done more efficiently by doing the dirty work only and only when required, and nowhere else.
PS: I pity those who noticed the pun in the title ._.
No comments:
Post a Comment