What will be the time complexity of insertion if a queue is implemented using two stacks?

Question

A Queue could be implemented using two Stacks.

So what will be the time complexity for insertion and deletion in this queue?

Thanks in advance.

Answer 1

The time complexity for insertion is $O(1)$ while deletion is $O(n)$ (in the worst case) for a single operation. The amortized costs for both are $O(1)$ since having to delete $n$ elements from the queue still takes $O(n)$ time.

The above is assuming your implementation is one stack called In for inserting new elements to and one stack called Out from which we will retrieve elements for deletion. Since we only ever add new elements to In, we only need a single push() for insertion. This gives the above time cost. For deletions, if Out is empty, pop() everything from In and push() it to Out. Then pop() the top element to return. This is $O(n)$. If Out is not empty, just pop() its top element. This gives worst case $O(n)$ but amortized $O(1)$.