:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/abstrakcyjne-struktury-danych-stos.md

Abstrakcyjne struktury danych: Stos

Tworząc oprogramowanie czasami zapisywanie poszczególnych danych do zwykłych zmiennych, tablicy bądź plików po prostu przestaje wystarczać bądź jest całkowicie nieefektywne. W takich przypadkach na pomoc programiście przychodzi programowanie zorientowane obiektowo i abstrakcyjne struktury danych. W tym artykule zajmiemy się stosem (ang. stack).

Stos to jedna z najprostszych do zrozumienia abstrakcyjnych struktur danych. Całą ideę jego funkcjonowania można opisać powołując się na prosty przykład ze stosem talerzy. Załóżmy, że mamy kilka talerzy i układamy je jeden na drugim tworząc swego rodzaju stos. Talerz (element), który położyliśmy jako ostatni będziemy ściągać jako pierwszy ponieważ znajduje się on na samej górze. Nie możemy wyciągać żadnych talerzy (elementów) ze środka, ani z dołu ponieważ mogło by to grozić rozbiciem pozostałych. Zasada jest więc bardzo prosta: ostatni talerz (element) jaki został odłożony, ściągamy jako pierwszy.

Jak nie trudno się domyślić na stos możemy odłożyć nieskończenie wiele talerzy (elementów) co jest jedną z kluczowych zalet tej struktury danych. Załóżmy bowiem, że mamy do czynienia z jakimiś danymi, ale w momencie pisania kodu nie wiemy ile ich ostatecznie będzie, wobec czego nie możemy do ich przechowywania zastosować tablicy.

Jeśli chodzi o kwestię techniczną to oczywiście talerze zastępujemy jakimś obiektem (zmienną), który oprócz przechowywanej wartości musi zawierać wskaźnik na element poprzedni czyli talerz odłożony wcześniej. Do prawidłowego funkcjonowania stosu potrzebujemy jeszcze wiedzieć czy zawiera on jakieś elementy czyli czy nie jest pusty oraz znać element ostatnio położony – ten, który jest najwyżej.

Zalety i wady stosowania stosu:

ZALETYWADY
  • Łatwa implementacja,
  • Możliwość zapisu dowolnej liczby danych (za wyjątkiem stosu opartego o tablicę),
  • Szybkość działania.
  • Możliwość przepełnienia stosu opartego o tablicę,
  • Usuwanie elementu nie zwalnia zajmowanej pamięci.

Uzbrojeni w teorię zabierzmy się więc za implementację prostego stosu w Javie. Na samym początku oczywiście musimy sobie stworzyć szkielet naszego programu:

java
public class Main {

    public static void main(String[] args) {

    }
}

Powyższego kodu chyba nie trzeba nikomu tłumaczyć, można go wygenerować bezpośrednio w dobrym IDE do Java.

Stos oparty o tablicę

ZALETYWADY
  • Łatwa implementacja.
  • Możliwość przepełnienia.

Na kolejnym etapie naszej pracy stworzymy sobie nowy obiekt czyli nową klasę o nazwie Stack:

java
class Stack {

}

public class Main {

    public static void main(String[] args) {

    }
}

I dodamy do niej trzy pola: value – tablica liczb typu int do przechowywania danych, size – typu int do przechowywania rozmiaru stosu oraz top – typu int do przechowywania informacji o ostatnio odłożonym elemencie czyli tym, który możemy ściągnąć:

java
class Stack {

    int[] value;
    int size;
    int top;
}

public class Main {

    public static void main(String[] args) {

    }
}

Nasz kod powoli zaczyna się rozrastać więc teraz przyszła pora na zaimplementowanie pierwszej funkcji stosu czyli napisania kodu odpowiedzialnego za implementacje obiektu typu Stack w metodzie main. W tym celu tworzymy konstruktor klasy Stack i inicjalizujemy w nim nasze pola:

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Nasza ogólna struktura obiektu Stack czyli stosu jest już gotowa. Teraz zajmiemy się implementacją metod, które będą obsługiwać tworzoną przez nas strukturę danych. Do zaimplementowania mamy między innymi metody odpowiedzialne za:

  • wstawianie elementu na szczyt stosu – push();
  • ściąganie i usuwanie elementu ze szczytu stosu – pop();
  • sprawdzanie czy stos jest pusty – stackIsEmpty();
  • sprawdzanie czy stos jest pełny – stackIsFull(); (UWAGA: Stos oparty o tablicę danych może zostać przepełniony).

