; circular arrays

(define (make-queue n)
  (let ((q (make-vector n #f))
        (start 0) (end 0) (size 0))
    (lambda (command . args)
      (case command
      ((empty?) (zero? size))
      ((enqueue)
        (if (= n size)
            (error 'enqueue "Full")
            (begin
              (set! size (+ size 1))
              (vector-set! q end (car args))
              (set! end (modulo (+ end 1) n)))))
      ((dequeue)
        (if (zero? size)
            (error 'enqueue "Empty")
            (let ((x (vector-ref q start)))
              (set! size (- size 1))
              (vector-set! q start #f)
              (set! start (modulo (+ start 1) n))
              x)))))))

(define q (make-queue 3))
(q 'enqueue 1)
(q 'enqueue 2)
(q 'enqueue 3)
(display (q 'dequeue)) (newline)
(display (q 'dequeue)) (newline)
(display (q 'dequeue)) (newline)
(display (q 'empty?)) (newline)

(define (make-queue)
  (let ((q (cons (list) (list)))) ; front/back
    (lambda (command . args)
      (case command
      ((empty?)
        (and (null? (car q)) (null? (cdr q))))
      ((enqueue)
        (set-cdr! q (cons (car args) (cdr q))))
      ((dequeue)
        (cond ((pair? (car q))
                (let ((x (caar q)))
                  (set-car! q (cdar q))
                  x))
        (else (set-car! q (reverse (cdr q)))
              (set-cdr! q (list))
              (if (null? (car q))
                  (error 'dequeue "Empty")
                  (let ((x (caar q)))
                    (set-car! q (cdar q))
                    x)))))))))

(set! q (make-queue))
(display (q 'empty?)) (newline)
(q 'enqueue 1)
(q 'enqueue 2)
(display (q 'empty?)) (newline)
(display (q 'dequeue)) (newline)
(q 'enqueue 3)
(q 'enqueue 4)
(display (q 'dequeue)) (newline)
(display (q 'dequeue)) (newline)
(display (q 'dequeue)) (newline)