1

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?

Community
  • 1
  • 1
Deqing
  • 14,098
  • 15
  • 84
  • 131

1 Answers1

0

As Dave L. states in his explanation "each element will be pushed twice and popped twice, giving amortized constant time operations". This is because each dequeue that needs to move n elements from one stack to the other (taking O(n) time) will be followed by n-1 dequeues that only take O(1) time.

So one way to express the complexity of dequeue() would be saying that it has amortized constant time with a best cas of O(1) and a worst case of O(n).

Aerlevsedi
  • 36
  • 5