Hi,
My doubt is: Why you are pushing the elements back to stack1 from stack2 during dequeue operation.
For the first time, we need to push everything to stack2.
But for second or later dequeue operations, we could just pop() the element from stack2 and just printed them (until the stack2 is not empty). And for enqueue() just push the new element to stack1.
This way the amortized complexity would be O(n) for dequeue as well.
Regarding the Queue using Stacks EnqueueEfficient
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
Method 1 (making dequeue efficient) moves all the elements twice in enQueue operation.
While method 2 (making enqueue efficient) in deQueue operation moves the elements once and moves elements only if stack2 empty. So, the amortized complexity of the dequeue operation becomes theta(1)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.