Welcome back, dear reader. So, how is it going? We hope you have understood both stacks and queues well by now and have practiced both of them well . So, let's discuss this problem.
Important Links : Question Video, Solution Video
Stack to Queue Adapter - Add Efficient
One "not so good" programmer can create 2 jobs a year. Hardwork is the only key to not being that.
Welcome back, dear reader. So, how is it going? We hope you have understood both stacks and queues well by now and have practiced both of them well . So, let's discuss this problem.
Important Links : Question Video, Solution Video
We are given two stacks, one is the main stack and the other is the helper stack. We have to adapt them and make them behave like a queue. Also, we have to take care that the add method of the queue is efficient i.e. it should be achieved in O(1) time complexity whereas the peek and remove methods can take O(n) time.
You may refer to the question video to understand the problem completely. The main challenge of this question is to convert the LIFO nature of the stack to the FIFO nature of the queue.
You may refer to the solution video to clear all your doubts about the peek and the remove methods. Now that we have studied all the methods, let us code them.
How about first trying by yourself without reading the code we provide?
java; true";
Dear reader, if you have any doubts regarding the code shown above, you may refer to the complete solution video to clear all your doubts. Now, let us discuss the time and space complexities of all of the above methods.
Add: The time complexity is O(1) because we have used the stack push method.
Size: The time complexity is O(1) as we have just returned the size of the stack.
Peek: The time complexity of the peek method is O(n) as we pooped the entire stack of n elements and then pushed them back again. So, there are two traversals. So, the time complexity will be n+n=2n i.e. O(n).
Remove: The time complexity of this method is O(n) as we pooped the entire stack of n elements and then pushed them back again. So, there are two traversals. So, the time complexity will be n+n=2n i.e. O(n).
Well the space complexity can be considered as O(n) as we are using two stacks for implementing the queue. But, these two stacks are given to us in our question, and apart from these stacks, we have not used any extra data structure or memory to implement the queue. Since the data structure that is given in the question (2 stacks in this case) is not considered in the space complexity, the space complexity will be O(1).
We hope that you got the solution completely and also understood that making add efficient will increase the time for peek and remove methods. If you still have any doubts, you may refer to the complete solution video to clear all of them.
Here are some suggestions from our side that you do not want to miss: