Struktury danych: stos i kolejka

Cześć! Dziś omówimy coś, co jest bardzo ważne dla każdego programisty: struktury danych. Wikipedia mówi: "Struktura danych to format organizacji, zarządzania i przechowywania danych, który umożliwia efektywny dostęp i modyfikację. Mówiąc dokładniej, struktura danych to zbiór wartości danych, relacji między nimi oraz funkcji lub operacji, które można zastosować do danych." Definicja jest nieco zagmatwana ale istota jest jasna. Struktura danych to rodzaj repozytorium, w którym przechowujemy dane do wykorzystania w przyszłości. W programowaniu istnieje wiele różnorodnych struktur danych. Przy rozwiązywaniu konkretnych problemów często najważniejszy jest wybór odpowiedniej dla problemu struktury danych. I wiele z nich już znasz! Wiesz już na przykład o tablicach. Znasz również Map (ta struktura danych może być również określana jako "słownik" lub "tablica asocjacyjna"). Bardzo ważne jest, aby zrozumieć, że struktury danych nie są powiązane z żadnym konkretnym językiem. Są to abstrakcyjne "projekty", których każdy język programowania używa do tworzenia własnych klas lub implementacji określonej struktury. Na przykład jedną z najbardziej znanych struktur danych jest lista połączona. Możesz wejść na Wikipedię i poczytać o tym, jak to działa oraz jakie ma wady i zalety. Definicja może wydać Ci się znajoma :) "Lista połączona to liniowy zbiór elementów, których kolejność nie jest określona przez ich fizyczne rozmieszczenie w pamięci. Zamiast tego każdy element wskazuje na następny." To opisuje naszą ukochaną klasę LinkedList, prawda? Tak i właśnie o to chodzi :) W Javie struktura danych "lista" jest implementowana przez klasę LinkedList. Ale inne języki również implementują listy połączone! W Pythonie ta struktura danych nosi nazwę "llist". W Scali nazywa się to "LinkedList", tak jak w Javie. Lista połączona jest jedną z podstawowych struktur danych, więc przekonasz się, że jest zaimplementowana w każdym nowoczesnym języku programowania. To samo dotyczy tablic asocjacyjnych. Oto definicja z Wikipedii: "Tablica asocjacyjna, tablica skojarzeniowa, mapa, słownik – powszechnie stosowany w informatyce abstrakcyjny typ danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza." Przypomina Ci to coś? :) Tak. Dla nas, programistów Java, tablica asocjacyjna jest interfejsem Map. Ale ta struktura danych jest zaimplementowana również w innych językach! Na przykład programiści C# znają ją pod nazwą "Dictionary". A w Ruby jest zaimplementowana w klasie o nazwie "Hash". Zapewne już rozumiesz: struktury danych to uniwersalne koncepcje w programowaniu, a każdy język programowania implementuje je na swój własny sposób. Dziś poznamy dwie z tych struktur — stos i kolejkę — i zobaczymy, jak są one zaimplementowane w Javie.

Stosy w Javie

