Using 2 stacks- s1 and s2 to implement a queue.
Purpose: keep the input on the bottom of s1
The idea is that when an input comes, we push the input to s1, BUT only if the s1 is empty. If s1 is not empty then we pop out all element from s1 and push into s2,
so that we always keep the input on the bottom of s1.
Time complexity :
Since we need pop out all elements in s1 and push in that elements in s2 before we push the input in the s1 also pop out s2 and push back s1. so it should be O(n).
We only pop out the top of s1. So it is O(1).
Space complexity :
PUSH: O(n). We need n space to store the coming queue elements.
POP: O(1). We only keep one element- the top of s1 which pop out from s1. So it is O(1).
void push(int x):
a while loop , if s1 is not empty,
pop all elements in the s1 and also push the elements to s2
so s2 contains the reverse of s1.
then push x to s1
a while loop, if s2 is not empty,
pop all elements in the s2 and also push the elements to s1
assign x to the integer-front
assign the element from pop s1 to x
assign s1.peek() to the integer-front