Stack w Java

Stack w Javie zwykle oznacza klasę z Collection Framework, która implementuje interfejs List. Działa ona na zasadzie struktury danych stos, która służy do organizowania jednego z typów pamięci. Może być to również część pamięci służąca do przechowywania danych. W tym artykule zwrócimy uwagę przede wszystkim na klasę Stack, omówimy jej metody i podamy przykłady. Ale wspomnimy też o strukturze danych Stack (Stos) i powiemy do czego służy.

Co to jest struktura danych Stos

Przede wszystkim rzućmy okiem jak wygląda struktura danych stos. Jest to liniowa struktura danych działająca według zasady ostatnie weszło-pierwsze wyszło (Last-in-First-Out, LIFO). Jest to jakby przeciwieństwo kolejki. Wyobraź sobie talię kart lub stos książek w pudełku. Książka, którą położysz na stosie jako pierwszą, jest na dole, a pierwszą, którą wyjmiemy z pudełka, jest książka, która była na górze — czyli ta, która trafiła do pudełka jako ostatnia. Oto obraz gif, który pokazuje tę zasadę. Co tu się dzieje? Mamy cylinder, do którego może wpaść tylko jedna kula naraz. Najpierw w cylindrze ląduje kula pomarańczowa, potem fioletowa, a na końcu zielona (przepraszam tych, którzy znają dokładniejsze nazwy tych kolorów). Aby wydobyć pomarańczową kulę z naszego stosu-cylindra, musimy najpierw wydobyć kulę, która dotarła tam jako ostatnia (zielona), następnie tę, która była przedostatnia (ale w momencie wyjmowania jest ostatnia). Struktura danych stos w Javie lub gdziekolwiek indziej w programowaniu ma dwie najważniejsze operacje, push i pop. Operacja push umieszcza element na stosie, a operacja pop usuwa element ze szczytu stosu.

Do czego służy struktura danych Stos?

Jednym z najważniejszych zastosowań stosu jest organizowanie wywołań podprogramów. Punkt wywoławczy na stosie przechowuje adres powrotu z podprogramu po jego zakończeniu (i ewentualnie przekazane parametry). Z każdym zagnieżdżonym (w tym rekurencyjnym) wywołaniem podprogramu do stosu dodawane są nowe adresy zwrotne. Przy każdej operacji powrotu z podprogramu (return) adres powrotu jest usuwany ze stosu i przekazywane jest do niego sterowanie. To zastosowanie jest tak ważne dla programowania, że w większości procesorów stos zwrotny jest implementowany sprzętowo w zestawie instrukcji. Jednak w innych przypadkach stos musi być oparty na bardziej ogólnych strukturach danych.

Klasa Java Stack z Collection Framework

W Javie Stack to klasa z frameworka Collection, która implementuje interfejs List i rozszerza klasę Vector. Implementuje również interfejsy Collection, Iterable, Cloneable, Serializable. Jak zapewne już się domyślasz, ta klasa reprezentuje stos obiektów LIFO. Oto wywołanie konstruktora klasy Stack, czyli utworzenie obiektu tej klasy.

Stack<E> stack = new Stack<E>();

Gdzie E to typ obiektu.

Metody Java Stack

Ta klasa ma tylko jeden domyślny konstruktor i wszystkie metody klasy Vector. Dodatkowo Stack ma 5 własnych metod:

• boolean empty() metoda sprawdza czy stos jest pusty. Zwraca true jeśli stos jest pusty, w przeciwnym wypadku zwraca false.

• Object peek() ta metoda zwraca element znajdujący się na szczycie stosu.

• Object pop() ta metoda zwraca element znajdujący się na szczycie stosu i usuwa go.

• Object push(Object element) ta metoda dodaje wskazany element na wierzchu stosu.

• int search(Object element) metoda przeszukuje stos w poszukiwaniu określonego elementu. W przypadku znalezienia wymaganego elementu zwracana jest jego "odległość" od wierzchu stosu (numer porządkowy). Jeśli element nie zostanie znaleziony, zwracane jest -1.

Przykładowy kod stosu

Stwórzmy przykładowy program, który działa, jak na powyższym obrazku gif. Umieścimy na stosie trzy "kule", pomarańczową, fioletową i zieloną. Sprawdźmy, czy stos jest pusty. Następnie będziemy zdejmować kule ze stosu, aż będzie pusty.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Oto wynik działania programu: Ponieważ Stack dziedziczy po klasie Vector i implementuje interfejs List, Stack oprócz charakterystycznych dla tej struktury danych operacji push i pop do dodawania i wyodrębniania elementów, obsługuje również standardowe operacje struktury listy add () i remove(). W naszym przykładzie dodawanie elementów można zaimplementować w ten sam sposób za pomocą metody add(). Jednak można też usuwać elementy za pomocą remove() ze wskazaniem elementu, co nie ma sensu dla tej struktury danych.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Wynik pracy programu będzie oczywiście dokładnie taki sam.

A może stworzysz własną implementację stosu?

W Javie możesz stworzyć własną strukturę stosu, używając klas tablic lub połączonych list. W pierwszym przypadku do przechowywania wartości w pamięci przydzielana jest ciągła tablica komórek, które są wykorzystywane w razie potrzeby. W drugim, do każdego elementu stosu przyporządkowany jest blok pamięci, wystarczający do przechowywania wartości i odniesień do poprzedniego i następnego elementu stosu. Implementacja oparta na tablicy jest prostsza, bardziej efektywna i wydajniejsza pod względem pamięci, ale wymaga wcześniejszej znajomości limitu rozmiaru stosu i może prowadzić do trudnych do znalezienia błędów. Implementacja oparta na listach jest bardziej niezawodna, ale mniej wydajna. Stwórzmy prostą implementację stosu opartą na tablicy. Będzie ona zawierać funkcje.

• push — metoda, która obsłuży dodanie elementu (na wierzchu stosu)

• pop — metoda, która obsłuży usunięcie elementu (z wierzchu stosu)

• readTop — metoda, która zwróci element z wierzchu stosu

• sEmpty — metoda, która sprawdzi czy stos jest pusty

• isFull — metoda, która sprawdzi czy nasza tablica, w której przechowujemy stos, nie jest pełna

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;
      
   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());
      
       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Teraz zaimplementujmy przykład z trzema kulami w oparciu o nasz stos:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

Wyświetlone zostanie: Jeśli przyjrzysz się uważnie, zmienna wierzchu stosu faktycznie zawiera indeks ostatniego elementu, a odwołanie do obiektu pozostaje w tablicy. Zatem ta implementacja wymaga pewnych ulepszeń. Pomyśl o najłatwiejszym sposobie, aby to zrobić.

Czy powinniśmy używać Java Stack?

W rzeczywistości klasa Java Stack, podobnie jak jej rodzic Vector, jest przestarzałą klasą. Zamiast tego zwykle używana jest klasa ArrayList. ArrayList nie jest synchronizowana, podczas gdy klasa Vector jest synchronizowana. Oznacza to, że tylko jeden wątek na raz może uzyskać dostęp do kodu Vector, podczas gdy ArrayList może pracować z wieloma wątkami. Ponadto klasa ArrayList jest bardziej efektywna i szybsza. Tak więc najprawdopodobniej zobaczysz tę klasę tylko w starszym kodzie. Ale struktura danych Stos jest bardzo często używana w programowaniu.