Stos to popularna struktura danych. Jest ona bardzo prosta. Wiele elementów z naszego codziennego życia ma "implementację" w formie stosu. Wyobraź sobie taką prostą sytuację: zatrzymujesz się w hotelu i w ciągu dnia otrzymujesz kilka listów biznesowych. Nie było cię wtedy w pokoju, więc recepcjonista po prostu położył przychodzące listy na twoim biurku. Najpierw położył pierwszy list na biurku. Potem przyszedł drugi list i położył go na pierwszym. Później położył trzeci list na drugim, a następnie czwarty na trzecim. A teraz odpowiedz na proste pytanie: który list przeczytasz jako pierwszy, kiedy wrócisz do pokoju i zobaczysz stos na stole? Jasne, przeczytasz list leżący na samej górze. To znaczy ten, który przyszedł jako ostatni. Dokładnie tak działa stos. Zasada ta nazywa się LIFO ("last in first out"), czyli "ostatnie weszło, pierwsze wyszło". Do czego służą stosy? Załóżmy, że tworzysz w Javie jakąś grę karcianą. Talia kart leży na stole. Zagrane karty są odrzucane. Możesz użyć dwóch stosów, aby zaimplementować zarówno talię dobierania, jak i stos kart odrzuconych. Gracze biorą swoje karty z wierzchu talii, kierując się tą samą zasadą, co w przypadku listów biznesowych. Kiedy gracze odkładają karty na stos kart odrzuconych, nowo odrzucone karty są umieszczane na starych. Oto nasza pierwsza próba 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 {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

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

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

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Jak powiedzieliśmy wcześniej, mamy dwa stosy: talię dobierania i stos kart odrzuconych. W Javie struktura danych stos jest implementowana przez klasę java.util.Stack. Nasza gra karciana ma 3 metody, które opisują działania graczy:

• weź kartę z talii (metoda getCardFromDeck())
• odrzuć kartę (metoda discard())
• spójrz na górną kartę (metoda lookAtTopCard()). Powiedzmy, że jest to premia "Inteligencja", która pozwala graczowi dowiedzieć się, jaka karta pojawi się jako kolejna w grze.

Wewnątrz naszych metod wywołujemy następujące metody klasy Stack:

• push() — dodaje element na wierzchu stosu. Kiedy wysyłamy kartę na stos kart odrzuconych, trafia ona na wierzch stosu
• pop() — usuwa ze stosu element umieszczony na wierzchu i zwraca go. Ta metoda jest idealna do realizacji akcji, w których 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) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Dodaliśmy do naszej talii pięć kart. Pierwszy gracz wziął 3 z nich. Jakie karty dostała? Wyświetlone zostanie:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Zwróć uwagę na kolejność wyświetlania kart w konsoli. Karta "Edwin VanCleef" trafiła do talii jako ostatnia (była to piąta karta) i była to karta, którą gracz dobrał jako pierwszą. "Mełko" był przedostatnią kartą w talii, a gracz wyciągnął ją jako drugą. "Sylwana" trafiła do talii jako trzecia od góry i była to trzecia karta dobrana przez gracza. Następnie gracz odrzuca karty. Najpierw odrzuca Edwina, następnie Mełka, a następnie Sylwanę. Następnie kolejno pokazujemy karty z naszego stosu kart odrzuconych: Wyświetlone zostanie:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Po raz kolejny widzimy, jak działa stos! W naszej grze stos kart odrzuconych jest również stosem (podobnie jak talia do dobierania). "Edwin VanCleef" został odrzucony jako pierwszy. Drugą odrzuconą kartą był Mełko Gromiłło, który został umieszczony nad Edwinem na stosie kart odrzuconych. Następnie odrzucono Sylwanę i położono tę kartę na Mełku. Jak widać, w stosie nie ma nic skomplikowanego. Warto jednak znać tę strukturę danych — pytania o nią często pojawiają się podczas rozmów kwalifikacyjnych i jest ona podstawą do budowania bardziej złożonych struktur danych.

Kolejka w Javie

Kolejka to kolejna powszechna struktura danych. Oprócz stosów wiele języków programowania, w tym Java, implementuje również strukturę danych kolejka. Na czym polega różnica pomiędzy kolejką a stosem? Kolejka nie opiera się na zasadzie LIFO, ale na zasadzie FIFO ("first in, first out") czyli "pierwsze weszło, pierwsze wyszło". Zasada ta jest łatwa do zrozumienia, jeżeli porównamy ją ze zwykłą kolejką w prawdziwym życiu! Na przykład kolejka w sklepie spożywczym. Jeśli w kolejce jest pięć osób, jako pierwszy zostanie obsłużony ten, kto wszedł do kolejki jako pierwszy. Jeśli kolejna osoba (oprócz pięciu już ustawionych w kolejce) chce coś kupić i ustawia się w kolejce, to zostanie obsłużona ostatnia, czyli szósta. Podczas pracy z kolejką nowe elementy są dodawane na końcu (z tyłu, ogon), a jeśli chcesz pobrać element, zostanie on pobrany z początku (z przodu, głowa). Jest to główna zasada, o której musisz pamiętać, jeśli chodzi o działanie kolejki. Obsługa kolejki jest bardzo intuicyjna, ponieważ często spotykamy się z kolejkami w prawdziwym życiu. Warto osobno zaznaczyć, że w Javie kolejka nie jest reprezentowana przez klasę, ale przez interfejs: Queue. Co więcej, w Javie istnieje wiele implementacji interfejsu queue. Jeśli spojrzymy na dokumentację Oracle, zobaczymy, że interfejs Queue dziedziczą 4 różne interfejsy, a także imponująca lista klas:

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

