Java: Queue and Deque

0:00Cześć do tej pory poznaliśmy sety listy i mapy

0:04i są to tak naprawdę najczęściej wykorzystywane na co dzień przez nas struktury

0:08jest jednak pewna jeszcze odnoga która jest rzadziej wykorzystywana jest to queue

0:12i deque teraz do czego one służą queue jak nazwa

0:16wskazuje jest to po prostu kolejka ta struktura narzuca nam pewną taką semantykę

0:21pracy z danymi która pozwala nam nam na wrzucanie z jednej strony elementów

0:25oraz wyciągania z drugiej deque zaś pozwala nam na wrzucanie

0:29i wyciąganie z każdej strony tak deque jest double-ended queue no

0:33i teraz używając queue możemy wrzucać elementy i wyciągać je w tej samej

0:37kolejności natomiast używając deque możemy je wrzucać

0:42i na przykład wyciągać w odwrotnej kolejności czyli osiągnąć efekt który daje

0:46nam stos taka struktura deque jest implementowany przez link listę

0:50i to jest prawdopodobnie najczęściej wykorzystywana implementacja ale

0:54też są jeszcze implementacje oparte o array ok stwórzmy sobie

0:58kolejkę integerów oraz podstawmy implementację w postaci link listy oraz

1:03na początek zobaczymy sobie jakie możliwości daje nam ten interfejs mamy przede wszystkim tutaj

1:07metodę add która jest dziedziczona z collection w parze do metody add

1:11mamy metodę pool która powiedzmy wyciąga jeden element i nam go zwraca

1:16poza tym do metody pool jest jeszcze metoda remove one robią dokładnie

1:20to samo tylko jest inne zachowanie tych metod w momencie kiedy nie

1:25ma elementów już prawda w tej kolekcji polł jeżeli jest powiedzmy

1:29element nam go zwróci jeżeli go nie ma to po prostu zwróci nam null natomiast

1:33remove jeżeli nie istnieje element w kolekcji no to rzuci nam

1:37w tym momencie wyjątkiem podobnie jest z metodami peek i element peek

1:42w stosunku do pull i remove zwraca nam element ale nie usuwa

1:46go z kolejki element tak samo bo to jest też różnica w zachowaniu

1:50jeżeli nie ma elementów kolekcji peek zwróci nam null a element rzuci

1:54nam wyjątkiem za to metoda offer jest metodą która ma znaczenie

1:58w momencie kiedy wykorzystujemy ograniczonych jeżeli chodzi o maksymalny

2:03rozmiar kolejki add ona pozwala nam dodać jakiś element

2:07tylko wtedy jeżeli jest na nią miejsce i tutaj właśnie jest ta flaga boolean tak

2:11która nam mówi że udało się dorzucić ten element do kolekcji albo nie warto

2:16również podkreślić że jeżeli użyjemy add na kolekcji która jest

2:20ograniczona rozmiarem tak to jeżeli nie ma miejsca w tej kolekcji to

2:24zamiast dostać powiedzmy false'a dostaniemy w tym momencie wyjątek

2:28tak add na queue zawsze jeżeli nie rzuci wyjątkiem zawsze

2:32zwróci true okej spróbujmy sobie zaimplementować jakieś zachowanie wykorzystując

2:37te metody pierwsza rzecz to dodajemy sobie kilka elementów do tej kolejki oraz

2:41wyprintujmy co się znajduje w środku jak widzimy zachowanie jest tutaj bardzo intuicyjne

2:45teraz spróbujmy wyciągnąć te elementy razem z usuwaniem ich więc wykorzystuje

2:50metodę poll w ten sposób tak tutaj wyciągałem po kolei te elementy w tej samej

2:54kolejności jak zostały wrzucone tutaj zauważ że jeżeli wywołamy

2:58o jeden za dużo operacji poll dostaniemy po prostu null'a zachowanie

3:02remove jest takie samo jak poll z tym wyjątkiem że na koniec

3:06kiedy wywołujemy remove na pustej kolekcji to po prostu dostajemy w tym momencie

3:10wyjątek jeżeli chcemy tylko podejrzeć co znajduje się w kolekcji

3:15zostanie wyciągnięty przy następnym wywołaniu poll bądź remove możemy

3:19wykorzystać peek lub element zachowanie tych metod zmieni się jeżeli nie zostanie

3:23żaden element w kolekcji jak widzimy operacja peek zwróci nam

3:27null a operacja element po prostu rzuci wyjątkiem teraz zamiast

3:31linked list podstawmy sobie inną implementację jest to na przykład array blocking

3:35queue jest to implementacja w której można ograniczyć capacity tak

3:39czyli powiedzmy maksymalny rozmiar tej kolekcji tak dzięki temu

3:43możemy sobie zobaczyć jak różni się działanie add od offer jak sobie wywołamy ten przykład

3:48po prostu damy dwie piątki do naszej kolekcji później bez problemu możemy je

3:52wyciągnąć tak wykorzystując poll teraz jeżeli dodamy trzeciego add'a

3:57i próbujemy to wywołać to dostaniemy exception że queue jest full natomiast

4:01jeżeli wykorzystamy w tym miejscu offer oraz wypiszemy co zwraca

4:05ta metoda to nie dostaniemy już wyjątku tylko po prostu dostaniemy false

4:09z tego względu że nie udało się znaleźć tego elementu zwiększymy teraz capacity na przykład

4:13na 3 to bez problemu uda się dodać kolejny element i dostaniemy w tym miejscu true

4:18okej jeżeli teraz sobie podmienimy interfejs queue na

4:22deque czyli double ended queue to możemy dalej wykorzystywać wszystkie te metody

4:26które mieliśmy w queue ale teraz te metody mają dodatkowo rozróżnienie

4:30możemy wywołać add ale możemy zamiast tego wywołać add first

4:34lub add last tak i dokładnie wskazać na który koniec

4:39tej kolejki ma być dodany element tak żeby zachować to samo zachowanie teraz

4:43zrobimy add last tak sobie wyprintujemy co tam da i teraz

4:47możemy w tej samej kolejności ściągnąć w jaki dodaliśmy tak czyli wykorzystamy

4:51poll first prawda teraz moglibyśmy zrobić zamiast

4:55poll first możemy zrobić na przykład poll last tak na queue nie byliśmy w

5:00stanie tego zrobić i teraz zauważ że ściągamy elementy powiedzmy

5:04z tej kolejki w odwrotnej kolejności niż je wrzucaliśmy tak i w ten sposób możemy

5:08uzyskać właśnie efekt stosu tak okej cała reszta metod między

5:13queue a deque nie różni po prostu wykorzystując add czy powiedzmy

5:17jakiegoś polla element remove i tak dalej musimy wyspecyfikować

5:21o który koniec tej kolejki nam chodzi okej to jest koniec tej lekcji

5:25jest to również koniec rozdziału o kolekcjach bardzo dziękuję ci za

5:29poświęcony czas i mam nadzieję że zdobyta wiedza pomoże ci w rozwiązywaniu codziennych

5:33problemów dzięki wielkie do usłyszenia