В очереди, какой конец является «головой»?

18

Я всегда думал, что «заголовок» очереди - следующий элемент для чтения, и никогда не ставил под сомнение такое использование. Итак, библиотека связанного списка, которую я написал, которая используется для обслуживания очередей, кодифицировала эту терминологию: у нас есть list1_headмакрос, который извлекает первый элемент; при использовании этой библиотеки в очереди это будет первый элемент, который будет удален.

Но новый разработчик в команде привык к внедрению очередей наоборот. Он описал очередь как ведение себя как собаку: вы вставляете в голову, а удаляете в хвост. Это достаточно умное описание, и мне кажется, что его использование должно быть более распространенным, и у меня нет такого же вызывающего воспоминания описания моего предпочтительного использования.

Итак, я думаю, есть два связанных вопроса: 1, что означает для вас «голова» очереди? и 2, почему мы используем слово «голова» для описания этой концепции?

Эйдан Калли
источник
1
«Он описал очередь как поведение, как собака» ... Звучит как забавный парень, с которым нужно работать - не позволяйте ему находиться рядом с клиентом.
NoChance
1
Я не знаю, но я бы догадался о вашей реализации, а не о собаках.
Изката
Еще одно хорошее объяснение разницы между QUEUE и STACK: http://pages.cs.wisc.edu/~mcw/cs367/lectures/stacks.html
Итало Росси
Кроме того, в учебниках (по отдельности) связанный список часто вводится перед другими структурами данных, такими как стек и очередь, а затем они строятся поверх структуры связанного списка (что не обязательно является предпочтительным способом построения этих структур данных сегодня, потому что кеша отсутствует). Связанный список часто будет иметь указатель головы (относится к первому элементу) и хвостовой указатель (к последнему); при таком расположении его легко вставлять в хвостовую часть, снимать с головы - поэтому в такой очереди FIFO вы удаляете спереди. Но обратите внимание, что это действительно внутренняя деталь реализации.
Филипп Милованович
Кстати, думаю, что это частично связано с языком, но также и о том, как мы концептуализируем то, что делает очередь. Для большинства людей, которые знают значение слова «очередь» или знакомятся с концепцией с помощью этой метафоры (ожидание в очереди), выходная часть находится впереди / впереди; Я подозреваю, что ваш друг концептуализирует это больше как нечто вроде конвейера, когда вы толкаете объекты на одном конце (начало или, в некотором смысле, «голова») трубы, и они выходят на другом конце.
Филипп Милованович

Ответы:

29

Вы входите в конец очереди и выходите с фронта. В большинстве обществ это подразумевает, что голова - это передняя часть, а предметы снимаются с головы.

Javadoc для очереди , похоже, согласен с классическим определением (т.е. вашего оригинала):

Какой бы порядок не использовался, заголовок очереди - это тот элемент, который будет удален вызовом remove () или poll (). В очереди FIFO все новые элементы вставляются в конец очереди.

Спенсер Кормос
источник
4
C ++ STL также согласен.
Фабио Секонелло
Также общей терминологией для FIFO / LIFO является удаление из верхней части очереди / стека. Верх собаки - голова, а не хвост. :-D
Спенсер Кормос
Похоже, что вы ответили на 1-й вопрос, это действительно тот случай, когда использование, которое я понял, является традиционным ... Спасибо за ссылки. Но это не так железно для меня, почему переднюю часть очереди называют «головой» ...
Эйдан Калли
... так в каком отверстии собаки мы ставим предметы? ;)
ell
1
Хвост собаки - голова очереди.
Калеб
8

То, что люди в Соединенных Штатах обычно называют линией, как, например, в почтовом отделении, люди в других англоязычных странах называют очередью. Таким образом, американцам будет проще придерживаться терминологии, если вы замените «очередь» на «очередь». Другими словами, когда вы находитесь в голове или впереди линии, вы следующий, кто будет вызван.

Карл Билефельдт
источник
Может быть, это больше вопрос об английском языке, потому что проблема, которая, кажется, возникла: «Почему мы называем фронт головой?»
Эйдан Калли
3
@AidanCully: потому что голова на теле (у четвероногих и других животных, ориентированных горизонтально) обращена вперед или вперед.
2012 г.
Это лучшее возможное объяснение для нас, американцев.
andDevW
4

Оба соглашения находятся в общем пользовании. По моему опыту, когда речь идет об очередях в целом, следующим является элемент head, который выходит из очереди, а хвост - это то, где элементы входят в очередь. Это согласуется с повседневным употреблением английского - мы выстраиваемся в очередь сзади, а следующий, который нужно подавать, находится спереди или в голове. (И если вы порежете, это для задней части линии для вас!)

Однако, когда очередь (также известная как FIFO) реализована в виде кольцевого буфера , термины обычно меняются местами, потому что используемая часть кольцевого буфера напоминает змею, идущую по кругу. Предполагая, что змея движется вперед, голова, естественно, является концом, ведущим движение, а также концом, в который вставляются входящие предметы.

IJ Кеннеди
источник
Стоит упомянуть кольцевые буферы в ядре Linux , которые используют соглашение, согласно которому элементы добавляются в начало, а удаляются в хвост.
Крейг МакКуин