W kolejce, który koniec to „głowa”?

Zawsze myślałem, że „głowa” kolejki jako następny element do przeczytania, i nigdy tak naprawdę nie kwestionowałem tego użycia. Tak więc napisana przeze mnie biblioteka list połączonych, która służy do utrzymywania kolejek, skodyfikowała tę terminologię: mamy list1_headmakro, które pobiera pierwszy element; podczas korzystania z tej biblioteki w kolejce będzie to pierwszy element do usunięcia.

Ale nowy programista w zespole przyzwyczaił się do kolejkowania zaimplementowanego na odwrót. Opisał, że kolejka zachowuje się jak pies: wkładasz głowę i zdejmujesz ogon. To dość sprytny opis, który wydaje mi się, że jego użycie musi być bardziej rozpowszechnione i nie mam podobnie sugestywnego opisu mojego preferowanego użycia.

Sądzę, że są dwa powiązane pytania: 1, co oznacza dla ciebie „głowa” kolejki? i 2, dlaczego używamy słowa „głowa” do opisania tego pojęcia?

terminology

— Aidan Cully
źródło

„Opisał, że kolejka zachowuje się jak pies” ... Brzmi jak fajny facet do pracy - Nie pozwól mu zbliżyć się do klienta.

— NoChance 15.04. Kwietnia

Nie wiem, ale zgadłbym z twojej realizacji, nie z tej psiej.

— Izkata

Kolejne dobre wyjaśnienie różnicy między

— KOLEJKĄ a STOSKIEM

Również w podręcznikach (pojedynczo) połączona lista jest często wprowadzana przed innymi strukturami danych, takimi jak stos i kolejka, a następnie są one budowane na strukturze połączonej listy (co niekoniecznie jest obecnie preferowanym sposobem budowania tych struktur danych, ponieważ braków w pamięci podręcznej). Połączona lista często ma wskaźnik głowy (odnosi się do pierwszego elementu) i wskaźnik ogona (do ostatniego); w tym układzie łatwo jest wstawić na końcu ogona zdjąć z głowy - więc w takiej kolejce FIFO wyjmujesz z przodu. Pamiętaj jednak, że jest to naprawdę wewnętrzny szczegół implementacji.

— Filip Milovanović

BTW, myślę, że jest to częściowo związane z językiem, ale także o tym, jak konceptualizujemy to, co robi kolejka. Dla większości ludzi, którzy znają znaczenie słowa „kolejka” lub są wprowadzani do pojęcia z tą metaforą (czekanie w kolejce), część wyjściowa znajduje się z przodu / na głowie; Podejrzewam, że twój przyjaciel wyobraża to bardziej jako coś w rodzaju potoku, w którym popychasz obiekty na jednym końcu (na początku lub w pewnym sensie „główce”) rury, a one wychodzą na drugim końcu.

— Filip Milovanović

Odpowiedzi:

Wchodzisz z tyłu kolejki i wychodzisz z przodu. W większości społeczeństw oznaczałoby to, że głowa jest przodem, a przedmioty są usuwane z głowy.

Javadoc dla kolejki wydaje się zgodzić z klasycznej definicji (czyli oryginalny jeden):

Niezależnie od zastosowanego porządku, kolejką jest ten element, który zostałby usunięty przez wywołanie metody remove () lub poll (). W kolejce FIFO wszystkie nowe elementy są wstawiane na końcu kolejki.

— Spencer Kormos
źródło

C ++ STL również się zgadza.

— Fabio Ceconello

Częstą terminologią dotyczącą FIFO / LIFO jest także usuwanie z góry kolejki / stosu. Wierzch psa jest głową, a nie ogonem. :-D

— Spencer Kormos

Wygląda na to, że odpowiedziałeś na pierwsze pytanie. Naprawdę często zdarza się, że użycie, które zrozumiałem, jest tradycyjne ... Dziękuję za referencje. Ale dla mnie nie jest tak ubrany w żelazo, dlaczego przód kolejki nazywa się „głową” ...

— Aidan Cully,

... więc w którym otworze psa kolejkujemy przedmioty? ;)

— ell

Ogon psa jest głową kolejki.

— Caleb

To, co ludzie w Stanach Zjednoczonych zwykle nazywają linią, tak jak w przypadku poczty, ludzie w innych krajach anglojęzycznych nazywają się kolejką. Tak więc Amerykanom łatwiej jest zachować prostą terminologię, zastępując „kolejkę” „kolejką”. Innymi słowy, kiedy jesteś na czele lub z przodu linii, jesteś następnym, który zostanie wezwany.

— Karl Bielefeldt
źródło

Być może jest to raczej pytanie o angielski, ponieważ wydaje się, że pojawiło się pytanie „dlaczego nazywamy przód głową?”.

— Aidan Cully

@AidanCully: ponieważ głowa na ciele jest (u czworonogów i innych zwierząt zorientowanych poziomo) skierowana do przodu lub do przodu.

— poza

To najlepsze możliwe wytłumaczenie dla nas, Amerykanów.

— iDevW,

Obie konwencje są w powszechnym użyciu. Z mojego doświadczenia, mówiąc ogólnie o kolejkach, element głowy jest kolejnym, który wychodzi z kolejki, a ogon jest miejscem, w którym elementy wchodzą do kolejki. Jest to zgodne z codziennym używaniem języka angielskiego - ustawiamy się w kolejce z tyłu, a następne, które ma zostać podane, znajduje się z przodu lub z przodu. (A jeśli tniesz, to dla ciebie jest na końcu linii!)

Jednak gdy kolejka (inaczej FIFO) jest implementowana jako bufor pierścieniowy , warunki są zwykle odwracane, ponieważ używana część bufora pierścieniowego przypomina węża krążącego po okręgu. Zakładając, że wąż porusza się do przodu, głowa jest oczywiście końcem prowadzącym ruch, który jest także końcem, na którym wkładane są przychodzące przedmioty.

— IJ Kennedy
źródło

Warto wspomnieć o okrągłych buforach w jądrze Linuksa , które wykorzystują konwencję, że elementy są dodawane na czele, a usuwane na ogonie.

— Craig McQueen