#Niezbędnik Juniora. Kolekcje w języku Java

By 16 June 2015Niezbędnik Juniora

W kur­sie Javy (a dokład­niej w lekcji 5) omówione były już pod­stawy kolekcji w języku Java. Dzisi­aj posz­erza­my tą wiedzę o infor­ma­c­je, które moga Ci się przy­dać w pra­cy oraz na roz­mowach.Kolekc­je to ta gru­pa obiek­tów z którą spotkasz się bard­zo szy­bko w swo­jej kari­erze. O ile częs­to wystar­czy ich pod­sta­wowa zna­jo­mość, warto nieco się zgłębić i poz­nać ich wady/zalety, aby wiedzieć którą kolekc­je zas­tosować kiedy. W tej lekcji zajmiemy się imple­men­tac­ja­mi, które rozsz­erza­ją inter­fe­js Col­lec­tion.

Słowem wstępu — notacja dużego O

Zan­im prze­jdziemy do opisu poszczegól­nych kolekcji, zatrzy­ma­jmy się na moment, żeby omówić sobie notację dużego O, która będzie nam potrzeb­na do porów­na­nia różnych kolekcji. Szczegółowe infor­ma­c­je na ten tem­at zawrze­my w odd­ziel­nym wpisie, dzisi­aj jedynie wstęp.

Notac­ja dużego O służy w infor­matyce do porówny­wa­nia klas algo­ryt­mów w sposób miar­o­da­jny — weźmy na przykład sor­towanie. Najprost­szym sposobem na porów­nanie różnych pode­jść jest zmierze­nie cza­su sor­towa­nia tych samych ele­men­tów, np. 100 liczb. Meto­da A zro­bi to w 10 jed­nos­tek cza­su a meto­da B zro­bi to w 20 jed­nos­tek cza­su. Czy znaczy to, że meto­da A jest lep­sza / wyda­jniejsza? Abso­lut­nie nie! Wykonu­jąc próbę dla 1000 liczb okaże się, że meto­da A potrze­bu­je już 100 jed­nos­tek cza­su, a meto­da B tylko 50. Aby rozwiązać ten prob­lem wprowad­zono notację dużego o, która mówi nam nie ile cza­su zajmie pew­na oper­ac­ja, ale jak ten czas się zmienia w zależnoś­ci od iloś­ci danych, na których pracu­je­my.

Brz­mi skom­p­likowanie, ale to naprawdę proste! Weźmy dla przykładu algo­rytm, który losu­je liczbę z przedzi­ału (a, b). Dla uproszczenia pomyślmy o tym jako o człowieku, który z wor­ka wszys­t­kich możli­wych liczb z tego przedzi­ału wybiera jed­ną. Czy czas potrzeb­ny na wybranie tej licz­by zmieni się w zależnoś­ci od tego czy w worku będzie 5, 50 czy 500000 liczb? Nie! Oznacza to, że algo­rytm ten dzi­ała w cza­sie stałym, który oznacza­my jako O(1). A dlaczego O(1) a nie np. O(3) ? Ponieważ intere­su­je nas jedynie sposób, w jaki ten czas rośnie, a nie sam czas. Jeśli jest stały, uży­wamy po pros­tu jed­nos­t­ki, aby pokazać, że się nie zmienia.

Jako dru­gi przykład weźmy algo­rytm, który dla każdej licz­by od zera do x wyp­isu­je ją na kon­soli. W zależnoś­ci od wejś­cia (x w tym wypad­ku) nasz algo­rytm będzie musi­ał wykon­ać różną ilość oper­acji — w tym wypad­ku dla każdej jed­nej licz­by będzie to określona, stała licz­ba oper­acji (ponown­ie, nie ma znaczenia, czy będą to 3 oper­ac­je czy 50, ważne, że jest to stała ilość). Dlat­ego algo­rytm ten ma złożoność obliczeniową O(n).

A co, jeśli poprzed­ni algo­rytm zmody­fiku­je­my tak, aby wyp­isy­wał też kwadrat tej licz­by? Nic się nie zmieni, ponieważ wyp­isanie oraz oblicze­nie kwadra­ta licz­by są oper­ac­ja­mi o stałym cza­sie wyko­na­nia, a więc złożoność nadal będzie wynosiła O(n).

