
Zadanie
W pierwszym zadaniu musiałeś stworzyć prosty algorytm obliczania mediany, tym razem weźmiemy zadanię z innej kategorii – ze struktur danych.
Twoim zadaniem jest stworzenie struktury danych Stack (stos) – implementując podany przeze mnie interfejs.
public interface Stack<T> { void clear(); boolean isEmpty(); void push(T t); T pop(); int size(); }
Jeśli nie chcesz korzystać z typów generycznych możesz wykorzystać typ Object.
public interface Stack { void clear(); boolean isEmpty(); void push(Object t); Object pop(); int size(); }
Jeszcze króki opis metod:
- clear – wyczyszczenie stosu,
- isEmpty – zwraca true, jeśli stos jest pusty,
- push – dodaje na stos obiekt
- pop – zdejmuje ze stosu ostatnią wartość i zwraca ją
- size – zwraca rozmiar stosu
Do implementacji stosu stosuje się tablicę i w taki sposób powinno ono być zaimplementowane – bez użycia kolekcji.
Czym jest stack
Stack (stos) – jest strukturą danych, do której można wrzucać elementy tylko na jej koniec (na samą górę) oraz zdejmować również tylko z końca (z góry). Można wyobrazić sobie stos talerzy, gdzie możemy zdejmować tylko z samej góry i dokładać nowe talerze w to samo miejsce.
Przykład
Poniższy przykład użycia stosu, żeby nie było żadnych wątpliwości.
public class Main { public static void main(String[] args) { Stack<String> names = new StackImpl<>(); names.push("Pablo"); names.push("Tuturu"); System.out.println("Powinien zwrócić obiekt Tuturu: " + names.pop()); System.out.println("Size powinien zwrocić size = 1 " + names.size()); names.clear(); System.out.println("Powinien zwrócić true: " + names.isEmpty()); } }
Punktacja
Za to zadanie można otrzymać maksymalnie 200 expa + 30 expa dodatkowo.
Przygotowane są cztery testy, za każdy zdany test otrzymasz 50expa, dodatkowo za użycie typów generycznych otrzymasz 30expa.
Porady
- Staraj się stosować angielskie nazewnictwo nazw zmiennych, metod, klas
- Przetestuj swój stos dla skrajnych przypadków np. dodawanie dużo elementów, próby zdejmowania z pustego stosu itd.
- Na początku stwórz stos dla konkretnego typu danych np. Integer – dopiero później wprowadź sobie typ generyczny
Termin
Zadanie zostało opublikowane 9 listopada 2018 roku, rozwiązania można przesyłać do 11 listopada 2018 roku do godziny 23:59. Zadania wysłane później będą automatycznie usuwane.
Format
Zadanie należy wysłać na email: njd@1024kb.pl z tematem: TWÓJ-NICK_STACK.
W załączniku należy przesłać plik o nazwie TWÓJ-NICK_STACK.java, w którym znajduje się tylko implementacja stosu. Nie wysyłaj interfejsu, klasy Main, ani całego projektu. Tylko klasę, która implementuje interfejs Stack. Pliki w załączniku – bez gita i różnych pastebinów. 😉
Rozwiązanie
Poniżej możesz zobaczyć moje przykładowe rozwiązanie. Tym razem rozwiązanie przysłało 13 osób – miałem nadzieję, że trochę więcej osób się podejmie zadania. 😉
import java.util.EmptyStackException; public class StackImpl<T> implements Stack<T> { private int maxStackSize = 16; private Object [] objects = new Object[maxStackSize]; private int size = 0; public StackImpl() { } public void clear() { maxStackSize = 16; objects = new Object[maxStackSize]; size = 0; } public boolean isEmpty() { return size == 0; } private void increaseStack() { maxStackSize *= 2; Object [] newStack = new Object[maxStackSize]; for(int i=0;i<size;i++) { newStack[i] = objects[i]; } objects = newStack; } public void push(T t) { if (size == maxStackSize) { increaseStack(); } objects[size++] = t; } public T pop() { if (isEmpty()) { throw new EmptyStackException(); } T object = (T) objects[--size]; return object; } public int size() { return size; } }
W przypadku próby zdjęcia elementu, który nie istnieje rzucam wyjątkiem EmptyStackException, który jest wbudowany w java.util – lepiej zrobić tak zamiast zwracać nulla. 😉
Zadanie było testowane poniższym zbiorem testów:
import org.junit.Assert; import org.junit.Test; import pl.maniaq.Stack; import pl.maniaq.StackImpl; public class TestStack { @Test public void firstStackTest() { //is Stack<String> stack = new StackImpl<>(); stack.push("Pablo"); stack.push("Katarina"); stack.push("XYZ"); stack.pop(); //when String popValue = stack.pop(); //expected Assert.assertEquals("Katarina", popValue); } @Test public void secondStackTest() { //is Stack<String> stack = new StackImpl<>(); stack.push("Pablo"); stack.push("Katarina"); stack.pop(); stack.pop(); //when int size = stack.size(); //expected Assert.assertEquals(0, size); } @Test public void thirdStackTest() { //is Stack<Integer> stack = new StackImpl<>(); for(int i=0;i<1000;i++) { stack.push(i); } //when int size = stack.size(); //expected Assert.assertEquals(1000, size); } @Test public void fourthStackTest() { //is Stack<Integer> stack = new StackImpl<>(); for(int i=0;i<1000;i++) { stack.push(i); } //when stack.clear(); boolean isEmpty = stack.isEmpty(); //expected Assert.assertTrue(isEmpty); } }
Oczywiście czasami testy musiałem lekko zmodyfikować (szczególnie, gdy ktoś nie użył typu generycznego), jednak dałem radę. 😉
Kilku osobom nie przechodziły testy w przypadku, gdy chcieliśmy dodać dużo więcej elementów do stosu – ich implementacja pozwalała na dodanie np. 10 lub 100. Niestety nie jest do idealna implementacja (choć ta moja również nie jest :P) stosu – w końcu chcemy dodawać mnóstwo elementów, a nie tylko kilkadziesiąt.
Dodatkowa rada, dla niektórych osób: proszę nie używajcie System.out.println w takich implementacjach, lepiej jest zastosować np. wyjątek. Stosując println ograniczamy się tylko do konsoli, a co gdybyśmy chcieli używać stos np. w aplikacji webowej? 😉
Prawdopodobnie nie do końca zrozumiałem się z dwoma osobami, które poprzez metodę size() – zwracały rozmiar tablicy, a nie ilość elementów. Nic na to teraz nie poradzę, a w następnym zadaniu postaram się nie dopuścić takich niedomówień. 😉