ListQueues - Cookbook - s c h e m a t i c s : c o o k b o o k

Creating Queues

Problem

You want to build a Queue data structure, e.g. a First-In-First-Out list structure.

Solution

SICP has a section on creating a queue using a cons cell to hold the head and tail pointers:

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
(define (empty-queue? queue) (null? (front-ptr queue)))

(define (make-queue) (cons '() '()))

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an empty queue" queue)
      (car (front-ptr queue))))

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else
           (set-cdr! (rear-ptr queue) new-pair)
           (set-rear-ptr! queue new-pair)
           queue)))) 

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        (else
         (set-front-ptr! queue (cdr (front-ptr queue)))
         queue)))

This implementation is interesting because of the tricky way it uses a cons to hold the head and tail pointers. A result of this implementation is that the printed representation of the queue is a bit deceptive:

> (define q (make-queue ))
> q
(())
> (insert-queue! q 1)
((1) 1)
> (insert-queue! q 2)

((1 2) 2)

It looks like there's an extra element on the queue, but that's really just a result of how the printer wants to interpret a cons.

The front-ptr and rear-ptr functions are really implementation details, so if you wanted to use this is real code, you might want to wrap it in a module declaration and not provide them.

Queues are often used for communicating between processes and threads, and for buffering I/O in high-volume applications like web servers that tend to see spikes in input. However, queues used for interprocess/interthread communications also generally require additional synchronization mechanisms.

Comments about this recipe

See also FunctionalQueue for another version.

Contributors

-- GordonWeakliem - 14 Aug 2004

CookbookForm
TopicType:	Recipe
ParentTopic:	DataStructureRecipes
TopicOrder:	999

PLT Scheme	SISC
Scheme48	SCM
MIT Scheme	scsh
JScheme	Kawa
Chicken	Guile
Bigloo	Tiny
Gambit	LispMe
Gauche	Chez

s c h e m a t i c s : c o o k b o o k

Creating Queues

Problem

Solution

Discussion

Comments about this recipe

Contributors