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