Robust software, for everybody.

SICP persistent amortized O(1) queue

Posted on 

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))

plaintext

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)

plaintext