Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
"He described a queue as behaving like a dog"...Sounds like a fun guy to work with - Don't let him near a customer. –  Emmad Kareem Apr 15 '12 at 6:11
    
I don't know, but I would've guessed at your implementation, not the dog one. –  Izkata Apr 16 '12 at 2:06
add comment

3 Answers

up vote 17 down vote accepted

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.

share|improve this answer
4  
The C++ STL also agrees. –  Fabio Ceconello Apr 14 '12 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 Apr 14 '12 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 Apr 14 '12 at 23:41
    
...so in which orifice of the dog do we enqueue items? ;) –  ell Apr 14 '12 at 23:58
1  
The tail of a dog is the head of the queue. –  Caleb Apr 15 '12 at 5:30
show 1 more comment

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.

share|improve this answer
    
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 Apr 14 '12 at 23:42
1  
@AidanCully: because the head on a body is (in quadrupeds and other animals oriented horizontally) forward-facing, or the front. –  outis Apr 15 '12 at 2:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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