In this implementation of a queue the dequeue operation will have average-case time complexity
O(1) but worst-case time complexity
So there are better ways to implement a queue.
The idea is to use one list as an inbox and the other as an outbox.
The key tactic to implement this idea is that reversing a stack amounts to popping each element and appending it to a new stack:
which in the abstract arises from the fact that a stack has the first-in-last-out property. So the algorithm as a whole is:
and note that the last bullet contains the operation
rev_stack as described above.
In total we have:
where we have written