En una cola, ¿qué final es la "cabeza"?

18

Siempre pensé que el "encabezado" de una cola como el siguiente elemento a leer, y nunca cuestioné ese uso. Entonces, una biblioteca de listas enlazadas que escribí, que se usa para mantener colas, codificó esa terminología: tenemos una list1_headmacro que recupera el primer elemento; Al usar esta biblioteca en una cola, este será el primer elemento que se eliminará.

Pero un nuevo desarrollador en el equipo estaba acostumbrado a que las colas se implementaran al revés. Describió una cola como comportarse como un perro: se inserta en la cabeza y se retira en la cola. Esta es una descripción lo suficientemente inteligente que siento que su uso debe estar más extendido, y no tengo una descripción evocativa similar de mi uso preferido.

Entonces, supongo que hay dos preguntas relacionadas: 1, ¿qué significa para usted la "cabeza" de una cola? y 2, ¿por qué usamos la palabra "cabeza" para describir ese concepto?

terminology Aidan Cully
fuente
1
"Describió una fila como comportarse como un perro" ... Suena como un tipo divertido para trabajar. No lo deje cerca de un cliente.
NoChance
1
No lo sé, pero habría adivinado tu implementación, no la del perro.
Izkata
Otra buena explicación sobre la diferencia entre QUEUE y STACK: http://pages.cs.wisc.edu/~mcw/cs367/lectures/stacks.html
Ythalo Rossy
Además, en los libros de texto, la lista enlazada (individualmente) a menudo se introduce antes que otras estructuras de datos como stack y queue, y luego se construyen sobre la estructura de la lista enlazada (que no es necesariamente la forma preferida de construir estas estructuras de datos hoy en día porque de caché pierde). Una lista vinculada a menudo tendrá un puntero de cabecera (se refiere al primer elemento) y un puntero de cola (al último); En esta disposición, es fácil insertar en el extremo posterior retirar de la cabeza, por lo que, en una cola FIFO de este tipo, eliminar desde el frente. Pero tenga en cuenta que esto es realmente un detalle de implementación interna.
Filip Milovanović
Por cierto, creo que es parcialmente una cuestión relacionada con el lenguaje, pero también se trata de cómo conceptualizamos lo que hace una cola. Para la mayoría de las personas que conocen el significado de la palabra "cola", o se les presenta el concepto con esa metáfora (esperando en la fila), la parte de salida está en la parte delantera / cabeza; Sospecho que su amigo lo conceptualiza más como un tipo de tubería, donde empuja objetos en un extremo (el comienzo, o en cierto sentido, la "cabeza") de la tubería, y salen por el otro extremo.
Filip Milovanović

Respuestas:

29

Entras al final de la cola y sales desde el frente. En la mayoría de las sociedades, eso implicaría que la cabeza es el frente, y los artículos se eliminan de la cabeza.

El Javadoc para cola parece estar de acuerdo con la definición clásica (es decir, la original):

Cualquiera que sea el orden utilizado, el encabezado de la cola es ese elemento que sería eliminado por una llamada a remove () o poll (). En una cola FIFO, todos los elementos nuevos se insertan en la cola de la cola.

Spencer Kormos
fuente
44
El C ++ STL también está de acuerdo.
Fabio Ceconello
También la terminología común para FIFO / LIFO es eliminar de la parte superior de la Cola / Pila. La parte superior del perro es la cabeza, no la cola. :-D
Spencer Kormos
Parece que has respondido la primera pregunta, realmente es el caso que el uso que he entendido es tradicional ... Gracias por las referencias. Pero no es tan irónico para mí por qué el frente de la fila se llama "cabeza" ...
Aidan Cully
... entonces, ¿en qué orificio del perro colocamos artículos? ;)
ell
1
La cola de un perro es la cabeza de la cola.
Caleb
8

Lo que la gente en los Estados Unidos comúnmente llama una línea, como en lo que se para en la oficina de correos, la gente en otros países de habla inglesa llama una cola. Por lo tanto, es más fácil para los estadounidenses mantener la terminología correcta si sustituyes "línea" por "cola". En otras palabras, cuando estás en la cabeza o frente de la línea, eres el próximo en ser llamado.

Karl Bielefeldt
fuente
Quizás esta sea más una pregunta sobre el inglés, entonces, porque el problema que parece haber surgido es "¿por qué llamamos al frente la cabeza?"
Aidan Cully
3
@AidanCully: porque la cabeza de un cuerpo está (en cuadrúpedos y otros animales orientados horizontalmente) hacia adelante o hacia adelante.
outis
Esa es la mejor explicación posible para nosotros los estadounidenses.
andDevW
4

Ambas convenciones son de uso común. En mi experiencia, cuando se habla de colas en general, el elemento principal es el siguiente en salir de la cola, y la cola es donde los elementos entran en la cola. Esto es coherente con el uso diario del inglés: nos ponemos en fila en la parte de atrás, y el siguiente en ser atendido es en la parte delantera o en la cabeza. (Y si cortas, ¡está al final de la línea para ti!)

Sin embargo, cuando una cola (también conocida como FIFO) se implementa como un búfer en anillo , los términos generalmente se invierten, porque la parte utilizada del búfer en anillo se asemeja a una serpiente dando vueltas en un círculo. Suponiendo que la serpiente se está moviendo hacia adelante, la cabeza es naturalmente el final que lidera el movimiento, que también es el final en el que se insertan los elementos entrantes.

IJ Kennedy
fuente
Vale la pena mencionar los buffers circulares en el kernel de Linux , que usan la convención de que los elementos se agregan en la parte superior y se eliminan en la cola.
Craig McQueen