Omówienie stosu

W poprzedniej lekcji o typach generycznych otrzymałeś zadanie – stworzyć strukturę danych stos przy użyciu typów generycznych. Jest to zadanie, które może sprawiać niektórym problemy, dlatego pozwolę sobie je w miarę sensownie omówić.

Stos…

Stos jak wspomniałem jest strukturą danych – w zadaniu wspomniałem jeszcze, że wyróżnia się tym, że można dodawać elementy tylko na górę stosu i również tylko z góry ściągać elementy. Tak jak stos talerzy – oczywiście, bez żadnej oszukiwania.

Po co w ogóle taka struktura danych?

Stos jest sporadycznie używany w projektach biznesowych, jego głównym zastosowaniem jest zarządzanie procesami lub pamięcią np. w wirtualnej maszyny Javy – czyli dobrze znane JRE.

Stos również jest bardzo popularnym zadaniem dla początkujących programistów – szczególnie na studiach. Pojawia się on jako zadanie również na rozmowach kwalifikacyjnych z tego, więc powodu go sobie zaimplemenetujemy.

Założenia

W zadaniu dałem podpowiedź również, żeby na początku stos zrobić bez typów generycznych – my zrobimy na początku na Stringu. Do przechowywania dodawanych elementów na stos będzie służyć tablica, dodatkowo w klasie będziemy przechowywać indeks ostatnio dodanego elementu. Liczba -1 będzie oznaczać, że stos jest pusty.

Implementacja!

Skoro mamy przechowywać tablicę Stringów i index ostatniego elementu to zróbmy to!

public class Stack {
    private String [] elements;
    private int lastIndex;

    public Stack() {
        elements = new String[10];
        lastIndex = -1;
    }
}

Na początku nasza tablica jest zainicjalizowana na 10 elementów – w przypadku, gdy będziemy dodawać 11 element trzeba będzie stworzyć nową większa i przekopiować do niej stare elementy. 😉

Push

Metoda push (albo inaczej add) służy do dodawania elementów na stos. Jako argument przyjmuje oczywiście element, który ma być dodany.

public void push(String element) {
}

Przed dodaniem elementu musimy sprawdzić czy jest na niego miejsce w tablicy. Do tego wykorzystamy taką metodę

private boolean isNotEmptySpaceInArray() {
    return lastIndex >= elements.length - 1;
}

Owa metoda sprawdza czy aktualny index jest większy bądź równy długości tablicy – 1. Dzięki temu nigdy nie wyjdziemy poza tablicę. Mamy teraz, więc taki kod:

public void push(String element) {
    if (isNotEmptySpaceInArray()) {
    }
}

Jeśli zaś warunek zostanie spełniony – czyli nie ma już miejsc na nowe elementy to trzeba powiększyc naszą tablicę. My będziemy powiększać tablicę za każdym razem o dwa razy. W tym celu stworzymy nową metodę:

private String[] increaseArraySize(String[] elements) {
    int newSize = elements.length * 2;
}

Skoro mamy już rozmiar nowej tablicy to czas ją stworzyć i przekopiować do niej nowe elementy. Do tego celu posłuży nam kolejna metoda:

private String[] copyToNewArray(String[] elements, int newSize) {
    String [] newElements = new String[newSize];
    for(int i=0;i<elements.length;i++) {
        newElements[i] = elements[i];
    }
    return newElements;
}

Nie jest ona bardzo skomplikowana – na początku tworzymy dwukrotnie większą tablicę, a elementy ze starej tablicy kopiujemy do nowej, którą zwracamy z metody.

Mając już gotową metodę copyToNewArray możemy jej użyć o tutaj:

private String[] increaseArraySize(String[] elements) {
    int newSize = elements.length * 2; 
    return copyToNewArray(elements, newSize);
}

A metody increaseArraySize możemy już użyć tutaj:

public void push(String element) {
    if (isNotEmptySpaceInArray()) {
        elements = increaseArraySize(elements);
    }
}

Skoro nasza tablica już jest wystarczającego rozmiaru to możemy przejść do zwiększenia indexu ostatniego elementu i zapisania elementu pod tym indeksem.

public void push(String element) {
    if (isNotEmptySpaceInArray()) {
        elements = increaseArraySize(elements);
    }
    lastIndex++;
    elements[lastIndex] = element;
}

I w taki o to sposób mamy gotową metodę push. 😉

Pop

Kolejną częścia zadania jest metoda pop – czyli metoda do ściągania ostatniego elementu ze stosu – oczywiście o ile coś na nim jest. 😉

public String pop() {
}

Na początku w ogóle musimy sprawdzić czy stos jest pusty – w tym celu stworzyłem osobną metodę prywatną:

private boolean isEmpty() {
    return lastIndex == -1;
}

I możemy jej teraz użyć w metodzie pop – jeśli warunek zostanie spełniony to zwrócić nulla.

public String pop() {
    if (isEmpty()) {
        return null;
    }
}

Gdy mamy już to sprawdzone to możemy ściągać nasz element ze stosu – trzeba go najpierw zapisać do innej zmiennej, wpisać null na to samo miejsce oraz zmniejszyć index – to jest bardzo ważne! W końcu w tym miejscu już nic nie ma!

public String pop() {
    if (isEmpty()) {
        return null;
    }
    String popElement = elements[lastIndex];
    elements[lastIndex] = null;
    lastIndex--;
    return popElement;
}