Złożoność jest bard­zo waż­na ponieważ częs­to nie wiemy, ile dokład­nie danych będzie przetwarzanych w naszym sys­temie i przez to nie jesteśmy w stanie wykon­ać miar­o­da­jnych prób cza­sowych. Nawet jes­li byśmy to zro­bili, te założe­nia będą się zmieni­ać z cza­sem. Dlat­ego o ile nie jesteśmy abso­lut­nie pewni, że będziemy przetwarzać określoną, niewielką ilość infor­ma­cji (np. kilka­naś­cie) w danym miejs­cu, zawsze powin­niśmy wybier­ać algo­rytm o najm­niejszej złożonoś­ci, a nie taki, który dzi­ała szy­b­ciej (cza­sowo) pod­czas testów. Oczy­wiś­cie od tej reguły moż­na robić wyjąt­ki, ale tylko pod warunk­iem, ze naprawdę wiemy co robimy, a decyz­ja ta została zwery­fikowana i udoku­men­towana w specy­fikacji pro­jek­tu.

Porów­nanie złożonoś­ci oper­acji we wszys­t­kich kolekc­jach możesz znaleźć na stron­ie http://infotechgems.blogspot.ie/2011/11/java-collections-performance-time.html .

Zachę­camy także do zapoz­na­nia się z mate­ri­ała­mi dostęp­ny­mi pod adresem https://codility.com/media/train/1-TimeComplexity.pdf .

Rodzaje kolekcji w Javie

Poniżej omówimy poszczególne rodza­je kolekcji, dla każdej z nich podamy zas­tosowa­nia, najważniejsze cechy oraz stan­dar­d­owe imple­men­tac­je.

Tablica

Dla przeko­ry pier­wszą omaw­ianą struk­turą będzie tabli­ca. Dla przeko­ry ponieważ tablice nie są stricte kolekc­ja­mi (w tym sen­sie, że nie imple­men­tu­ją inter­fe­j­su Col­lec­tion), a ele­mentem języ­ka Java. Jako jedyne mogą prze­chowywać prymi­ty­wy (we wszys­t­kich innych przy­pad­kach ma miejsce auto­box­ing — automaty­cz­na zami­ana prymi­w­ty­wu na odpowiada­jącą mu reprezen­tac­je obiek­tową — jeśli spróbu­je­my dodać prymi­tyw).

Tabli­ca to uporząd­kowany (mają­cy kole­jność, ale niekoniecznie posor­towany!) zbiór ele­men­tów, które fizy­cznie w pamię­ci kom­put­era są umieszc­zone obok siebie. Umożli­wia­ją dostęp losowy (tzw. Ran­dom Access), czyli dostęp do ele­men­tu na dowol­nie wybranej pozy­cji. Ele­men­ty tabl­i­cy mogą mieć wartość null! Aby utworzyć tablicę sto­su­je­my poniższą kon­strukcję:

String[] tablica = new String[6];

Doz­wolone jest także umieszcze­nie naw­iasów kwadra­towych za nazwą zmi­en­nej:

String tablica[] = new String[6];

Jak pewnie zauważyłaś, nie uży­wamy tutaj naw­iasów () jak w przy­pad­ku kon­struk­torów obiek­tów.

Inna dopuszczal­na skład­nia, która od razu inicju­je tablicę wartoś­ci­a­mi jest poniższa:

String[] tablica = {"jeden", "dwa", "trzy", "cztery", "pięć", "sześć"};

Ist­nieje jeszcze jed­na możli­wość zadeklarowa­nia tabl­i­cy — jako ostat­ni argu­ment metody, dzię­ki czemu może one przyj­mować nieokreśloną liczbę argu­men­tów. Weźmy na przykład poniższą metodę:

public void wypiszStringiWNowychLiniach(String... tablica) { //argument ten jest tablicą
    for (i = 0; i<tablica.length; i++) {
        System.out.println(tablica[i]);
    }
}

//przykładowe wywołania
wypiszStringiWNowychLiniach("jeden", "dwa", "trzy", "cztery", "pięć");
String[] tablica = {"jeden", "dwa", "trzy", "cztery", "pięć"};
wypiszStringiWNowychLiniach(tablica);

