Struktury danych w Javie - stos i kolejka

Cześć! Dzisiaj porozmawiamy o rzeczach tak ważnych dla każdego programisty, jak struktury danych . Wikipedia mówi: Struktura danych ( ang. datastructure ) to jednostka oprogramowania, która umożliwia przechowywanie i przetwarzanie wielu danych tego samego typu i/lub logicznie powiązanych w informatyce. Definicja jest nieco myląca, ale jej istota jest jasna. Struktura danych to rodzaj magazynu, w którym przechowujemy dane do dalszego wykorzystania. W programowaniu istnieje ogromna różnorodność struktur danych. Bardzo często przy rozwiązywaniu konkretnego problemu najważniejsze jest wybranie najodpowiedniejszej do tego celu struktury danych. A wiele z nich już znasz! Na przykład z tablicami . A także z Map(co zwykle tłumaczy się jako „słownik”, „mapa” lub „tablica asocjacyjna”). Bardzo ważne jest zrozumienie: struktury danych nie są powiązane z żadnym konkretnym językiem . Są to po prostu abstrakcyjne „plany”, według których każdy język programowania tworzy własne klasy – implementacje tej struktury. Na przykład jedną z najbardziej znanych struktur danych jest lista połączona . Możesz zajrzeć do Wikipedii, przeczytać o tym, jak to działa, jakie ma zalety i wady. Być może jej definicja jest Ci znana :) „Lista połączona to podstawowa dynamiczna struktura danych w informatyce, składająca się z węzłów, z których każdy zawiera zarówno same dane, jak i jedno lub dwa łącza („łącza”) do następnego i/lub poprzednia lista węzłów” A więc to jest nasze LinkedList! Dokładnie tak to jest :) Struktura danych listy połączonej jest zaimplementowana w języku Java w klasie LinkedList. Ale inne języki również implementują listy połączone! W Pythonie nazywa się to „ llist”, w Scali nazywa się to tak samo jak w Javie - „ LinkedList„. Lista połączona jest jedną z podstawowych powszechnych struktur danych, dlatego jej implementację można znaleźć w każdym nowoczesnym języku programowania. To samo z tablicą asocjacyjną. Oto jej definicja z Wikipedii: Tablica asocjacyjna to abstrakcyjny typ danych (interfejs do magazynu danych), który umożliwia przechowywanie par w postaci „(klucz, wartość)” i obsługuje operacje dodawania pary, a także wyszukiwanie i usuwanie pary według klucza. Nic Ci nie przypomina? :) Dokładnie, dla nas Javaistów tablica asocjacyjna jest interfejsemMap. Ale ta struktura danych jest zaimplementowana także w innych językach! Na przykład programiści C# znają go pod nazwą „Słownik”. W języku Ruby jest to zaimplementowane w klasie o nazwie „Hash”. Ogólnie rzecz biorąc, z grubsza rozumiesz, co to oznacza: struktura danych jest rzeczą wspólną dla całego programowania, która jest implementowana inaczej w każdym konkretnym języku. Dzisiaj przestudiujemy dwie takie struktury i zobaczymy, jak są zaimplementowane w Javie – stos i kolejka.

Stos w Javie

Stos jest znaną strukturą danych. Jest to bardzo proste i całkiem sporo obiektów z naszego codziennego życia jest „realizowanych” w postaci stosu. Wyobraź sobie prostą sytuację: mieszkasz w hotelu i w ciągu dnia otrzymujesz korespondencję służbową. Ponieważ nie było Cię w tym czasie w pokoju, pracownik hotelu po prostu kładł przychodzące listy na Twoim stole. Najpierw położył na stole pierwszy list. Potem przyszedł drugi i położył go na pierwszym. Trzeci otrzymany list położył na drugim, a czwarty na trzecim. A teraz odpowiedz na proste pytanie: jaki list przeczytasz jako pierwszy , kiedy wejdziesz do swojego pokoju i zobaczysz stos na stole? Zgadza się, przeczytasz górną literę. To znaczy ten, który przyszedł jako ostatni na czas . Dokładnie tak działa stos. Ta zasada działania nazywa się LIFO – „ostatnie weszło, pierwsze wyszło” („ostatnie weszło, pierwsze wyszło”). Do czego może przydać się stos? Na przykład tworzysz jakąś grę karcianą w Javie. Na stole leży talia kart. Zagrane karty są odrzucane. Możesz wdrożyć zarówno talię, jak i odrzucić, używając dwóch stosów. Gracze dobierają karty z wierzchu talii – na tej samej zasadzie, co w przypadku liter. Kiedy gracze odrzucają karty, nowe karty są umieszczane na starych. Oto jak wyglądałaby pierwsza wersja naszej gry, zaimplementowana przy użyciu stosu:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Jak powiedzieliśmy wcześniej, mamy dwa stosy: talię i stos odrzuconych kart. Struktura danych stosu jest zaimplementowana w Javie w formacie java.util.Stack. W naszej grze karcianej istnieją 3 metody opisujące działania graczy:

