We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It's not taking O(n) time for insertion. As you can see in the code, for insertion, the element is being pushed onto the "rear" stack. That's all for a push(element) operation which takes O(1) time. Now, for front() and pop() operations only, all the elements present in the "rear" stack are moved to the "front" stack in case "front" stack is empty. Note the case
when the elements are moved. You did not take this case into consideration which actually makes the time complexity for front() and pop() operations as O(1) . How? You mentioned that we need to transfer n elements from 'Rear' stack to 'Front' stack but you should also note that no element is being moved more than once. Hence, time complexity for both front() and pop() operations is "O(1) + time to move one element from 'rear' stack to 'front' stack if not present in the 'front' stack". Time taken to move includes one pop() operation in the 'rear' stack and one push() operation in the 'front' stack, which is O(1). Please correct me if I am wrong.
Queue using Two Stacks
You are viewing a single comment's thread. Return to all comments →
It's not taking O(n) time for insertion. As you can see in the code, for insertion, the element is being pushed onto the "rear" stack. That's all for a push(element) operation which takes O(1) time. Now, for front() and pop() operations only, all the elements present in the "rear" stack are moved to the "front" stack in case "front" stack is empty. Note the case when the elements are moved. You did not take this case into consideration which actually makes the time complexity for front() and pop() operations as O(1) . How? You mentioned that we need to transfer n elements from 'Rear' stack to 'Front' stack but you should also note that no element is being moved more than once. Hence, time complexity for both front() and pop() operations is "O(1) + time to move one element from 'rear' stack to 'front' stack if not present in the 'front' stack". Time taken to move includes one pop() operation in the 'rear' stack and one push() operation in the 'front' stack, which is O(1). Please correct me if I am wrong.