Stosy - Java
Stos to ograniczona lista — nowe węzły można dodawać i usuwać tylko na szczycie stosu. Z tego powodu stos jest strukturą danych typu ostatnie weszło, pierwsze wychodzi (LIFO). Składowa łącza dolnego węzła stosu jest ustawiona na null, aby wskazać dno stosu. Stosu nie trzeba implementować jako listy — można go implementować za pomocą tablicy lub ArrayList.
Operacje na stosie
Podstawowymi metodami do obsługi stosu są push i pop, które odpowiednio dodają nowy węzeł do szczytu stosu i usuwają węzeł ze szczytu stosu. Metoda pop ponadto zwraca dane ze zdjętego węzła.
Zastosowania stosu
Stosy mają wiele interesujących zastosowań. Przykładowo gdy program wywołuje metodę, musi ona wiedzieć, jak powrócić do kodu wywołującego, więc adres powrotu do metody wywołującej jest umieszczany na stosie wywołań metod. Jeśli dojdzie do serii wywołań metod, każdy kolejny adres powrotu również trafia na stos w porządku „ostatni wszedł, pierwszy wychodzi”, więc każda z metod użyje właściwego powrotu. Stos obsługuje rekurencyjne wywołania metod w taki sam sposób jak tradycyjne wywołania
metod. Stos wywołań programu zawiera również pamięć dla zmiennych lokalnych związanych z każdą z wywoływanych metod. Gdy metoda zwraca sterowanie do kodu wywołującego, pamięć zajmowana przez zmienne lokalne jest zwalniana, więc zmienne przestają być dostępne. Jeśli zmienna lokalna dotyczyła referencji do obiektu, a obiektu tego nie dotyczy już żadna inna zmienna, obiekt może zostać usunięty mechanizmem odśmiecania pamięci.
Kompilatory używają stosów do wyliczania wyrażeń arytmetycznych i generowania kodu maszynowego do ich przetworzenia.
Klasa Stack zawierająca List
Wykorzystamy bliski związek między listami i stosami do implementacji klasy stosu, która skorzysta z istniejącej implementacji klasy List (rysunek 21.3). Użyjemy kompozycji, dołączając referencję do obiektu List jako prywatną zmienną instancji. Struktury danych listy, stosu i kolejki są implementowane w taki sposób, aby umożliwić przechowywanie obiektów dowolnego typu i wspomóc wielokrotne wykorzystanie tego samego kodu. Klasa Stack (rysunek 21.9) jest zadeklarowana w pakiecie com.deitel.datastructures (wiersz 3.), co pozwala na jej wielokrotne użycie. Kod źródłowy z pliku Stack nie importuje List, bo
obie klasy znajdują się w tym samym pakiecie. Użyj następującego polecenia do kompilacji klasy Stack:
javac -d .. -cp .. Stack.java
2 // Klasa Stack używająca kompozycji obiektu List
3 package com.deitel.datastructures;
4
5 import java.util.NoSuchElementException;
6
7 public class Stack {
8 private List stackList;
9
10 // Konstruktor
11 public Stack() {stackList = new List("stos");}
12
13 // Dodanie obiektu do stosu
14 public void push(E object) {stackList.insertAtFront(object);}
15
16 // Usunięcie obiektu ze stosu
17 public E pop() throws NoSuchElementException {
18 return stackList.removeFromFront();
19 }
20
21 // Określenie, czy stos jest pusty
22 public boolean isEmpty() {return stackList.isEmpty();}
23
24 // Wyświetlenie zawartości stosu
25 public void print() {stackList.print();}
26 }
Rysunek 21.9. Klasa Stack używająca kompozycji obiektu List
Metody klasy Stack
Klasa Stack ma cztery metody: push, pop, isEmpty i print. Są to tak naprawdę metody insertAtFront, removeFromFront, isEmpty i print z List. Inne metody klasy List nie powinny być dostępne z poziomu kodu używającego Stack — właśnie dlatego zdecydowaliśmy się na prywatną kompozycję List (wiersz 8.) zamiast dziedziczenia, bo możemy w ten sposób ukryć pozostałe metody List. Wszystkie metody Stack są wykonane jako wywołania metod List. To tak zwana delegacja — każda z metod Stack deleguje pracę do odpowiedniej metody klasy List. W tym przypadku klasa Stack deleguje wywołania
do metod insertAtFront (wiersz 14.), removeFromFront (wiersz 18.), isEmpty (wiersz 22.) i print (wiersz 25.) z List.
Testowanie klasy Stack
Klasa StackTest (rysunek 21.10) tworzy obiekt Stack o nazwie stack (wiersz 8.). Program umieszcza wartości int na stosie (wiersze 11., 13., 15. i 17.). Automatyczne opakowywanie zamienia każdy z argumentów na obiekt Integer. Wiersze od 21. do 33. zdejmują obiekty ze stosu. Jeśli metoda pop zostanie wywołana dla pustego stosu, zgłosi wyjątek NoSuchElementException. W takiej sytuacji program wyświetli zrzut stosu, który pokazuje metody ze stosu wywołań z momentu zajścia wyjątku. Program wyświetla zawartość stosu po każdej operacji zdjęcia elementu. Aby skompilować i uruchomić klasę StackTest, użyj następujących poleceń:
javac -cp .;.. StackTest.java
java -cp .;.. StackTest
2 // Program modyfikujący stos
3 import com.deitel.datastructures.Stack;
4 import java.util.NoSuchElementException;
5
6 public class StackTest {
7 public static void main(String[] args) {
8 Stack stack = new Stack<>();
9
10 // Użyj metody push
11 stack.push(-1);
12 stack.print();
13 stack.push(0);
14 stack.print();
15 stack.push(1);
16 stack.print();
17 stack.push(5);
18 stack.print();
19
20 // Usuwaj elementy ze stosu
21 boolean continueLoop = true;
22
23 while (continueLoop) {
24 try {
25 int removedItem = stack.pop(); // Usuń element ze szczytu
26 System.out.printf("%nZdjęto %d%n", removedItem);
27 stack.print();
28 }
29 catch (NoSuchElementException noSuchElementException) {
30 continueLoop = false;
31 noSuchElementException.printStackTrace();
32 }
33 }
34 }
35 }
stos zawiera: -1
stos zawiera: 0 -1
stos zawiera: 1 0 -1
stos zawiera: 5 1 0 -1
Zdjęto 5
stos zawiera: 1 0 -1
Zdjęto 1
stos zawiera: 0 -1
Zdjęto 0
stos zawiera: -1
Zdjęto -1
Pusty stos
java.util.NoSuchElementException: stos jest pusta
at com.deitel.datastructures.List.removeFromFront(List.java:68)
at com.deitel.datastructures.Stack.pop(Stack.java:18)
at StackTest.main(StackTest.java:25)
Rysunek 21.10. Program modyfikujący stos
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
