FIFO queues are a standard data structure that have many uses but they can be surprisingly difficult to get right. The standard implementation is an array with two pointers called front and rear.
It’s the details of maintaining the pointers that cause trouble. An object is added to the queue by advancing the rear pointer—in a circular fashion—and placing the new object where it points. An object is taken off the queue by removing the object pointed to by the front pointer and then advancing the pointer, again in a circular fashion. You also have to worry about what it means when both pointers point to the same place.
In Scheme and Lisp, FIFOs are often implemented with lists by manipulating the cdr of the last element to push a new object onto the queue. This is fast and direct but you still have to maintain the rear pointer. There’s a nice method of implementing FIFO queues that I learned from Programming Praxis. The idea is that the queue is made up of two lists, front and back. You add objects to the queue by consing them onto the front of the back list, and you remove objects from the queue by popping them off the front of the front list. If the front lists goes empty, you set it to the reverse of the back list and set the back list to the empty list.
Here’s an implementation of that idea in Scheme. A Lisp implementation is very similar.
1: ;;; 2: ;;; Queue obect 3: ;;; 4: 5: ;; 'push x: push x onto the rear of the queue 6: ;; 'pop: remove the head of the queue and return it 7: ;; 'peek: return the head of the queue 8: ;; 'show: show the queue's contents 9: ;; 'fb: show the front and back parts of the queue (for debugging) 10: (define make-queue 11: (lambda () 12: (let ((front '()) (back '())) 13: (lambda (cmd . data) 14: (define exchange 15: (lambda () 16: (set! front (reverse back)) 17: (set! back '()))) 18: (case cmd 19: ((push) (push (car data) back)) 20: ((pop) (or (pop front) 21: (begin 22: (exchange) 23: (pop front)))) 24: ((peek) (unless (pair? front) 25: (exchange)) 26: (car front)) 27: ((show) (format #t "~s\n" (append front (reverse back)))) 28: ((fb) (format #t "front: ~s, back: ~s\n" front back)) 29: (else (error "Illegal cmd to queue object" cmd)))))))
Calling make-queue returns a closure that implements the queue. You can push and pop objects onto and off of the queue by sending it the push or pop command.
(define q (make-queue)) (q 'push "Hello, World!") (q 'pop) → "Hello, World!"
As you can see on line 19, the push command merely pushes the object onto the front of the back list. The pop command on lines 20–23 just gets the first object on the front list. If the front list is empty, exchange (line 14) is called to set the front list to the reverse of the back list.
There are a few other commands mostly for debugging purposes. This is a tremendously helpful trick that I use all the time—the make-queue function is part of my standard library.
Finally, just for completeness, here are the unless, push, and pop macros that the above code uses. These are pretty standard and may even come with your Scheme implementation.
(define-macro (unless pred . body) `(if (not ,pred) (begin ,@body))) ;; Push an object onto a list (defmacro push (obj lst) `(set! ,lst (cons ,obj ,lst))) ;; Pop an object off a list and return the object (defmacro pop (lst) (let ((t (gensym))) `(if (null? ,lst) #f (let ((,t (car ,lst))) (set! ,lst (cdr ,lst)) ,t))))