@elo_elo_elo: po kolei, Kolejka to struktura, która co do zasady realizuje poniższe założenia:
– dodanie elementu powoduje, że ląduje on na końcu kolejki,
– odczytanie elementu powoduje usunięcie go z początku kolejki.
I tak działa typowa kolejka FIFO (First In, First Out). Modyfikacją kolejki jest kolejka z priorytetami, czyli taka, gdzie o kolejności odczytu decyduje poza kolejnością dodania jeszcze jeden parametr zwany priorytetem. Przykładowo:
Do apteki przychodzą klienci i są obsługiwani w kolejności, w jakiej pojawili się w aptece. To jest kolejka FIFO.
Jeżeli jednak pojawi się kobieta w ciąży, to jest obsługiwana poza kolejnością, ponieważ ma wysoki priorytet. To jest kolejka z priorytetami.
Jeżeli jednak w kolejce stoją już emeryci i pojawi się ciężarna, to musi nastąpić uzgodnienie priorytetów, które zdefiniuje kolejność obsługi. Oczywiście może pojawić się posiadacz odznaki ZHDK i jest jeszcze weselej…
Cechą szczególną kolejki jest, że formalnie nie można (poza użyciem priorytetów) dodawać i usuwać elementów, które znajdują się w środku. Kolejka ponadto może mieć ograniczoną wielkość.
Lista jest strukturą, która pozwala na (w uproszczeniu):
– dodawanie elementów w dowolnym miejscu,
– usuwanie elementów z dowolnego miejsca.
Lista może być jednokierunkowa albo dwukierunkowa. W liście jednokierunkowej mając dowolny element An możesz przejść jedynie do elementu An+1. Nie możesz się cofnąć tzn. z elementu An+1 nie dostaniesz się do elementu An. W przypadku list dwukierunkowych możesz się cofnąć.
Kolejka i lista w Javie.
Interfejsy List
i Queue
są niezależne, ale istnieje klasa LinkedList
, która implementuje oba z nich. I tyle jeżeli chodzi o API. Inne implementacje tych interfejsów mają swoje zastosowania, które pozwalają na tworzenie kodu współbieżnego lub różnią się złożonością pewnych operacji.