cperilla
11/1/2013 - 7:46 PM

Queue implementation for programming praxis. This one wasn't much of my idea as I had recently looked at the erlang's implementation of the

Queue implementation for programming praxis.

This one wasn't much of my idea as I had recently looked at the erlang's implementation of the deque(double ended queue) module and did some analysis of the amortized O(1) complexity of this implementation for deque usage. I think it should be the same for normal queue usage

ex-queues-01-11-2013.scm
content_copyfile_download
;; Author: Carlos Perilla <deepspawn@valkertown.org>
;; Date: 2013-11-01
;; License: CC0
;; http://programmingpraxis.com/2013/11/01/queues/

(define (new-queue) (list '() '()))
(define (isEmpty q) (and (list? q) (null? (car q)) (null? (cadr q))))
(define (enqueue x q) (list (car q)
                            (if (null? (cdr q))
                                (list x)
                                (cons  x (cadr q)))))
(define (dequeue q) (if (null? (car q))
                        (if (null? (cadr q))
                            (cons 'empty q)
                            (let [(nh (reverse (cadr q)))]
                              (list (car nh) (list (cdr nh) '()))
                              ))
                        (list (caar q) (list (cdar q) (cadr q)))))
(dequeue (new-queue))

(dequeue (enqueue 'c
                  (cadr  (dequeue (enqueue 'b
                                           (enqueue 'a
                                                    (new-queue)))))))

(isEmpty (new-queue))
(dequeue
 (cadr (dequeue (enqueue 'd
                         (enqueue 'c
                                  (cadr (dequeue (enqueue 'b
                                                          (enqueue 'a
                                                                   (new-queue))))))))))