Abstrakcyjne struktury danych: Stos
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
}
}