23

I had always thought that the "head" of a queue as the next element to be read, and never really questioned that usage. So a linked-list library I wrote, which is used for maintaining queues, codified that terminology: we have a list1_head macro that retrieves the first element; when using this library in a queue, this will be the first element to be removed.

But a new developer on the team was used to having queues implemented the other way around. He described a queue as behaving like a dog: you insert at the head, and remove at the tail. This is a clever enough description that I feel like his usage must be more widespread, and I don't have a similarly evocative description of my preferred usage.

So, I guess, there are two related questions: 1, what does the "head" of a queue mean to you? and 2, why do we use the word "head" to describe that concept?

5
  • 1
    "He described a queue as behaving like a dog"...Sounds like a fun guy to work with - Don't let him near a customer.
    – NoChance
    Commented Apr 15, 2012 at 6:11
  • 1
    I don't know, but I would've guessed at your implementation, not the dog one.
    – Izkata
    Commented Apr 16, 2012 at 2:06
  • Another good explanation about the difference between QUEUE and STACK: http://pages.cs.wisc.edu/~mcw/cs367/lectures/stacks.html
    – Ythalo Rossy
    Commented Nov 15, 2018 at 22:49
  • Also, in textbooks, the (singly) linked list is often introduced before other data structures like stack and queue, and then these are built on top of the linked list structure (which is not necessarily the preferred way to build these data structures today because of cache misses). A linked list will often have a head pointer (refers to the first element), and a tail pointer (to the last); in this arrangement, it is easy to insert at the tail end remove from the head - so, in a such a FIFO queue, you remove from the front. But note that this is really an internal implementation detail.
    – Filip Milovanović
    Commented Nov 15, 2018 at 23:45
  • BTW, do think it's partially a language-related thing, but it's also about how we conceptualize what a queue does. To most people who know the meaning of the word "queue", or are introduced to the concept with that metaphor (waiting in line), the exit part is at the front/head; I suspect your friend conceptualizes it more like a pipeline kind of thing, where you push objects at one end (the start, or in some sense, the "head") of the pipe, and they exit at the other end.
    – Filip Milovanović
    Commented Nov 15, 2018 at 23:59

3 Answers 3

Reset to default
34

You enter at the back of the queue, and leave from the front. In most societies, that would imply the head is the front, and items are removed from the head.

The Javadoc for Queue seems to agree with the classic definition (i.e. your original one):

Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue.

6
  • 4
    The C++ STL also agrees.
    – Fabio Ceconello
    Commented Apr 14, 2012 at 21:22
  • Also common terminology for FIFO / LIFO is to remove from the top of the Queue / Stack. The top of the dog is the head, not the tail. :-D
    – Spencer Kormos
    Commented Apr 14, 2012 at 21:24
  • It seems that you've answered the 1st question, it really is commonly the case that the usage I'd understood is traditional... Thank you for the references. But it's not as iron-clad to me why the front of the queue is called the "head"...
    – Aidan Cully
    Commented Apr 14, 2012 at 23:41
  • ...so in which orifice of the dog do we enqueue items? ;)
    – ell
    Commented Apr 14, 2012 at 23:58
  • 2
    The tail of a dog is the head of the queue.
    – Caleb
    Commented Apr 15, 2012 at 5:30
9

What people in the United States commonly call a line, as in the thing you stand in at the post office, people in other English speaking countries call a queue. So, it's easier for Americans to keep the terminology straight if you substitute "line" for "queue." In other words, when you are in the head, or front, of the line, you are the next to be called.

3
  • Maybe this is more a question about English, then, because the issue that seems to have come up is "why do we call the front the head?"
    – Aidan Cully
    Commented Apr 14, 2012 at 23:42
  • 3
    @AidanCully: because the head on a body is (in quadrupeds and other animals oriented horizontally) forward-facing, or the front.
    – outis
    Commented Apr 15, 2012 at 2:11
  • That's the best possible explanation for us Americans.
    – andDevW
    Commented May 15, 2018 at 21:33
5

Both conventions are in common use. In my experience, when talking about queues in general, the head element is the next one to come out of the queue, and the tail is where elements enter the queue. This is consistent with everyday English usage—we get in line at the back, and the next to be served is at the front, or head. (And if you cut, it's to the back of the line for you!)

However, when a queue (aka FIFO) is implemented as a ring buffer, the terms are typically reversed, because the used portion of the ring buffer resembles a snake going around in a circle. Assuming the snake is moving forward, the head is naturally the end that leading the movement, which is also the end at which incoming items are inserted.

1

Not the answer you're looking for? Browse other questions tagged or ask your own question.