W powyższym przykładzie widz­imy też jak odwoły­wać się do ele­men­tów tabl­i­cy — w prze­ci­wieńst­wie do kolekcji nie uży­wamy metod, a skład­ni, pisząc nazwę zmi­en­nej a następ­nie w naw­iasie kwadra­towym numer ele­men­tu.

Ostat­nia bard­zo waż­na infor­ma­c­ja na tem­at tablic jest taka, że rozmi­aru tabl­i­cy nie moż­na zmieni­ać! Jeśli utworzymy tablicę z 6 ‘miejs­ca­mi’, aby  dodać do niej 7 ele­ment, będziemy musieli utworzyć nową, więk­szą, tablicę i przepisać wcześniejsze 6 ele­men­tów.

Lista (java.util.List)

Listy są jed­ny­mi z najczęś­ciej uży­wanych kolekcji — kon­cep­cyjnie są podob­ne do tablic, moż­na jed­nak (tak jak w przy­pad­ku wszys­t­kich pozostałych kolekcji) dynam­icznie zmieni­ać ich rozmi­ar (dodawać i usuwać ele­men­ty). Ele­men­ty w liś­cie mogą się pow­tarzać (tzn. ten sam obiekt może być na liscie wielokrot­nie). Ist­nieje kil­ka stan­dar­d­owych imple­men­tacji, z których najważniejsze zostały opisane poniżej:

Klasa Cechy Zas­tosowanie
ArrayList
  •  w ‘tle’ prze­chowu­je dane w tabl­i­cy, której samodziel­nie zmienia rozmi­ar wg potrzeb
  • dostęp do dowol­nego ele­men­tu w cza­sie O(1)
  • dodanie ele­men­tu O(1), pesymisty­czny przy­padek O(n)
  • usunię­cie ele­men­tu O(n)
 Najczęst­szy wybór z racji najbardziej uni­w­er­sal­nego zas­tosowa­nia. Inne ime­ple­men­tac­je mają przewagę tylko w bard­zo specy­ficznych przy­pad­kach. Jeśli nie wiesz, jakiej listy potrze­bu­jesz, wybierz tą.
LinkedList
  •  prze­chowu­je ele­men­ty jako lista pow­iązanych ze sobą obiek­tów (tj. pier­wszy ele­ment wie, gdzie jest dru­gi, dru­gi wie, gdzie trze­ci itd)
  • dostęp do dowol­nego ele­men­tu O(n) (iter­a­cyjnie O(1) )
  • dodanie ele­men­tu O(1)
  • usunię­cie ele­men­tu O(1)
 LinkedList ma przewagę w przy­pad­ku dodawa­nia ele­men­tów poje­dync­zo, w dużej iloś­ci, w sposób trud­ny do przewidzenia wcześniej, kiedy prze­j­mu­je­my się iloś­cią zaj­mowanej pamięci.W prak­tyce nie spotkałem się z sytu­acją, w której LinkedList było­by wyda­jniejsze od ArrayList
Vec­tor
  • Ist­nieje od początku Javy, z założe­nia miała to być  obiek­towa reprezen­tac­ja tabl­i­cy
  • Funkcjon­al­ność i cechy ana­log­iczne do ArrayList, ale znacznie mniej wyrafi­nowane
API ofic­jal­nie zale­ca korzys­tanie z klasy ArrayList zami­ast Vec­tor

Imple­men­tacją inter­fe­j­su List jest także klasa Stack — będziemy jed­nak omaw­iać stos jako osob­ną struk­turę i tam omówimy tą klasę.

Aby utworzyć nową listę (do przykładów bedziemy korzys­tać z ArrayListy) wystar­czy wywołać kon­struk­tor:

List<String> lista = new ArrayList<String>();

Do dodawa­nia ele­men­tu służy meto­da add:

lista.add("jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem metody get, poda­jąc pozy­cję ele­men­tu jako argu­ment:

String pierwszy = lista.get(0);

Stan listy może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = lista.size();
boolean listaJestPusta = lista.isEmpty();

Set / zbiór (java.util.Set)

Sety to zbio­ry ele­men­tów, w których nie może­my uzyskać dostępu do n’tego ele­men­tu, a jedynie może­my pobrac iter­a­tor (obiekt, który poz­woli nam pobrać kole­jne ele­men­ty, w zależnoś­ci od imple­men­tacji w porząd­ku posor­towanym lub losowym). Ele­men­ty w Setach nie mogą się pow­tarzać.

Klasa Cechy Zas­tosowanie
Hash­Set
  • zbiór nieposor­towany
  • kole­jność iter­acji nieokreślona, może się zmieni­ać
  • dodanie ele­men­tu oraz sprawdze­nie czy ist­nieje ma złożoność O(1)
  • pobranie kole­jnego ele­men­tu ma złożoność O(n/h), gdzie h to para­metr wewnętrzny (pesymisty­czny przy­padek: O(n) )
Sytu­acje, kiedy nie potrze­bu­je­my dostępu do konkret­nego ele­men­tu, ale potrze­bu­je­my częs­to sprawdzać, czy dany ele­ment już ist­nieje w kolekcji (czyli chce­my zbu­dować zbiór unikalnych wartości).W prak­tyce częs­to zna­j­du­je zas­tosowanie do raportowania/zliczeń oraz jako ‘prze­chowal­nia’ obiek­tów do przetworzenia (jeśli ich kole­jność nie ma znaczenia).
Linked­Hash­Set
  • ana­log­iczne, jak Hash­Set (dziedz­iczy po nim)
  • kole­jność ele­men­tów uży­wa­jąc iter­a­to­ra jest deter­min­isty­cz­na i pow­tarzal­na (zawsze będziemy prze­chodz­ić przez ele­men­ty w tej samej kole­jnoś­ci)
  • pobranie kole­jnego ele­men­tu ma złożoność O(1)
Jesto to mniej znana i rzadziej stosowana imple­men­tac­ja, częs­to może ona zastąpić Hash­Set poza specy­ficzny­mi przy­pad­ka­mi. W prak­tyce do iterowa­nia w określonej kole­jnoś­ci częs­to uży­wane sa inne kolekc­je (Listy, kole­j­ki)
TreeSet
  • Prze­chowu­je ele­men­ty posor­towane wg porząd­ku nat­u­ral­nego (jeśli imple­men­tu­ją one inter­jfe­js Com­pa­ra­ble, w prze­ci­wnym wypad­ku porządek jest nieokres­lony)
  • Wszys­tkie oper­ac­je (dodanie, sprawdze­nie czy ist­nieje oraz pobranie kole­jnego ele­men­tu) mają złożoność O(log n)
Jeśli potrze­bu­je­my, aby nasz zbiór był posor­towany bez dodatkowych oper­acji (sor­towanie nastepu­je już w momen­cie doda­nia ele­men­tu) oraz iterować po posor­towanej kolekcji.

Aby utworzyć nowy set (do przykładów bedziemy korzys­tać z Hash­Set) wystar­czy wywołać kon­struk­tor:

Set<String> set = new HashSet<String>();

Do dodawa­nia ele­men­tu służy meto­da add:

set.add("jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem iter­a­to­ra, np w pętli for:

for (String string : set) {
    ...
}

Stan zbioru może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = set.size();
boolean zbiorJestPusty = set.isEmpty();

Map (java.util.Map)

Mapy nie imle­men­tu­ją wprawdzie inter­fe­j­su Col­lec­tion, ale są także częś­cią Java Col­lec­tions API. Prze­chowu­ją one mapowa­nia pomiędzy klucza­mi, a wartoś­ci­a­mi. Zarówno dodanie ele­men­tu, jak i jego pobranie wyma­ga poda­nia klucza. Kluczem może być dowol­ny obiekt. Ele­men­ty w Mapach mogą się pow­tarzać, pod warunk­iem, że sa one wartoś­ci­a­mi. Klucze nie mogą się pow­tarzać. Mapy mają wiele wspól­nego z omaw­iany­mi wyżej zbio­ra­mi (moż­na o nich myśleć jak o zbio­rach pow­iązań pomiędzy kluczem i wartoś­cią), przez co jak pewnie zauważysz dzielą wiele cech wspól­nych.

Klasa Cechy Zas­tosowanie
HashMap
  • mapa nieposor­towana
  • kole­jność iter­acji nieokreślona, może się zmieni­ać
  • dodanie ele­men­tu oraz sprawdze­nie czy klucz ist­nieje ma złożoność O(1)
  • pobranie kole­jnego ele­men­tu ma złożoność O(h/n), gdzie h to para­metr wewnętrzny
Ogól­ny przy­padek, tworze­nie lokalnej pamię­ci podręcznej czy ‘słown­i­ka’ o ogranic­zonym rozmi­arze, zliczanie wg klucza.
Linked­HashMap
  • ana­log­iczne, jak HashMap (dziedz­iczy po niej)
  • kole­jność kluczy uży­wa­jąc iter­a­to­ra jest deter­min­isty­cz­na i pow­tarzal­na (zawsze będziemy prze­chodz­ić przez klucze w tej samej kole­jnoś­ci)
  • pobranie kole­jnego ele­men­tu ma złożoność O(1)
Podob­nie jak Linked­Hash­Set, rzadziej znana i stosowana. Przy­dat­na, jeśli potrze­bu­je­my iterować po kluczach w założonej kole­jnoś­ci.
TreeMap
  • Prze­chowu­je ele­men­ty posor­towane wg porząd­ku nat­u­ral­nego kluczy (jeśli imple­men­tu­ją one inter­jfe­js Com­pa­ra­ble, w prze­ci­wnym wypad­ku porządek jest nieokres­lony)
  • Wszys­tkie oper­ac­je (dodanie, sprawdze­nie czy klucz ist­nieje oraz pobranie kole­jnego ele­men­tu) mają złożoność O(log n)
Jeśli potrze­bu­je­my, aby nasz zbiór był posor­towany wg kluczy bez dodatkowych oper­acji (sor­towanie nastepu­je już w momen­cie doda­nia ele­men­tu) oraz iterować po posor­towanej kolekcji.
 Hashtable
  •  His­to­rycz­na klasa, która w Javie 1.2 została włąc­zona do Java Col­le­cion API
Ofic­jal­nie zale­ca się korzys­tanie z Hash­Set w więk­szoś­ci wypad­ków zami­ast Hashtable

Aby utworzyć nową mapę (do przykładów bedziemy korzys­tać z HashMap) wystar­czy wywołać kon­struk­tor:

Map<Integer, String> map= new HashMap<Integer,String>();

Do dodawa­nia ele­men­tu służy meto­da put:

map.put(1, "jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem metody get, poda­jąc klucz jako argu­ment:

String string = map.get(1)

Stan mapy może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = map.size();
boolean mapaJestPusta = map.isEmpty();
boolean zawieraKlucz = map.containsKey(1);
boolean zawieraWartosc = map.containsValue("jeden");

Kolejki (java.util.Queue)

Kole­j­ki dzielą się na dwa typy — LIFO (last-in, first-out) oraz FIFO (first-in, first-out). Przykła­dem kole­j­ki LIFO jest stos, mówiąc o kole­jce częs­to mamy na myśli kole­jkę FIFO. Co ciekawe, w języku Java klasa Stack imple­men­tu­je inter­fe­js listy, a nie kole­j­ki. Drugą cieka­wostką jest fakt, że klasa LinkedList także imple­men­tu­je inter­fe­js Queue (ponieważ była ona już omówiona wczes­niej, nie będziemy pow­tarzać).

W kole­jkach wyróż­ni­amy głowę oraz ogon — stadar­d­owo inter­fe­js Queue pozwala na pracę tylko z głową, inter­fe­js Dequeue (który dziedz­iczy po Queue) pozwala na pracę zarówno z głową jak i ogonem.

Ideą kole­jek jest prze­chowywanie ‘kole­j­ki’ obiek­tów do przetworzenia w określonej kole­jnoś­ci, stanow­ią pewnego rodza­ju bufor obiek­tów.

Klasa Cechy Zas­tosowanie
Array­D­eque
  • Prze­chowu­je ele­men­ty w tabl­i­cy
  • Ma nieogranic­zoną pojem­ność (automaty­cznie rozsz­erza tablicę wpamię­ci)
  • Dodanie i pode­jrze­nie ele­men­tu mają złożoność O(1)
  • Pobranie ele­men­tu ma złożoność O(n)
Uni­w­er­sal­na imple­men­tac­ja pasu­ją­ca do więk­szoś­ci przy­pad­ków, dzi­ała na zasadzie FIFO, możli­wość pra­cy także z ogonem powodu­je że sprawdzi się także jako kole­j­ka LIFO
Pri­or­i­tyQueue
  • Nie umożli­wa prze­chowywa­nia wartoś­ci null
  • Nie jest stricte kole­jką FIFO, ponieważ kole­jność ele­men­tów zalezy od ‘pri­o­ry­te­tu’ — w najprost­szym przy­pad­ku ele­men­ty są po pros­tu sor­towane
 Uży­wana najczęś­ciej jako kole­j­ka zadań, które mają określony pri­o­ry­tet, tzn jedne są ważniejsze od innych.
Stack
  •  Kole­j­ka typu LIFO (stos)
  • API niez­godne z inter­fe­jsem Queue!
  • imple­men­tu­je inter­fe­js List, dziedz­iczy po Vec­tor
 Imple­men­tac­ja ta była od początku Javy, przed pow­staniem Col­lec­tions API. Obec­nie raczej zale­cane jest korzys­tanie np. z Array­D­e­queue

Poniższy opis obe­j­mu­je jedynie inter­fe­js Queue, którego klasa Stack nie imple­men­tu­je. Aby z niej sko­rzys­tać, zapoz­naj się z doku­men­tacją API.

Aby utworzyć nową kole­jkę (do przykładów bedziemy uży­wać Array­D­e­queue) wystar­czy wywołać kon­struk­tor:

Queue<String> kolejka = new ArrayDequeue<String>();

Do dodawa­nia ele­men­tu służą metody add oraz offer:

kolejka.add("jeden"); //jeżeli kolejka jest pełna, rzuci wyjątek
kolejka.offer("jeden"); //nie rzuci wyjątku, a jedynie zwróci false

Pobieranie ele­men­tów odby­wa się z uży­ciem metod remove i poll:

String string = kolejka.remove(); //jeżeli kolejka jest pusta, rzuci wyjątek
String string = kolejka.poll(); //jeżeli kolejka jest pusta, zwróci null

Kole­j­ka pozwala nam także ‘pode­jrzeć’ kole­jny ele­ment nie usuwa­jąc go z kole­j­ki, służą do tego metody ele­ment oraz peek:

String string = kolejka.element(); //jeżeli kolejka jest pusta, rzuci wyjątek
String string = kolejka.peek(); //jeżeli kolejka jest pusta, zwróci null

Stan kole­j­ki może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = kolejka.size();
boolean kolejkaJestPusta = kolejka.isEmpty();

Podsumowanie

W ramach pod­sumowa­nia zbierze­my infor­ma­c­je o wszys­t­kich omówionych rodza­jach kolekcji w formie tabeli. Warto też zapoz­nać się z ofic­jal­ną doku­men­tacją na tem­at col­lec­tions API, dostęp­nńą pod adresem http://docs.oracle.com/javase/8/docs/technotes/guides/collections/ .

Kolekc­ja Cechy imple­men­tac­je
Object[] uporząd­kowana
dostęp losowy (n’ty ele­ment)
może zaw­ier­ać dup­likaty
może zaw­ier­ać wartoś­ci null
struk­tu­ra języ­ka
może prze­chowywać prymi­ty­wy
niezmi­en­na pojem­ność
nie doty­czy
List uporząd­kowana
dostęp losowy (n’ty ele­ment)
może zaw­ier­ać dup­likaty
ArrayList
LinkedList
Stack
Vec­tor
Set zbiór nieu­porząd­kowany
nie może zaw­ier­ać dup­likatów
dostęp do ele­men­tów możli­wy tylko poprzez iter­a­tor
Hash­Set
Linked­Hash­Set
TreeSet
Map mapu­je klucz na wartość
możli­we dup­likaty (tylko w przy­pad­ku wartoś­ci, klucze nie mogą się pow­tarzać)
dostęp do obiek­tów poprzez klucz lub iter­a­cyjnie
HashMap
Linked­HashMap
TreeMap
Queue kole­j­ka first-in, first-out
możli­wość pobiera­nia pier­wszego ele­men­tu poprzez jego ‘zdję­cie’ z kole­j­ki lub pode­jrze­nie
Array­D­e­queue
Pri­or­i­tyQueue
LinkedList
  •  
  •  
  •  
  •  
  •