• weź kartę z talii (metoda getCardFromDeck());
• odrzucić kartę (metoda discard());
• spójrz na górną kartę (metoda lookTopCard()). Powiedzmy, że będzie to bonusowa mechanika „Inteligencja”, która pozwoli graczowi dowiedzieć się, która karta wejdzie do gry jako następna.

Wewnątrz naszych metod metody klasowe nazywane są Stack:

• push()— dodaje element na górę stosu. Kiedy odrzucamy kartę, umieszcza się ją na wierzchu wcześniej odrzuconych kart;
• pop()— usuwa wierzchni element ze stosu i zwraca go. Ta metoda jest idealna do wdrożenia mechaniki „gracz dobiera kartę”.
• peek()- zwraca górny element stosu, ale nie usuwa go ze stosu

Zobaczmy jak będzie działać nasza gra:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Dlatego dodaliśmy pięć kart do naszej talii. Pierwszy gracz wziął 3 z nich. Jakie dostał karty? Wyjście konsoli:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Zwróć uwagę na kolejność, w jakiej karty zostały wysłane do konsoli. Karta „Edwin Van Cleiff” trafiła do talii jako ostatnia (piąta z rzędu) i to właśnie tę kartę gracz wziął jako pierwszy. „Michhlaus” uderzył w talię przedostatni, a jego gracz zajął ją jako drugi. „Sylvanas” uderzyła w talię jako trzecia od końca i trafiła do trzeciego gracza. Następnie gracz odrzuca swoje karty. Najpierw porzuca Edwina, potem Millhouse'a, a na koniec Sylvanas. Następnie po kolei wyprowadzamy na konsolę karty znajdujące się w naszym odrzucie: Wyprowadzamy na konsolę:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

I znowu widzimy, jak działa stos! Odrzucona w naszej grze to także stos (podobnie jak talia). Jako pierwszy odpadł „Edwin Van Clyffe”. Drugim, który został upuszczony, był „Millhouse Manastorm” – i leżał na Edwinie w odrzucie. Następnie Sylvanas została odrzucona i ta karta leżała na wierzchu Millhouse. Jak widać, działanie stosu nie jest skomplikowane. Znajomość tej struktury danych jest jednak konieczna – często jest ona pytana w wywiadach i często na jej podstawie budowane są bardziej złożone struktury danych.

Kolejka

