Cześć,
Mam pytanie, kiedy powinienem stosować liste, a kiedy kolejke?
Mam taki przypadek, że usuwam elementy zawsze z przodu i zawsze dodaje elementy na koniec. Czy jak zostosuje kolejke będę te operacje szybciej wykonywał?
Są jeszcze jakieś zalety albo jakies inne kontenery, ktore bardziej by tutaj pasowały?
Kolejka to jest raczej interface, a lista to implementacja
ArrayDeque na ogół chyba będzie szybsze, ale dla standardowych rozmiarów kolekcji (1,2,5 czy 10 elementów) to żadna różnica ;)
A kolejkę się stosuje wtedy kiedy chcesz wywoływać operacje jak na kolejce :D Osobiście sam nigdy standardowej kolejki nie używałem, jak już to BlockingQeue ;]
Struktury te, niezależnie od języka, różnią się implementacją wewnętrzną, tak, aby wydajnej wykonywać pewne operacje. Poza samym podziałem na kolejki i listy istnieje podział bardziej szczegółowy np na kolejki dwu i jednokierunkowe itp itd. Znaczenie przy wyborze tych struktur może mieć czy będziesz dokładał elementy do kolekcji, czy będziesz je dokładał tylko na końcu, czy również w środku.
Kolejkę FIFO jako koncept (strukturę danych) możesz zaimplementować na wiele sposobów - np. używając tablicy, LinkedListy. Java daje do tego konkretną implementację - ArrayDeque, co nie znaczy, ze nie możesz posłużyć się po prostu LinkedListą. Kluczowe tutaj jest zrozumienie złożoności obliczeniowej operacji na strukturze danych (dodawanie i usuwanie powinno być O(1)) + kwestie synchronizacji, które mogą spowolnić całość (np. klasa Vector).
@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.