Douglas Crockford

About

Books

Videos

2019 Appearances

Blog

JSLint

JSON

Github

How JavaScript Works

The Queue Metaphor: List or Beast

The queue is one of the fundamental data structures. It is a FIFO (first in, first out), where items are appended to one end and extracted from the other. The two ends are commonly labelled head and tail, but which end is which? It depends on your metaphor.

If your queue is a list, then you will append at the tail and extract from the head. But if your queue is a beast, then you feed the head and excrete from the tail.

So which be it, list or beast?

This seems to be one of those questions for which there is not a sufficiently right answer, so opinions are sharply divided. My thought was to appeal to a higher authority, who in this case would have to be Donald Knuth. But Volume One of The Art of Computer Programming does not use head and tail in describing queues.

Knuth has published a program called Simpath that does implement a queue using head and tail, but the commentary does not describe the metaphor. An examination of the code shows that he uses the beast metaphor, and he just assumes that the reader knows that. That is an interesting data point, but it is not the definitive authority I was looking for.

So this is where it settles out for me: I want to disambiguate, making it obvious which end is which. The terms head and tail are provably ambiguous and confusing, so they should not be used regardless of the metaphor.

If your metaphor is list, then use front and back. You read from the front and you write to the back.

If your metaphor is beast, then use mouth and anus. It just makes sense.