W taki o to sposób mamy też metodę do zdejmowania elementów ze stosu.

display

W celach edukacyjnych warto też stworzyć metodę display, odpowiedzialną za wyświetlenie wszystkich elementów na stosie – przypominam, że tylko w celach edukacyjnych. W normalnej implementancji stosu nie powinna ona istnieć, w końcu możemy się tylko dostać do ostatniego elementu ze stosu.

public void displayStack() {
    for (int i=0;i<=lastIndex;i++) {
        System.out.println(elements[i]);
    }
}

Działa?

Sprawdźmy szybko czy działa – prosty main:

package pl.maniaq;

public class Main {

    public static void main(String[] args) {
      Stack stack = new Stack();
      stack.push("Pablo");
        stack.push("coś na stosie");
        stack.push("Witam");
        stack.push("nowy pablo");
        stack.displayStack();

        stack.pop();
        stack.pop();
        System.out.println("=====");
        stack.displayStack();
    }
}

A po uruchomieniu otrzymujemy

Pablo
coś na stosie
Witam
nowy pablo
=====
Pablo
coś na stosie

Czyli jak widać wszystko działa, kolejność wrzucania i zdejmowania się zgadza. 😉

Typy generyczne

Czas na klucz tego zadania – czyli implementacja typu generycznego.

Na początku nauki tak jak wspomniałem warto na początku zrobić to na konkretnym typie obiektu – a dopiero później to ugenerycznić, tak samo jak my teraz to zrobimy.

O ile teraz wszystko u nas jest Stringiem to wystarczy dodać ostre nawiasy z literą np. T – może być oczywiście inna. 😉

public class Stack<T>

Oraz wszystkie (w naszym przypadku wszystkie) wystąpienia Stringa zamienić na literę T.

package pl.maniaq;

public class Stack<T> {
    private T [] elements;
    private int lastIndex;

    public Stack() {
        elements = (T[]) new Object[10];
        lastIndex = -1;
    }

    public void push(T element) {
        if (isNotEmptySpaceInArray()) {
            elements = increaseArraySize(elements);
        }
        lastIndex++;
        elements[lastIndex] = element;
    }

    private T[] increaseArraySize(T[] elements) {
        int newSize = elements.length * 2;
        return copyToNewArray(elements, newSize);
    }

    private T[] copyToNewArray(T[] elements, int newSize) {
        T [] newElements = (T[]) new Object[newSize];
        for(int i=0;i<elements.length;i++) {
            newElements[i] = elements[i];
        }
        return newElements;
    }

    private boolean isNotEmptySpaceInArray() {
        return lastIndex >= elements.length - 1;
    }

    public T pop() {
        if (isEmpty()) {
            return null;
        }
        T popElement = elements[lastIndex];
        elements[lastIndex] = null;
        lastIndex--;
        return popElement;
    }

    private boolean isEmpty() {
        return lastIndex == -1;
    }

    public void displayStack() {
        for (int i=0;i<=lastIndex;i++) {
            System.out.println(elements[i]);
        }
    }


}

Choć nie do końca – niestety nie da się utworzyć tablic przy użyciu samych generyków – litery T.

Trzeba na początku utworzyć tablicę obiektów, a później rzutować ją na tablicę T – w taki o to sposób:

T [] newElements = (T[]) new Object[newSize];

I wszystko będzie już śmigać.

Testujemy jeszcze raz…

W main zmieniamy teraz z:

Stack stack = new Stack();

na

Stack<String> stack = new Stack();

I uruchamiamy:

Pablo
coś na stosie
Witam
nowy pablo
=====
Pablo
coś na stosie

I jak widać wszystko ładnie działa. 😉

Co nam to daje?

Typy generyczne zabezpieczają nas przed bałaganem – używając typów generycznych nie ma możliwości już wrzucenia obiektu innego typu niż ten, który zostanie zadeklarowany.

Spójrz, że zmieniajać inicjalizację stosu na:

Stack<Integer> stack = new Stack();

Wszystko się sypie i mówi, mi, że skoro zadeklarowałem Integer to nie mogę dodawać obiektów String – co jest raczej zrozumiale. W końcu tworzymy szablon na okreslony typ danych.

Podsumowanie

Całe rozwiązanie możesz znaleźć tutaj.

Mam nadzieję, że zrozumiałeś implementację stosu – struktury danych, bardzo podstawowej, z którą każdy się w końcu spotyka na swojej programistycznej karierze. I to już na samym początku.

Jeśli czegoś nie rozumiesz to zadaj pytanie w komentarzu lub spróbuj wrócić do lekcji jeszcze raz – chociażby nastepnego dnia lub poczytaj trochę teorii o samym stosie, a nawet rozrysuj sobie wszystko na kartce. To ostatnie rozwiązanie często bardzo pomaga.

Jednak nigdy się nie załamuj, tylko czasami daj sobie chwilę na odpoczynek i przemyślenie tematu.

Zaś jeśli wszystko jest zrozumiałe to czas na aplikację domową na ten tydzień. 😉

:

 

 

 

 

Kamil Klimek

Od 2016 jestem programistą Java. Przez pierwsze 4 lata pracowałem jako Full Stack Java Developer. Później postanowiłem postawić nacisk na Javę, żeby jeszcze lepiej ją poznać.

Subscribe
Powiadom o
guest
0 komentarzy
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x