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)