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ń. 😉
: