From 020c1e77489b772f854bb3288b9c8d2818a6bf9d Mon Sep 17 00:00:00 2001
From: EuAndreh <eu@euandre.org>
Date: Fri, 18 Apr 2025 02:17:12 -0300
Subject: git mv src/content/* src/content/en/

---
 .../2021/09/03/sicp-persistent-queue.adoc          | 76 ++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 src/content/en/pastebins/2021/09/03/sicp-persistent-queue.adoc

(limited to 'src/content/en/pastebins/2021/09/03')

diff --git a/src/content/en/pastebins/2021/09/03/sicp-persistent-queue.adoc b/src/content/en/pastebins/2021/09/03/sicp-persistent-queue.adoc
new file mode 100644
index 0000000..2b4a8a2
--- /dev/null
+++ b/src/content/en/pastebins/2021/09/03/sicp-persistent-queue.adoc
@@ -0,0 +1,76 @@
+= SICP persistent amortized O(1) queue
+
+[source,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:
+
+[source,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)
+----
-- 
cgit v1.2.3