FIFO Queues in Scheme and Lisp

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.

http://irreal.org/blog/wp-content/uploads/2011/05/wpid-queue.png

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))))
This entry was posted in Programming and tagged . Bookmark the permalink.

3 Responses to FIFO Queues in Scheme and Lisp

  1. Shemika says:

    It is some thing I need to find more information about, appreciation for the blog post.

  2. Juan says:

    This is slower than the circular buffer or keeping a pointer to the end of the queue due to the reverse operation, though, right? (linear time)

    • jcs jcs says:

      I haven't done any timings but it surely is because of the reverse operation. I've written queues by maintaining front and back pointers and although it's not all that hard it can be tricky to get the details right. For a really time critical application I might use the tail pointer method but in general the algorithm in this post is so fast and easy that I just use it. The circular buffer method is trickier than either of the other two methods and suffers from a fixed size so in some ways it's the worst of both worlds. OTOH, if you're implementing in C (say) it's probably what you'd use because you don't have all the built-in data structures and functions that Lisp provides. And, of course, the circular buffer method is probably the fastest because there's no memory allocation/deallocation to worry about.

Comments are closed.