Niedawno w wywiadzie zapytano mnie o wadę korzystania z okrągłej kolejki. Nie mogłem myśleć o żadnym. Przeszukując internet jedyną odpowiedzią, jaką znalazłem, jest to, że trudno ją zrealizować niż kolejkę liniową :). Czy są jakieś inne wady?Wada okrągłej kolejki?
Wydaje mi się, że każdy kod przechodzący przez kolejkę musiałby śledzić pierwszy węzeł, aby wykryć koniec trawersu. Ale w środowisku wielowątkowym inny wątek może usunąć pierwszy węzeł, co spowoduje, że wątek przechodzi w nieskończoną pętlę. Tak więc wątek przechodzący musiałby utrzymywać pierwszy węzeł zablokowany na czas trwania swojego cyklu przez kolejkę.
Z drugiej strony zwykle występują zagrożenia związane z używaniem jakiejkolwiek listy podczas wyliczania. Na przykład ogon regularnej listy połączonej może zostać usunięty i przeniesiony do głowy (niezbyt często w przypadku kolejek), co może przerwać iterację. – nneonneo
Czy nie stanie się to w przypadku pamięci współdzielonej między wieloma procesami? Pytam, gdy wyraźnie zaznaczasz * wątki * – asheeshr
@AshRj Tak, z pewnością może się zdarzyć w przypadku wielu procesów. –
Powiedziałbym, że największą wadą kolistej kolejki jest możliwość przechowywania tylko elementów queue.length. Jeśli używasz go jako bufora, ograniczasz głębokość historii.
Kolejną mniejszą wadą jest to, że trudno jest powiedzieć pustą kolejkę z pełnej kolejki bez zachowania dodatkowych informacji.
Nie takie trudne. Zobacz komentarze w pytaniu. Są co najmniej 2 sposoby na zrobienie tego ... –
Odpowiedź, której szukał analityk prawdopodobnie zależy od jakiegoś dodatkowego kontekstu, który nie znajduje się w powyższym pytaniu.
Na przykład, często okrągłe kolejki są brane pod uwagę w bardzo równoczesnych systemach producentów/konsumentów. Gdy kolejka jest pełna, operacje z przodu iz tyłu kolejki mogą dotyczyć tych samych linii pamięci podręcznej, co może stanowić problem w takich kontekstach.
A może prowadzący wywiad chciał, abyś porozmawiał o tym, o ile łatwiej jest w języku, który zbiera śmieci, by utworzyć pozbawioną blokady połączoną kolejkę w porównaniu z kolejką opartą na tablicy.
A może chodzi tylko o to, jak lepiej wykorzystać pojemniki wektorowe dostarczone przez twój język, jeśli używasz liniowej kolejki z okresową zmianą zamiast okrągłej kolejki.
W zależności od implementacji, może być konieczne pozostawienie węzła pustego w okrągłej kolejce, podczas gdy liniowa kolejka zostanie całkowicie wypełniona. Nie jest to żadną wadą, chyba że każdy węzeł jest gigantyczny! – asheeshr
dlaczego węzeł musi pozostać pusty? –
To zależy od sposobu wdrożenia kolejki cyklicznej. Jeśli przechowujesz dane w każdym węźle, nie ma łatwego sposobu na rozróżnienie między pustą i pełną listą. – asheeshr