Zacznijmy od metody push():

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        value[--top] = x;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Do tablicy value poczynając od indeksu najwyższego czyli od końca tablicy przypisujemy poszczególne liczby, które odkładamy na stos. Metodę push() mamy już w części napisaną (później będziemy musieli jeszcze ją zabezpieczyć przed przepełnieniem) więc idziemy dalej, zabierzmy się zatem za następną funkcję czyli metodę pop():

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        value[--top] = x;
    }

    int pop()
    {
        return value[top++];
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Tutaj zwracamy wartość wskazywaną przez pole top i zwiększamy indeks. Metodę tą również będziemy musieli zabezpieczyć na wypadek próby ściągnięcia danych z pustego stosu. Teraz przechodzimy dalej do funkcji stackIsEmpty():

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        value[--top] = x;
    }

    int pop()
    {
        return value[top++];
    }

    boolean stackIsEmpty()
    {
        return top == size;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Jeżeli top jest równy maksymalnemu rozmiarowi stosu no to wtedy wiadomo, że stos jest pusty i zwracamy true. Mając metodę sprawdzającą czy stos jest pusty możemy zabezpieczyć funkcję pop() przed próbą ściągnięcia danych z pustego stosu:

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        value[--top] = x;
    }

    int pop()
    {
        if(!stackIsEmpty())
            return value[top++];
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == size;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Na końcu pozostało nam tylko dopisanie metody sprawdzającej czy stos jest pełny (w stosie opartym na tablicy może on zostać zapełniony):

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        value[--top] = x;
    }

    int pop()
    {
        if(!stackIsEmpty())
            return value[top++];
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == size;
    }

    boolean stackIsFull()
    {
        return top == 0;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Jeżeli top jest równy 0 to tablica jest pełna. Zabezpieczmy więc metodę push() przed próbą odłożenia na pełny stos jakiś danych:

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        if(!stackIsFull())
            value[--top] = x;
        else System.out.println("Stos jest pełny");
    }

    int pop()
    {
        if(!stackIsEmpty())
            return value[top++];
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == size;
    }

    boolean stackIsFull()
    {
        return top == 0;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Nasz stos jest już gotowy, napiszmy sobie prosty program wykorzystujący jego możliwości oraz dla lepszej wygody dopiszmy jeszcze metodę top() zwracającą wartość ze szczytu stosu:

java
class Stack {

    int[] value;
    int size;
    int top;

    Stack(int Size)
    {
        value = new int[Size];
        size = Size;
        top = size;
    }

    void push(int x)
    {
        if(!stackIsFull())
            value[--top] = x;
        else System.out.println("Stos jest pełny");
    }

    int pop()
    {
        if(!stackIsEmpty())
            return value[top++];
        else
            return -1;
    }

    int top()
    {
        if(!stackIsEmpty())
            return value[top];
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == size;
    }

    boolean stackIsFull()
    {
        return top == 0;
    }
}

public class Main {

    public static void main(String[] args) {

        Stack stack = new Stack(10);

        for(int i = 0;i<10;i++)
            stack.push(i); //odkładamy na stos elementy od 0 do 9

        stack.push(10); //błąd - stos jest pełny

        System.out.println(stack.top()); //sprawdzamy co jest na szczycie stosu

        for(int i = 0;i<10;i++)
            System.out.println(stack.pop()); //ściągamy elementy ze stosu

        stack.pop(); //błąd - stos jest pusty
    }
}

Stos oparty o listę jednokierunkową

ZALETYWADY
  • Możliwość przechowywania praktycznie nieograniczonej ilości danych,
  • Szybkość działania.
  • Trudniejsza implementacja w porównaniu do stosu opartego o tablicę.

Tworzenie stosu opartego o listę jednokierunkową rozpoczynamy od przygotowania samej listy czyli tworzymy nowy obiekt (klasę) List, gdzie tworzymy jedno pole typu int na przechowywanie danych oraz jedno pole typu List (czyli pole, którego typem jest tworzona przez nas klasa) do przechowywania informacji o obiekcie poprzednim:

java
class List
{
    int value;
    List prev;
}

public class Main {

    public static void main(String[] args) {

    }
}

Następnie zajmiemy się inicjalizacją wyżej stworzonych pól klasy List. W tym celu napiszemy konstruktor w którym zainicjalizujemy pole value oraz prev przekazywanymi argumentami:

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Listę mamy już gotową, teraz pora napisać drugi obiekt, który będzie naszym stosem. Tworzymy więc klasę Stack, a w niej pole typu List (czyli pole, którego typem będzie nasza wcześniej utworzona lista):

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;
}

public class Main {

    public static void main(String[] args) {

    }
}

