Implementacja stosu - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

Najprostszymi dynamicznymi strukturami, które poznaliśmy, są stos i kolejka. Obydwie implementować można za pomocą różnych mechanizmów. Jedno z najprostszych rozwiązań, które służy zazwyczaj do wyjaśnienia działania tych struktur, to użycie statycznej lub dynamicznej tablicy. Jednak nie jest to rozwiązanie w pełni dynamiczne, ponieważ użycie tablic wymaga podania maksymalnej liczby przechowywanych w strukturze elementów. Aby uzyskać w pełni dynamiczne struktury stosu i kolejki, wykorzystuje się listy.

Stos

Przypomnijmy, że stos to liniowa struktura typu LIFO (ang. Last‑In, First‑Out – ostatni na wejściu, pierwszy na wyjściu), która obsługuje dwie podstawowe operacje, tj. odkładanie i zdejmowanie danych. Dodatkowe działania, które wykonuje się na stosie, to odczytywanie wierzchołka stosu, czyli ostatniego odłożonego elementu, bez usuwania go, oraz ewentualnie sprawdzanie rozmiaru stosu, czyli liczby odłożonych elementów.

Biorąc podane warunki pod uwagę, do implementacji stosu wystarczy jednokierunkowa lista niecykliczna. Elementami tej listy będą węzły zawierające dane, np. liczby, oraz – w przypadku listy jednokierunkowej – referencja na element następny. Do zdefiniowania węzła użyjemy klasy zawierającej dwa pola oraz konstruktor:

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }
}

Stworzenie nowego węzła i przypisanie wartości do jego składowych umożliwia instrukcja:

Wezel nowy = new Wezel(liczba);

Stos zaimplementujemy również jako klasę, której atrybutem będzie referencja na wierzchołek stosu o nazwie wierzcholek. Klasa będzie zawierała również definicję konstruktora.

class Stos {
    Wezel wierzcholek;
    public Stos() {
        wierzcholek = null;
    }
    
    // Miejsce na dodanie metod

}

W konstruktorze Stos() inicjalizujemy pole wierzcholek referencją pustą.

Do klasy Stos() dodamy teraz metody wykonujące charakterystyczne dla stosu operacje.

Zaczniemy od metody czyPusty(), która będzie zwracała wartość true (prawda), jeżeli stos będzie pusty, czyli w sytuacji, kiedy pole wierzcholek będzie referencją pustą. W przeciwnym razie metoda zwróci wartość false (fałsz).

public boolean czyPusty() {
    if (wierzcholek == null) {
        System.out.println("Stos pusty!");
    }
    return (wierzcholek == null);
}

W celu zachowania poprawności działania struktury LIFO, funkcja odloz() będzie dodawała elementy na początku listy i odpowiednio funkcja zdjemij() będzie usuwała elementy również z początku listy.

Zacznijmy od metody odloz():

public void odloz(int liczba) {
    System.out.println("Odkładam " + String.valueOf(liczba));
    Wezel nowy = new Wezel(liczba);
    nowy.nastepny = wierzcholek;
    wierzcholek = nowy;

}

W funkcji odloz() tworzymy nowy węzeł i zapisujemy w nim wartość zmiennej liczba przekazaną jako argument. Następnie pole nastepny nowego elementu ustawiamy na dotychczasowy wierzcholek, w ten sposób dodajemy element na początku listy. Na koniec aktualizujemy pole wierzcholek, tak aby wskazywało na nowo dodany element.

W metodzie pomijamy sprawdzenie ewentualnego błędu przepełnienia stosu, który ze względu na użycie listy jest mało prawdopodobny.

Usuwanie pierwszego elementu jest możliwe dzięki referencji wierzcholek:

public int zdejmij() {
    if (czyPusty()) return Integer.MIN_VALUE;
    Wezel pomocniczy = wierzcholek;
    int liczba = pomocniczy.liczba;
    wierzcholek = wierzcholek.nastepny;
    System.out.println("Zdejmuję " + Integer.toString(liczba));
    
    return liczba;

}

Jeżeli stos jest pusty, tzn. zachodzi błąd niedopełnienia stosu, zwracamy minimalną wartość zdefiniowaną dla typu całkowitego w stałej MIN_VALUE.

W przeciwnym razie dotychczasowy pierwszy element oraz zapisaną w nim wartość zapamiętujemy w zmiennych pomocniczych. Następnie ustawiamy wierzchołek na drugi element listy, dotychczasowy pierwszy usuwamy, a zapamiętaną wartość zwracamy.

Metoda pobierzWierzcholek() ma tylko jedno zadanie: jeżeli stos nie jest pusty, zwraca wartość zapisaną w pierwszym, czyli ostatnim dodanym, elemencie listy:

public int pobierzWierzcholek() {
    if (czyPusty()) return Integer.MIN_VALUE;
    return wierzcholek.liczba;
}

Metoda wypisz() posłuży do wypisania wartości odłożonych na stosie, czyli zapisanych w kolejnych węzłach listy:

public void wypisz() {
    if (czyPusty()) return;
    System.out.print("Stos zawiera: ");
    Wezel pomocniczy = wierzcholek;
    while (pomocniczy != null) {
        System.out.print(pomocniczy.liczba + " ");
        pomocniczy = pomocniczy.nastepny;
    }
    System.out.println();

}

