algorithm - 3 つのスタックを使用して Deque を実装する (償却時間 O(1))

Question

howmework に次の質問があります。

3 つのスタックを使用して Deque を実装します。Deque には、InsertHead、InsertTail、DeleteHead、DeleteTail という操作があります。各操作の償却時間が O(1) であることを証明します。

私が試みたのは、問題をハノイ問題として見ることです。スタックを次のように呼び出しましょう: L(左)、M (中央)、R(右)。

擬似コードの実装:

InsertHead(e):
     L.push(e);

DeleteHead(e):
     L is empty:

       while R is not empty:
          pop and insert the element to M;
       pop M;
       while M is not empty:
         pop and insert the element to R;

     L is not empty:    
       L.pop(e);

InsertTail と DeleteTail は、上記の実装と同じ原則に基づいています。償却された時間が O(1) であることをどのように証明できますか? L には N 個の要素が存在する可能性があり、wile ループは O(n) かかるため、deleteHead を N 回呼び出して償却時間を計算すると、複雑さは O(n^2) になりませんか?

上記の実装が償却時間でO(1)かかることを証明するにはどうすればよいですか?