Implamentacja: Stos, kolejka i lista w Java Collections Framework - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

Stos, kolejka i lista w Java Collections Framework

Dla zainteresowanych

Java Collections Framework to zestaw interfejsów oraz implementacji przeznaczonych do tworzenia omawianych wyżej struktur dynamicznych. Interfejsy w języku Java definiują abstrakcyjne metody i pola, które muszą zostać zaimplementowane w konkretnej klasie służącej do tworzenia danej kolekcji. Omawiane w materiale struktury można tworzyć za pomocą różnych interfejsów i klas.

Interfejs `Deque` i klasa `ArrayDeque`

Java Collections Framework definiuje klasę Stack będącą implementacją struktury stosu. Jednak ze względu na jej ograniczenia, m.in. dziedziczenie z niewspieranej już klasy Vector, zaleca się używanie interfejsu Deque i wybranej jego implementacji. Nazwa interfejsu Deque jest skrótem od wyrażenia double ended queue, które oznacza kolejkę dwukierunkową. Jedną z implementacji tego interfejsu jest klasa ArrayDeque, wykorzystująca dynamiczne tablice. Klasa ta implementuje m.in. następujące metody interfejsu:

push() – zadaniem metody jest umieszczenie elementu na stosie;
pop() – metoda usuwa pierwszy element kolejki;
getFirst() – metoda zwraca bez usuwania pierwszy element kolekcji;
peek() – zadaniem metody jest pobranie wierzchołka stosu;
isEmpty() – metoda sprawdza, czy stos jest pusty;
size() – zadaniem metody jest zwrócenie liczby elementów na stosie.

Przykład 1

Przykładowy program:

Linia 1. import java kropka util kropka Deque średnik. Linia 2. import java kropka util kropka ArrayDeque średnik. Linia 4. public class StosJF otwórz nawias klamrowy. Linia 5. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. Deque otwórz nawias ostrokątny Integer zamknij nawias ostrokątny stos znak równości new ArrayDeque otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 7. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny System kropka out kropka println otwórz nawias okrągły cudzysłów Odkładam liczby 5 przecinek 4 przecinek 6 cudzysłów zamknij nawias okrągły średnik. Linia 8. stos kropka push otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 9. stos kropka push otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 10. stos kropka push otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 11. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły stos kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 12. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzchołek dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły stos kropka getFirst otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 14. System kropka out kropka println otwórz nawias okrągły cudzysłów Zdejmuję wierzchołek dwukropek cudzysłów plus stos kropka pop otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 15. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły stos kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 16. System kropka out kropka println otwórz nawias okrągły cudzysłów Wierzchołek dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły stos kropka getFirst otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 18. System kropka out kropka print otwórz nawias okrągły cudzysłów Stos zawiera dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 19. while otwórz nawias okrągły wykrzyknik stos kropka isEmpty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. System kropka out kropka print otwórz nawias okrągły stos kropka peek otwórz nawias okrągły zamknij nawias okrągły plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 21. stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 22. zamknij nawias klamrowy. Linia 23. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 25. System kropka out kropka println otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły stos kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 26. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 28. zamknij nawias klamrowy.

import java.util.Deque;
import java.util.ArrayDeque;

public class StosJF {
public static void main(String[] args) {
Deque<Integer> stos = new ArrayDeque<>();
        System.out.println("Odkładam liczby 5, 4, 6");
        stos.push(5);
        stos.push(4);
        stos.push(6);
        System.out.print("Rozmiar: " + Integer.toString(stos.size()));
        System.out.println(" Wierzchołek: " + Integer.toString(stos.getFirst()));
    
        System.out.println("Zdejmuję wierzchołek: " + stos.pop());
        System.out.print("Rozmiar: " + Integer.toString(stos.size()));
        System.out.println(" Wierzchołek: " + Integer.toString(stos.getFirst()));
    
        System.out.print("Stos zawiera: ");
        while (!stos.isEmpty()) {
            System.out.print(stos.peek() + " ");
            stos.pop();
        }
        System.out.println();
    
        System.out.println("Rozmiar: " + Integer.toString(stos.size()));
    }

}

Na początku tworzymy obiekt stos do przechowywania wartości typu Integer (liczby całkowite). Następnie odkładamy na stosie trzy liczby za pomocą metody push, która dodaje je na początku listy. Następnie wypisujemy rozmiar (size()) i wierzchołek (getFirst()) stosu.

W kolejnych instrukcjach zdejmujemy wierzchołek ze stosu (pop()), wypisujemy rozmiar i nowy wierzchołek.

Na końcu przy użyciu pętli wykonującej się, dopóki stos nie jest pusty (isEmpty()), wypisujemy kolejny wierzchołek (peek()) i zdejmujemy go. Na końcu wypisujemy jeszcze raz aktualny rozmiar stosu.

Wynik działania programu:

Odkładam liczby 5, 4, 6
Rozmiar: 3 Wierzchołek: 6
Zdejmuję wierzchołek.
Rozmiar: 2 Wierzchołek: 4
Stos zawiera: 4 5
Rozmiar: 0

