SICP persistent amortized O(1) queue

Posted on September 3, 2021
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)