Stworzone pole o nazwie top typu List będziemy używać do przechowywania informacji o ostatnim odłożonym elemencie na stos. Oczywiście dobrą praktyką jest jego inicjalizacja:

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Nasza ogólna struktura obiektu Stack czyli stosu oraz List czyli listy jest już gotowa. Teraz zajmiemy się implementacją metod, które będą obsługiwać tworzony przez nas stos. Do zaimplementowania mamy między innymi metody odpowiedzialne za:

  • wstawianie elementu na szczyt stosu – push();
  • ściąganie i usuwanie elementu ze szczytu stosu – pop();
  • sprawdzanie czy stos jest pusty – stackIsEmpty();

Zacznijmy od metody push():

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }

    void push(int x)
    {
        top = new List(x, top);
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

W metodzie push() tworzymy oczywiście nowy obiekt typu List i przypisujemy go do pola top, ponieważ to właśnie on jest teraz na szczycie stosu. Jako argumenty podajemy daną którą chcemy zapisać (w tym przypadku jest to liczba typu int) oraz obiekt, który poprzednio był na szczycie (musimy wiedzieć, jaki obiekt będzie na szczycie, kiedy ten właśnie dodawany zostanie zdjęty).

Przebrnęliśmy właśnie przez tworzenie metody push() więc teraz przyszła kolej na kolejną czyli funkcję pop():

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }

    void push(int x)
    {
        top = new List(x, top);
    }

    int pop()
    {
        int tmp = top.value;
        top = top.prev;
        return tmp;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Metodę pop() będziemy musieli jeszcze zabezpieczyć przed próbą ściągnięcia z pustego stosu jakiegoś elementu ale to w kolejnym kroku. Tutaj zrobiliśmy sobie zmienną pomocniczą tmp do której przypisujemy element obecnie znajdujący się na szczycie. Dalej do zmiennej top przypisujemy element poprzedni (czyli jakby zapominamy o elemencie, który właśnie jest przez nas ściągany) no i na końcu zwracamy wartość zmiennej tmp.

Teraz pozostało nam napisanie metody sprawdzającej czy stos jest pusty:

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }

    void push(int x)
    {
        top = new List(x, top);
    }

    int pop()
    {
        int tmp = top.value;
        top = top.prev;
        return tmp;
    }

    boolean stackIsEmpty()
    {
        return top == null;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Oraz zabezpieczenie metody pop():

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }

    void push(int x)
    {
        top = new List(x, top);
    }

    int pop()
    {
        if(!stackIsEmpty())
        {
            int tmp = top.value;
            top = top.prev;
            return tmp;
        }
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == null;
    }
}

public class Main {

    public static void main(String[] args) {

    }
}

Nasz stos jest już gotowy, napiszmy sobie prosty program wykorzystujący jego możliwości oraz dla lepszej wygody dopiszmy jeszcze metodę top() zwracającą wartość ze szczytu stosu:

java
class List
{
    int value;
    List prev;

    List(int x, List Prev)
    {
        value = x;
        prev = Prev;
    }
}

class Stack {

    List top;

    Stack()
    {
        top = null;
    }

    void push(int x)
    {
        top = new List(x, top);
    }

    int pop()
    {
        if(!stackIsEmpty())
        {
            int tmp = top.value;
            top = top.prev;
            return tmp;
        }
        else
            return -1;
    }

    int top()
    {
        if(!stackIsEmpty())
            return top.value;
        else
            return -1;
    }

    boolean stackIsEmpty()
    {
        return top == null;
    }
}

public class Main {

    public static void main(String[] args) {

        Stack s = new Stack();

        for(int i = 0;i < 10;i++)
            s.push(i); //odkładam elementy na stos od 0 do 9

        System.out.println(s.top()); //sprawdzam co jest na szczycie stosu

        for(int i = 0;i < 10;i++)
            System.out.println(s.pop()); //ściągam elementy ze stosu

        s.pop(); //błąd - stos jest pusty
    }
}

Implementacja stosu wbudowanego w Java

Oczywiście język Java ma znacznie większe możliwości sam z siebie i nie wymaga od programistów ciężkiej i mozolnej pracy nad tworzeniem po raz setny stosu opartego o tablicę czy listę. Przy pracy nad różnego rodzaju oprogramowaniem możemy skorzystać z wbudowanych klas.

Przykład użycia wbudowanego w Java stosu:

java
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Stack s = new Stack();

        for(int i = 0;i < 10;i++)
            s.push(i); //odkładam elementy na stos od 0 do 9

        for(int i = 0;i < 10;i++)
            System.out.println(s.pop()); //ściągam elementy ze stosu
    }
}

Więcej informacji o dostępnych metodach znajduje się w dokumentacji języka Java: www.docs.oracle.com/javase/7/docs/api/java/util/Stack.html. Na tym polega cała potęga tej technologii – programy składa się z gotowych klocków ;-).

Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).