Kurs Java Podstawy - rozszerzony

Struktury danych: Stos

Stos - jest to liniowa struktura danych, wykorzystywana często w informatyce. Głównym założeniem stosu, jest strategia LIFO - Last In First Out. W wolnym tłumaczeniu polega to na tym, aby ostatnio położony element, był z niego w pierwszej kolejności zdejmowany.

Aby wyobrazić sobie jak powinien funkcjonować stos, można przywołać w głowie obraz kilku (nastu, dziesięciu, set) dużych i ciężkich arkuszy stali, leżących jeden na drugim. Bez ciężkiego sprzętu (a zakładamy, że takim nie dysponujemy), aby dostać się do arkuszy położonych na dnie stosu, musimy z niego usunąć te leżące na górze.

Stos można zaimplementować na dwa sposoby: za pomocą listy i tablicy. Dziś przedstawię Wam swoją implementacje tablicową.

Wyjaśnienia do kodu - rzecz jasna nie będę objaśniał wszystkich, gdyż większość jest banalna - chodzi o samą ideę.

firstFree - nazewnictwo może być dowolne. Generalnie jest to najważniejszy element stosu, tak zwany wierzchołek. Odpowiada za prawidłowe dodawanie, zdejmowanie, generowanie rozmiaru - generalnie to taki boss stosowego półświatka.I w tym momencie mamy dwie możliwości. Albo wskazywać na pierwsze wolne miejsce (jak zrobiłem ja), albo na ostatnio zajęte. Zmiany w obu przypadkach są kosmetyczne, trzeba tylko być świadomym, który warian implementujemy.

pop, push- elementy są dodawane / zdejmowane, z odpowiedniego miejsca wskazywanego przez wierzchołek, generalnie żadnej magii. Istotne (najistotniejsze?) jest, aby w wyżej wymienionych metodach, nie zapomnieć o inkrementacjach / dekrementacjach owej zmiennej wierzchołkowej.

display -Metoda ciekawa, ze względu na to, że aby zachować właściwości stosu, elementy musimy wyświetlać w odwrotnej kolejności, tak jak ściągamy arkusze blachy, od samej góry, do samego dołu.

clean - również bez czarów. Zerujemy wierzchołek, zerujemy tablicę (choć to niekonieczne. Wartości po prostu będą podmieniane).

//Autor: Mateusz Koza

public class Stack {

    // Zdefiniowanie tablicy i elementów odpowiedzialnych za wierzchołek.
    double[] tab;
    int firstFree;

    // Konstruktor, który zainicjuje wierzchołek i stos o odpowiedniej
    // wielkości.
    public Stack(int MaxSize) {
        tab = new double[MaxSize];
        firstFree = 0;
    }

    // Metoda zwracająca maksymalny rozmiar stosu
    int getMaximumStackSize() {
        return tab.length;
    }

    // Metoda zwracająca prawdę, jeżeli stos jest pusty
    boolean isEmpty() {
        if (firstFree == 0) {
            return true;
        } else
            return false;
    }

    // Metoda zwracająca rozmiar stosu
    int getSize() {
        return firstFree;
    }

    // Metoda dodająca na stos
    void Push(double E) throws ArrayIndexOutOfBoundsException {
        if (firstFree < tab.length) {
            tab[firstFree] = E;
            firstFree++;

        } else {
            throw new ArrayIndexOutOfBoundsException(
                    "Przepełnienie stosu, operacja nie powiodła się");
        }
    }

    // Metoda zdejmująca ze stosu
    double Pop() throws IndexOutOfBoundsException {
        if (firstFree <= 0) {
            throw new IndexOutOfBoundsException(
                    "Stos jest pusty, operacja nie powiodła się");
        }

        double temp = tab[firstFree - 1];
        firstFree--;
        return temp;
    }

    // Metoda wyświetlająca zawartość stosu
    void display() throws IndexOutOfBoundsException {
        if (firstFree == 0) {
            throw new IndexOutOfBoundsException(
                    "Stos jest pusty, operacja nie powiodła się");
        }

        int temp = firstFree - 1;
        do {
            System.out.println(tab[temp]);
            temp--;
        } while (temp > -1);

    }

    // Metoda wielokrotnego zdjęcia
    void multiPop(int k) {
        if (k < firstFree) {
            for (int i = k; i > 0; i--) {
                System.out.println(Pop());
            }
        }
    }

    // Metoda czyszcząca stos
    void clear() {
        for (int i = 0; i < firstFree; i++) {
            tab[i] = 0.0;

        }

        firstFree = 0;
    }

    // Metoda odwracająca kolejność elementów na stosie
    void reverse() {
        for (int i = 0; i < firstFree / 2; i++) {
            double temp = tab[i];
            tab[i] = tab[firstFree - 1 - i];
            tab[firstFree - 1 - i] = temp;

        }
    }
}

Komentarze

Bartek

Super fajnie, że jest tu coś takiego, ale niestety, wydaje mi się, że stos na innym typie danych jest dużo trudniejszy, np. na char, którego sam nie umiem napisać :(

Marcin Kunert

Zamień wszystkie double na char i powinno działać.

Bartek

tak, jednakże nie sprecyzowałem swojego posta do końca. Trudniejszy jest stos na liście jednokierunkowej :(