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:
| ZALETY | WADY |
|
|
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:
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ę
| ZALETY | WADY |
|
|
Na kolejnym etapie naszej pracy stworzymy sobie nowy obiekt czyli nową klasę o nazwie Stack:
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ąć:
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:
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():
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():
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():
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:
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):
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:
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:
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ą
| ZALETY | WADY |
|
|
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:
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:
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):
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:
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():
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():
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:
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():
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:
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:
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 ;-).



// brak komentarzy — bądź pierwszy