Hackerrank :: Using two stack to implement a queue

Source:
https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks/problem

Solution:

Policy of queue: FIFO. Assume two stack are S1 and S2 separately.
Following is the implement of two method: enqueue() and dequeue()

   def Enqueue(x):

       push(x, S1) // push into S1

   def Dequeue():

       If (S2().empty)

       while(S1().empty):

x = S1.pop()   // pop all element from S1

push(x, S2)    // and push() to S2

       S2.pop()         // pop one element from S2

Prove above pseudo code is O(1):

Analysis by account method:

( one of amortized analysis: https://tmp4by.blogspot.com/2018/04/amortized-analysus.html)

Assume

   Enqueue() charges $4 for:

    $1 for push() into S1

    $1 deposit for pop() from S1

    $1 deposit for push() into S2

    $1 deposit for pop() from S2

   Dequeue() charges $0 since every operation can cost the deposit from Enqueue().
According to our pseudo code, every element in S2 is due to Enqueue() function call with deposit.
If there is no deposit, means there is nothing in S1 and S2 and nothing to dequeue()

The n sequence operation cost 4n = O(n) overall