blob: 8cf7ea26c907c1705d31ed2c97cf2ccbda7c4b81 (
about) (
plain) (
blame)
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
---
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)
```
|