Co za lista! Ale oczywiście nie musisz od razu uczyć się na pamięć tych wszystkich klas i interfejsów — głowa może eksplodować :) Rozważymy tylko kilka najważniejszych i najciekawszych punktów. Najpierw zwróćmy uwagę na jeden z czterech "podinterfejsów" Queue: Deque. Co czyni go tak wyjątkowym? Deque to kolejka dwustronna. Rozszerza funkcjonalność zwykłej kolejki, umożliwiając dodawanie elementów na obu końcach (na początku i na końcu) oraz pobieranie elementów z obu końców kolejki. Kolejki dwustronne są szeroko stosowane w tworzeniu oprogramowania. Zwróć uwagę na listę klas kolejek, którą podaliśmy powyżej. Lista jest dość długa, ale czy zawiera coś znajomego?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Oto nasz stary przyjaciel LinkedList! Więc implementuje interfejs Queue? Ale jak to może być kolejka? W końcu LinkedList to lista połączona! To prawda, ale to nie przeszkadza w byciu kolejką :) Oto lista wszystkich interfejsów, które implementuje:

All implemented interfaces:

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

Jak widać, LinkedList implementuje interfejs Deque (czyli kolejkę dwustronną). Do czego jest to potrzebne? To pozwala nam pobierać elementy z początku i końca LinkedList. Pozwala nam również dodawać elementy na początku i na końcu. Oto metody, które LinkedList uzyskuje z interfejsu Deque:

• peekFirst() — zwraca pierwszy element (ale nie usuwa go z kolejki).
• peekLast() — zwraca ostatni element (ale nie usuwa go z kolejki).
• pollFirst() — zwraca pierwszy element z kolejki i usuwa go.
• pollLast() — zwraca ostatni element z kolejki i usuwa go.
• addFirst() — dodaje nowy element na początku kolejki.
• addLast() — dodaje element na końcu kolejki.

Jak widać, LinkedList w pełni implementuje funkcjonalność kolejki dwustronnej. A jeśli potrzebujesz takiej funkcjonalności w swoim programie, wiesz gdzie ją znaleźć :) Dzisiejsza lekcja dobiega końca. Podsumowując, dam ci kilka linków do dodatkowej lektury. Najpierw zwróć uwagę na ten artykuł o PriorityQueue. To jedna z najciekawszych i najbardziej przydatnych implementacji Queue. Załóżmy na przykład, że w Twoim sklepie czeka w kolejce 50 osób, a 7 z nich to klienci VIP. PriorityQueue pozwoli ci obsłużyć ich jako pierwszych! Bardzo przydatna rzecz, prawda? :) Po drugie, nie zaszkodzi jeszcze raz wspomnieć o książce Roberta Lafore "Java. Algorytmy i struktury danych". Czytając tę książkę, nie tylko poznasz wiele struktur danych (w tym stos i kolejkę), ale także własnoręcznie zaimplementujesz wiele z nich! Na przykład, co by było, gdyby Java nie miała klasy Stack? Co byś zrobiła/zrobił, potrzebując takiej struktury danych do swojego programu? Oczywiście należałoby to napisać. Czytając książkę Lafore'a często będziesz właśnie to robić. W efekcie twoje zrozumienie struktur danych będzie znacznie głębsze niż to, co uzyskasz z prostego przestudiowania teorii :) Kończymy z teorią na dziś, ale teoria bez praktyki to nic! Zadania same się nie rozwiążą, więc pora się nimi zająć! :)