Dans une file d'attente, à quelle extrémité est la «tête»?

18

J'avais toujours pensé que la "tête" d'une file d'attente était le prochain élément à lire, et je n'ai jamais vraiment remis en question cet usage. Ainsi, une bibliothèque de listes chaînées que j'ai écrite, qui est utilisée pour maintenir les files d'attente, a codifié cette terminologie: nous avons une list1_headmacro qui récupère le premier élément; lors de l'utilisation de cette bibliothèque dans une file d'attente, ce sera le premier élément à supprimer.

Mais un nouveau développeur de l'équipe était habitué à ce que les files d'attente soient implémentées dans l'autre sens. Il a décrit une file d'attente comme se comportant comme un chien: vous insérez à la tête et retirez à la queue. C'est une description assez intelligente pour que je pense que son utilisation doit être plus répandue, et je n'ai pas une description évocatrice similaire de mon utilisation préférée.

Donc, je suppose, il y a deux questions liées: 1, que signifie pour vous la "tête" d'une file d'attente? et 2, pourquoi utilisons-nous le mot «tête» pour décrire ce concept?

terminology Aidan Cully
la source
1
"Il a décrit une file d'attente comme se comportant comme un chien" ... On dirait un gars amusant avec qui travailler - Ne le laissez pas près d'un client.
NoChance
1
Je ne sais pas, mais j'aurais deviné votre mise en œuvre, pas celle du chien.
Izkata
Une autre bonne explication sur la différence entre QUEUE et STACK: http://pages.cs.wisc.edu/~mcw/cs367/lectures/stacks.html
Ythalo Rossy
De plus, dans les manuels, la liste liée (individuellement) est souvent introduite avant d'autres structures de données comme la pile et la file d'attente, puis celles-ci sont construites au-dessus de la structure de la liste liée (ce qui n'est pas nécessairement la façon préférée de construire ces structures de données aujourd'hui car de cache manque). Une liste chaînée aura souvent un pointeur de tête (fait référence au premier élément) et un pointeur de queue (au dernier); dans cet agencement, il est facile d'insérer à l'extrémité arrière, retirer de la tête - donc, dans une telle file d'attente FIFO, vous retirez par l'avant. Mais notez que c'est vraiment un détail d'implémentation interne.
Filip Milovanović
BTW, pensez que c'est en partie lié à la langue, mais il s'agit également de la façon dont nous conceptualisons ce que fait une file d'attente. Pour la plupart des gens qui connaissent le sens du mot "file d'attente", ou qui sont initiés au concept avec cette métaphore (faisant la queue), la partie de sortie est à l'avant / tête; Je soupçonne que votre ami le conçoit davantage comme une sorte de pipeline, où vous poussez des objets à une extrémité (le début, ou dans un certain sens, la "tête") du tuyau, et ils sortent à l'autre extrémité.
Filip Milovanović

Réponses:

29

Vous entrez au fond de la file d'attente et sortez par le devant. Dans la plupart des sociétés, cela impliquerait que la tête est le front, et les éléments sont retirés de la tête.

Le Javadoc pour Queue semble être d'accord avec la définition classique (c'est-à-dire votre définition d'origine):

Quel que soit l'ordre utilisé, la tête de file d'attente est cet élément qui serait supprimé par un appel à remove () ou poll (). Dans une file d'attente FIFO, tous les nouveaux éléments sont insérés à la fin de la file d'attente.

Spencer Kormos
la source
4
La STL C ++ est également d'accord.
Fabio Ceconello
La terminologie courante pour FIFO / LIFO consiste également à supprimer du haut de la file d'attente / pile. Le sommet du chien est la tête, pas la queue. :-D
Spencer Kormos
Il semble que vous ayez répondu à la 1ère question, il est vraiment courant que l'usage que j'avais compris soit traditionnel ... Merci pour les références. Mais ce n'est pas aussi clair pour moi pourquoi le front de la file d'attente est appelé la "tête" ...
Aidan Cully
... alors dans quel orifice du chien devons-nous mettre les objets en file d'attente? ;)
ell
1
La queue d'un chien est la tête de la file d'attente.
Caleb
8

Aux États-Unis, ce que les gens appellent communément une ligne, comme dans le cas où vous vous trouvez au bureau de poste, les gens des autres pays anglophones appellent une file d'attente. Ainsi, il est plus facile pour les Américains de garder la terminologie droite si vous remplacez «ligne» par «file d'attente». En d'autres termes, lorsque vous êtes dans la tête ou devant la ligne, vous êtes le prochain à être appelé.

Karl Bielefeldt
la source
Peut-être s'agit-il plutôt d'une question sur l'anglais, car le problème qui semble se poser est "pourquoi appelons-nous le front la tête?"
Aidan Cully
3
@AidanCully: parce que la tête sur un corps est (dans les quadrupèdes et autres animaux orientés horizontalement) orientée vers l'avant ou vers l'avant.
Outis
C'est la meilleure explication possible pour nous, Américains.
andDevW
4

Les deux conventions sont couramment utilisées. D'après mon expérience, lorsque l'on parle de files d'attente en général, l'élément head est le suivant à sortir de la file d'attente, et la queue est l'endroit où les éléments entrent dans la file d'attente. Cela correspond à l'usage quotidien de l'anglais - nous nous alignons à l'arrière et le prochain à servir est à l'avant ou à la tête. (Et si vous coupez, c'est au fond de la ligne pour vous!)

Cependant, lorsqu'une file d'attente (alias FIFO) est implémentée en tant que tampon en anneau , les termes sont généralement inversés, car la partie utilisée du tampon en anneau ressemble à un serpent circulant en cercle. En supposant que le serpent avance, la tête est naturellement la fin qui mène le mouvement, qui est également la fin à laquelle les éléments entrants sont insérés.

IJ Kennedy
la source
Il convient de mentionner les tampons circulaires dans le noyau Linux , qui utilisent la convention selon laquelle les éléments sont ajoutés en tête et supprimés en queue.
Craig McQueen