The notion of amortization is important in situations where we care only about the total running time of a group of operations and don’t care about the running time of each individual operation. For instance, given a sequence of n operations, we may wish to bound the total running time of the sequence by O(n) without insisting that each individual operation run in O(1) time. We might be satisfied if a few operations run in O(log n) or even O(n) time, provided the total cost of the sequence is only O(n). The following implementation of aQueue exploits the idea of amortization and provides O(1) snoc (insert) and remove operations. This is achieved by using two internal lists, one to represent the front of the queue and the other to represent the tail. The implementation contains no mutable operation, so it can be safely shared by concurrent processes without explicit synchronization:

(define (mk) (cons null null))

(define front car)
(define rear cdr)

(define (apply-invariant q)
  (if (and (null? (front q))
           (not (null? (rear q))))
      ;; reverse eats up the credits accumulated 
      ;; by the elements in the list.
      (cons (reverse (rear q)) null)
      q))

;; Every snoc adds a credit of one to the new element.
(define (snoc q e)
  (apply-invariant (cons (front q) (cons e (rear q)))))

(define (head q)
  (if (not (null? (front q)))
      (caar q)
      null))

(define (tail q)
  (if (not (null? (front q)))
      (apply-invariant (cons (cdr (front q)) (rear q)))
      (apply-invariant (cons null (rear q)))))

(define (remove q)
  (if (not (null? (front q)))
      (apply-invariant (cons (cdr (front q)) (rear q)))))

Sample usage:

> (define q (snoc (snoc (snoc (mk) 1) 2) 3))
> q
=> ((1) 3 2)
> (front q)
=> (1)
> (tail q)
=> ((2 3))
> (snoc q 4)
=> ((1) 4 3 2)
> (remove q)
=> ((2 3))
> (remove (remove q))
=> ((3))

Every function except tail takes O(1) worst-case time, but tail takes O(n) worst-case time. How is this cost amortized over time? This is done by assigning each element of the rear list a credit of 1. Every snoc into a non-empty queue takes one actual step and allocates a credit to the new element of the rear list, for an amortized cost of two. Every tail that does not reverse the rear list takes one actual step and neither allocates nor spends any credits, for an amortized cost of one. Finally, every tail that does reverse the rear list takes m + 1 actual steps, where m is the length of the rear list, and spends the m credits contained by that list, for an amortized cost of m + 1 - m = 1.

Reference: Purely Functional Data Structures by Chris Okasaki