Do wypisania wartości używamy pętli przechodzącej po wszystkich elementach stosu zapisywanych w zmiennej pomocniczy, którą ustawiamy na wierzchołek, a następnie wewnątrz pętli przesuwamy na kolejne węzły wskazywane przez pole nastepny. Pętla będzie działać dopóki nie dojdziemy do ostatniego węzła, którego referencja nastepny będzie pusta.

Do sprawdzenia działania stosu możemy użyć poniższego kodu:

public class StosLista {
    public static void main(String[] args) {
        Stos stos = new Stos();
        stos.odloz(1);
        stos.odloz(2);
        stos.odloz(3);
        stos.wypisz();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
    }
}

Ćwiczenie 1

Na podstawie całego omówionego powyżej kodu przygotuj program ilustrujący działanie stosu. Przeanalizuj podaną wyżej funkcję główną i odpowiedz, jaki będzie ostatni wypisany przez program komunikat. Uruchom program i sprawdź poprawność swojej odpowiedzi.

Wykorzystaj omówiony kod i przygotuj program pozwalający sprawdzić działanie kolejki. Dodaj do kolejki trzy liczby, wypisz kolejkę, a następnie cztery raz wywołaj metodę usuwającą.

RJl1aILncO7Yk

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. this kropka liczba znak równości liczba średnik. Linia 6. this kropka nastepny znak równości null średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy. Linia 10. class Stos otwórz nawias klamrowy. Linia 11. Wezel wierzcholek średnik. Linia 12. 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 public Stos otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. wierzcholek znak równości null średnik. Linia 14. zamknij nawias klamrowy. Linia 16. public boolean czyPusty otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. if otwórz nawias okrągły wierzcholek znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. System kropka out kropka println otwórz nawias okrągły cudzysłów Stos pusty wykrzyknik cudzysłów zamknij nawias okrągły średnik. Linia 19. zamknij nawias klamrowy. Linia 20. return otwórz nawias okrągły wierzcholek znak równości znak równości null zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 23. public void odloz otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. System kropka out kropka println otwórz nawias okrągły cudzysłów Odkładam cudzysłów plus String kropka valueOf otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 26. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 27. nowy kropka nastepny znak równości wierzcholek średnik. Linia 28. wierzcholek znak równości nowy średnik. Linia 29. zamknij nawias klamrowy. Linia 30. public int zdejmij otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return Integer kropka MIN podkreślnik VALUE średnik. Linia 32. Wezel pomocniczy znak równości wierzcholek średnik. Linia 33. int liczba znak równości pomocniczy kropka liczba średnik. Linia 34. wierzcholek znak równości wierzcholek kropka nastepny średnik. Linia 36. System kropka out kropka println otwórz nawias okrągły cudzysłów Zdejmuję cudzysłów plus Integer kropka toString otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 38. return liczba średnik. Linia 39. zamknij nawias klamrowy. Linia 41. public int pobierzWierzcholek otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return Integer kropka MIN podkreślnik VALUE średnik. Linia 43. return wierzcholek kropka liczba średnik. Linia 44. zamknij nawias klamrowy. Linia 46. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 49. 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 50. Wezel pomocniczy znak równości wierzcholek średnik. Linia 51. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 53. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 54. zamknij nawias klamrowy. Linia 55. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 56. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 58. zamknij nawias klamrowy. Linia 60. public class StosLista otwórz nawias klamrowy. Linia 61. 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 62. Stos stos znak równości new Stos otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 63. stos kropka odloz otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 64. stos kropka odloz otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 65. stos kropka odloz otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 66. stos kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 67. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 68. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 69. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 70. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 71. zamknij nawias klamrowy. Linia 72. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }
}

class Stos {
Wezel wierzcholek;
    public Stos() {
        wierzcholek = null;
    }
    
    public boolean czyPusty() {
        if (wierzcholek == null) {
            System.out.println("Stos pusty!");
        }
        return (wierzcholek == null);
    }
    
    public void odloz(int liczba) {
        System.out.println("Odkładam " + String.valueOf(liczba));
        
        Wezel nowy = new Wezel(liczba);
        nowy.nastepny = wierzcholek;
        wierzcholek = nowy;
    }
    public int zdejmij() {
        if (czyPusty()) return Integer.MIN_VALUE;
        Wezel pomocniczy = wierzcholek;
        int liczba = pomocniczy.liczba;
        wierzcholek = wierzcholek.nastepny;
        
        System.out.println("Zdejmuję " + Integer.toString(liczba));
        
        return liczba;
    }  
    
    public int pobierzWierzcholek() {
        if (czyPusty()) return Integer.MIN_VALUE;
        return wierzcholek.liczba;
    }
    
    public void wypisz() {
        if (czyPusty()) return;
    
        System.out.print("Stos zawiera: ");
        Wezel pomocniczy = wierzcholek;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }

}

public class StosLista {
public static void main(String[] args) {
Stos stos = new Stos();
stos.odloz(1);
stos.odloz(2);
stos.odloz(3);
stos.wypisz();
stos.zdejmij();
stos.zdejmij();
stos.zdejmij();
stos.zdejmij();
}
}

Wynik działania programu:

Odkładam 1
Odkładam 2
Odkładam 3
Stos zawiera: 3 2 1 
Zdejmuję 3
Zdejmuję 2
Zdejmuję 1
Stos pusty!

W funkcji main() na stos odkładane są trzy wartości, natomiast później metoda zdejmij() wywoływana jest cztery razy. Dlatego ostatni komunikat to: „Stos pusty!”.

Misja: stos i kolejka

Implementacja kolejki

Stos