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