Kolejka (lub po angielsku „Kolejka”) to kolejna popularna struktura danych. Podobnie jak stos, jest zaimplementowany w wielu językach programowania, w tym w Javie. Jaka jest różnica między kolejką a stosem? Jej kolejka nie opiera się na LIFO, ale na innej zasadzie – FIFO („pierwsze weszło – pierwsze wyszło”, „pierwsze weszło – pierwsze wyszło”) . Łatwo to zrozumieć, biorąc za przykład… a przynajmniej zwykłą, prawdziwą kolejkę z prawdziwego życia! Na przykład kolejka do sklepu. Jeżeli w kolejce będzie pięć osób, do sklepu wejdzie pierwsza osoba z kolejki . Jeżeli jeszcze jedna osoba (oprócz pięciu w kolejce) chce coś kupić i staje w kolejce, to wchodzi do sklepu jako ostatnia , czyli szósta. Podczas pracy z kolejką nowe elementy dodawane są na końcu, a jeśli chcemy uzyskać element, zostanie on pobrany od początku. To podstawowa zasada jego działania, o której trzeba pamiętać.Zasada kolejki jest bardzo łatwa do zrozumienia intuicyjnie, gdyż często spotyka się ją w prawdziwym życiu. Warto osobno zauważyć, że w Javie kolejka jest reprezentowana nie przez klasę, ale przez interfejs - . Ale jednocześnie kolejka w Javie jest interfejsem, który ma wiele implementacji. Jeśli spojrzymy na dokumentację Oracle, zobaczymy, że z kolejki dziedziczone są 4 różne interfejsy i niezwykle imponująca lista klas: Queue

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Cóż za duża lista! Ale oczywiście nie musisz teraz zapamiętywać wszystkich tych klas i interfejsów - głowa może eksplodować :) Przyjrzymy się tylko kilku najważniejszym i najciekawszym punktom. Najpierw zwróćmy uwagę na jeden z czterech „podinterfejsów” kolejki - Deque. Co w tym takiego specjalnego? Deque- To jest kolejka dwukierunkowa. Rozszerza funkcjonalność zwykłej kolejki, umożliwiając dodawanie elementów na oba końce (początek i koniec kolejki) oraz pobieranie elementów z obu końców kolejki. Deque jest szeroko stosowany w rozwoju. Zwróć uwagę na listę klas kolejek, którą podaliśmy powyżej. Lista jest dość długa, ale czy jest tam coś dla nas znajomego?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, więc nasz stary przyjaciel tu jest LinkedList! Oznacza to, że implementuje interfejs Queue? Ale jak może stać w kolejce? W końcu LinkedListjest to połączona lista! To prawda, ale to nie powstrzymuje go od bycia kolejką :) Oto lista wszystkich zaimplementowanych interfejsów:

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Jak widać LinkedListimplementuje interfejs Deque- kolejkę dwukierunkową. Dlaczego jest to konieczne? Dzięki temu możemy uzyskać elementy zarówno z początku, jak i z końca LinkedList. A także - dodaj elementy zarówno na początku, jak i na końcu. Oto metody odziedziczone LinkedListz interfejsu Deque:

• peekFirst()— zwraca (ale nie usuwa z kolejki) pierwszy element.
• peekLast()— zwraca (ale nie usuwa z kolejki) ostatni element.
• pollFirst()- zwraca pierwszy element z kolejki i usuwa go.
• pollLast()- zwraca ostatni element z kolejki i usuwa go.
• addFirst()— dodaje nowy element na początek kolejki.
• addLast()— dodaje element na koniec kolejki.

Jak widać, LinkedListw pełni realizuje funkcjonalność kolejki dwukierunkowej! A jeśli w programie będzie potrzebna taka funkcjonalność, to będziecie wiedzieć, że można z niej skorzystać :) I nasz dzisiejszy wykład dobiega końca. Na koniec podam kilka linków do dalszej lektury. Na początek zwróć uwagę na artykuł poświęcony PriorityQueue – „kolejka priorytetowa”. Jest to jedna z najciekawszych i najbardziej przydatnych implementacji Queue. Przykładowo, jeśli w Twoim sklepie jest 50 osób w kolejce, a 7 z nich to klienci VIP, PriorityQueueto pozwoli Ci to obsłużyć ich w pierwszej kolejności! Bardzo przydatna rzecz, prawda? :) Po drugie, nie byłoby zbyteczne przypomnienie jeszcze raz książki Roberta Laforeta „Struktury danych i algorytmy w Javie” . Czytając książkę, nie tylko poznasz wiele struktur danych (w tym stos i kolejkę), ale wiele z nich zaimplementujesz samodzielnie! Załóżmy na przykład, że Java nie ma klasy Stack. Co byś zrobił, gdybyś potrzebował takiej struktury danych dla swojego programu? Oczywiście musiałbym to napisać sam. Czytając książkę Laforeta, często tak właśnie zrobisz. Dzięki temu Twoje zrozumienie struktur danych będzie znacznie szersze niż tylko studiowanie teorii :) Na dziś skończyliśmy z teorią, ale teoria bez praktyki jest niczym! Problemy same się nie rozwiążą, więc najwyższy czas się z nimi uporać! :)