When I came across this question - using two stacks to implement a queue, I'm wondering how to analyze complexity of it.
Take this as example:
- For queue(), the complexity is always O(1), as it simply push into the inbox.
- For dequeue(), most of the time the complexity is also O(1), but when outbox is empty, it needs a loop to move all elements from inbox to outbox. So what is the complexity of this operation?
What is the idea when analyzing such kind of problem?