Interfejs `Queue` i klasa `LinkedList`

Interfejs Queue definiuje metody dla typowych kolejek typu FIFO, kolejek priorytetowych oraz kolekcji typu LIFO (typu stos). Jedną z implementacji interfejsu dostarcza klasa LinkedList. Do dyspozycji mamy m.in. następujące metody:

add() – zadaniem metody jest dodawanie elementu na końcu listy;
remove() – metoda usuwa pierwszy element listy;
peek() – metoda zwraca pierwszy element listy bez usuwania go;
size() – zadaniem metody jest zwrócenie liczby elementów listy.

Ważne!

Jeżeli do deklarowania typu struktury wykorzystujemy interfejs, ogranicza on dostępne metody, nawet jeżeli implementująca go klasa zawiera ich więcej. Na przykład klasa LinkedList definiuje ponad 30 metod do wykonywania różnych operacji na liście dwukierunkowej, ale użycie interfejsu Queue umożliwia nam wykorzystanie tylko kilku z nich przeznaczonych do obsługi kolejki.

Przykład 2

Przykładowy program:

Linia 1. import java kropka util kropka Queue średnik. Linia 2. import java kropka util kropka LinkedList średnik. Linia 4. public class KolejkaJF otwórz nawias klamrowy. Linia 5. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. Queue otwórz nawias ostrokątny Integer zamknij nawias ostrokątny kolejka znak równości new LinkedList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 7. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaję liczby 5 przecinek 4 przecinek 6 cudzysłów zamknij nawias okrągły średnik. Linia 8. kolejka kropka add otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 9. kolejka kropka add otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 10. kolejka kropka add otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 11. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły kolejka kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 12. System kropka out kropka println otwórz nawias okrągły cudzysłów Pierwszy dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły kolejka kropka peek otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 14. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam pierwszy kropka cudzysłów zamknij nawias okrągły średnik. Linia 15. kolejka kropka remove otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 16. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły kolejka kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 17. System kropka out kropka println otwórz nawias okrągły cudzysłów Pierwszy dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły kolejka kropka peek otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 19. System kropka out kropka print otwórz nawias okrągły cudzysłów kolejka zawiera dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 20. while otwórz nawias okrągły kolejka kropka size otwórz nawias okrągły zamknij nawias okrągły ampersant gt średnik 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. System kropka out kropka print otwórz nawias okrągły kolejka kropka peek otwórz nawias okrągły zamknij nawias okrągły plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 22. kolejka kropka remove otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 24. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 26. System kropka out kropka println otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły kolejka kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 29. zamknij nawias klamrowy.

import java.util.Queue;
import java.util.LinkedList;

public class KolejkaJF {
public static void main(String[] args) {
Queue<Integer> kolejka = new LinkedList<>();
        System.out.println("Dodaję liczby 5, 4, 6");
        kolejka.add(5);
        kolejka.add(4);
        kolejka.add(6);
        System.out.print("Rozmiar: " + Integer.toString(kolejka.size()));
        System.out.println(" Pierwszy: " + Integer.toString(kolejka.peek()));
    
        System.out.println("Usuwam pierwszy.");
        kolejka.remove();
        System.out.print("Rozmiar: " + Integer.toString(kolejka.size()));
        System.out.println(" Pierwszy: " + Integer.toString(kolejka.peek()));
    
        System.out.print("kolejka zawiera: ");
        while (kolejka.size() &gt; 0) {
            System.out.print(kolejka.peek() + " ");
            kolejka.remove();
        }
        System.out.println();
    
        System.out.println("Rozmiar: " + Integer.toString(kolejka.size()));
    }

}

Na początku tworzymy obiekt kolejka, który posłuży do przechowywania wartości typu Integer (liczby całkowite). Następnie dodajemy do kolejki trzy liczby (add) po czym wypisujemy rozmiar (size()) oraz pierwszy (peek()) element.

Następnie usuwamy pierwszy element (remove()) oraz wypisujemy rozmiar oraz pierwszy element kolejki.

Na końcu przy użyciu pętli wykonującej się, dopóki kolejka nie jest pusta (size() > 0), wypisujemy kolejne pierwsze elementy i usuwamy je. Na końcu wypisujemy jeszcze raz aktualny rozmiar kolejki.

Wynik działania programu:

Dodaję liczby 5, 4, 6
Rozmiar: 3 Pierwszy: 5
Usuwam pierwszy.
Rozmiar: 2 Pierwszy: 4
kolejka zawiera: 4 6
Rozmiar: 0

Implementacja listy

Klasa LinkedList

Stos, kolejka i lista w Java Collections Framework

Interfejs `Deque` i klasa `ArrayDeque`

Interfejs `Queue` i klasa `LinkedList`

Implementacja listy

Klasa LinkedList

I_R_W13A_M03_JAVA Zaawansowane struktury danych

Stos, kolejka i lista w Java Collections Framework

Interfejs Deque i klasa ArrayDeque

Interfejs Queue i klasa LinkedList

Interfejs `Deque` i klasa `ArrayDeque`

Interfejs `Queue` i klasa `LinkedList`