(Hackerrank exercise.)

In this implementation of a queue the dequeue operation will have *average-case* time complexity `O(1)`

but worst-case time complexity `O(n)`

.
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:

- maintain two stacks: call them in_stack and out_stack
- enqueue: append the new item to the in_stack (
`O(1)`

worst case) - dequeue: pop an item from the out_stack
*then if the out_stack has now become empty*pop the elements of the in_stack one by one and append them onto the out_stack (`O(n)`

worst-case but`O(1)`

average-case)

and note that the last bullet contains the operation `rev_stack`

as described above.
In total we have:

where we have written `enqueue`

as `put`

and `dequeue`

as `pop`

.