Implement a queue data structure using a stack in amortized O(1) time.
Note: A queue is a data structure that follows the FIFO (First-In, First-Out) approach.
Solutions
Method 1: In amortized O(1) time
We can implement a queue with amortized O(1) time complexity using two stacks.
The idea is to maintain two stacks, "input" and "output". In the add() method, just add the new element to the "input" stack in O(1) time.
While if poll() and peek() methods, transfer all elements from the "input" stack to the "output" stack and return the "top" of the "output" stack.
The size of the queue will be the size of both the "input" and "output" stacks.
Complexity
The time complexity of this solution is O(N) and space complexity is O(N).
The time complexity of add() for this solution is O(1) while for poll() and peek() is amortized O(1) ~ O(n) or O(1).