Queues
November 1, 2013
There are several ways to implement a queue. Imperative programmers would doubtless initialize an array that is large enough to hold the largest expected number of items in the queue, then keep two pointers, one to the head of the queue and the other to the tail. Adding an item at the end of the queue is done by incrementing the tail, then storing the item at the new tail, removing an item from the head of the queue is done by incrementing the head, then returning the item at the old head, and the queue is empty whenever the head and tail point to the same index in the array; all index arithmetic is done modulo the size of the array, so it wraps around as needed.
But we’re not going to do that. Functional programmers use a trick from the computing folklore: keep two lists, one for the front of the queue and one in reverse order for the back. New items are added to the back list, which is reversed and becomes the front list whenever an attempt is made to dequeue an item from an empty front list. The queue is empty whenever both the front and back lists are empty, and there is no predefined maximum size. Here’s our implementation:
(define (make-queue) (list (list)))
(define (enqueue q x) (cons (car q) (cons x (cdr q))))
(define (head q)
(if (pair? (car q))
(caar q)
(if (pair? (cdr q))
(car (reverse (cdr q)))
(error 'head "empty"))))
(define (tail q)
(if (pair? (car q))
(cons (cdar q) (cdr q))
(if (pair? (cdr q))
(cons (cdr (reverse (cdr q))) (list))
(error 'tail "empty"))))
(define (empty? q) (and (null? (car q)) (null? (cdr q))))
We split the dequeue operation into two pieces, head and tail, because otherwise we would have to modify the queue as a side effect, which is generally not preferred. Here are some examples:
> (define q (make-queue))
> (set! q (enqueue q 1))
> (set! q (enqueue q 2))
> (empty? q)
#f
> (head q)
1
> (set! q (tail q))
> (head q)
2
> (set! q (enqueue q 3))
> (set! q (tail q))
> (head q)
3
> (set! q (tail q))
> (empty? q)
#t
You can run the program at http://programmingpraxis.codepad.org/22B4rkGy.
Programming Praxis 
Implemented in Go.
Implementation in SML.
signature QUEUE = sig type 'a queue exception EmptyQ val empty: 'a queue val enqueue: 'a queue -> 'a -> 'a queue val dequeue: 'a queue -> 'a * 'a queue val isEmpty: 'a queue -> bool end structure ListQueue :> QUEUE = struct type 'a queue = 'a list * 'a list exception EmptyQ val empty = ([], []) fun enqueue (xs, ys) x = (x::xs, ys) fun dequeue ([], []) = raise EmptyQ | dequeue (xs, []) = dequeue ([], rev f) | dequeue (xs, y::ys) = (y, (xs, ys)) fun isEmpty ([], []) = true | isEmpty _ = false endvar Queue = function (items) { this.elements = items || []; }; Queue.prototype.enqueue = function (item) { this.elements.push(item); return this; }; Queue.prototype.dequeue = function () { return this.elements.shift(); }; Queue.prototype.isEmpty = function () { return this.elements.length === 0; }; window.tasksQueue = new Queue(["Wake Up", "Shower"]); tasksQueue.enqueue("Dress") .enqueue("Have Breakfast") .enqueue("Go to work"); while(!tasksQueue.isEmpty()) { console.log(tasksQueue.dequeue()); }Okasaki “banker’s queues” in Haskell:
import Prelude hiding (head,tail) import qualified Prelude as P data Queue a = Q [a] {-# UNPACK #-} !Int [a] {-#UNPACK#-} !Int -- toList is faster than just removing items one at a time because it avoids all the queue rotations. toList :: Queue a -> [a] toList (Q fs _ rs _) = fs ++ reverse rs -- fromList is faster than just snocing items on one at a time because it -- avoids all the queue rotations. It also produces a queue in the optimal state, with everything in the front list. fromList :: [a] -> Queue a fromList l = Q l (length l) [] 0 size (Q _ flen _ rlen) = flen+rlen emptyq = Q [] 0 [] 0 head :: Queue a -> a head (Q [] _ _ _) = error "Cannot get the head of an empty queue." head (Q (h:_) _ _ _) = h tail :: Queue a -> Queue a tail (Q [] _ _ _) = error "Cannot get the tail of an empty queue." tail (Q (f:fs) flen rs rlen) = queue fs (flen-1) rs rlen snoc :: Queue a -> a -> Queue a snoc (Q fs flen rs rlen) x = queue fs flen (x:rs) (rlen+1) queue :: [a] -> Int -> [a] -> Int -> Queue a queue f flen r rlen | flen >= rlen = Q f flen r rlen | otherwise = Q (f++reverse r) (flen+rlen) [] 0I forgot to mention above that if the size operation is not needed, it’s possible to save a bit of space by storing only the difference between the front and rear lengths, rather than the lengths themselves.