---

title: SICP persistent amortized O(1) queue

date: 2021-09-03

layout: post

lang: en

ref: sicp-persistent-amortized-o1-queue

---

```scheme
(define (queue)
  (cons '()
	'()))

(define (enqueue x q)
  (cons (car q)
	(cons x (cdr q))))

(define (flush q)
  (cons (reverse (cdr q))
	'()))

(define (dequeue q)
  (if (null? (car q))
    (dequeue (flush q))
    (cons (caar q)
	  (cons (cdar q)
		(cdr q)))))

(define (empty? q)
  (and (null? (car q))
       (null? (cdr q))))

(define (peek q)
  (car (dequeue q)))

(define (print-queue q)
  (define (rec l leading-space?)
    (when (not (null? l))
      (when leading-space?
	(display " "))
      (display (car l))
      (rec (cdr l) #t)))

  (display "#q(")
  (rec (car q) false)
  (rec (reverse (cdr q)) (not (null? (car q))))
  (display ")")
  (newline))
```

Sample interactive session:
```scheme
scheme@(guile-user)> (define true #t)
scheme@(guile-user)> (define false #f)
scheme@(guile-user)> (define q (queue))
scheme@(guile-user)> (print-queue q)
#q()
scheme@(guile-user)> (print-queue (enqueue 'a q))
#q(a)
scheme@(guile-user)> (print-queue q)
#q()
scheme@(guile-user)> (set! q (enqueue 'a q))
scheme@(guile-user)> (print-queue q)
#q(a)
scheme@(guile-user)> (set! q (enqueue 'e (enqueue 'd (enqueue 'c (enqueue 'b q)))))
scheme@(guile-user)> (print-queue q)
#q(e d c b a)
scheme@(guile-user)> (peek q)
$28 = a
scheme@(guile-user)> (define ret (dequeue q))
scheme@(guile-user)> (define value (car ret))
scheme@(guile-user)> (set! q (cdr ret))
scheme@(guile-user)> value
$29 = a
scheme@(guile-user)> (print-queue q)
#q(b c d e)
scheme@(guile-user)> (print-queue (cdr (dequeue (cdr (dequeue (enqueue 'g (enqueue 'f q)))))))
#q(d e f g)
```