Stos - implementacja tablicowa

Stos to struktura danych działająca w oparciu o zasadę LIFO (ang. Last In First Out), ostatni wchodzi pierwszy wychodzi. Dostęp do stosu możliwy jest tylko z jednego miejsca tzw. wierzchołka (ang. top). Podstawowe metody związane ze stosem to odłożenie elementu na stos (ang. push), ściągnięcie elementu ze stosu (ang. pop), podgląd elementu znajdującego się na szczycie stosu (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości stosu jak i sprawdzenia czy stos jest pusty. Chcemy napisać, w oparciu o tablicę, prostą klasę Stos przechowującą liczby całkowite (dane typu int). Poniżej klasa wraz z jej przykładowym wykorzystaniem.

/**
 * Stos liczb całkowitych - implementacja tablicowa
 * @author kodatnik.blogspot.com 
 */ 
class Stos {
 // tablica przechowująca elementy stosu
 private int[] wektor;
 // wierzchołek stosu
 private int top;

 // konstruktor domyślny (tworzy stos 10 elementowy)
 public Stos() {
  // wywołujemy konstruktor z parametrem int (czyli ten poniżej)
  this(10);
 }
 
 // konstruktor jednoparametrowy
 public Stos(int rozmiar) {
  // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania
  wektor = new int[rozmiar];
  // ustawiamy wartość początkową wierzchołka stosu
  top = -1;
 }
 
 // metoda odkładająca na stosie elementy
 public void push(int element) {
  // wpisujemy na odpowiedniej pozycji element oraz zwiększamy wierzchołek
  wektor[++top] = element;
 }

 // metoda ściąga ze stosu element
 public int pop() {
  // zwracamy element z wierzchołka stosu oraz zmniejszamy wierzchołek
  return wektor[top--]; 
 }
 
 // metoda sprawdza czy stos jest pusty
 public boolean czyPusty() {
  // zwracamy prawdę lub fałsz
  return (top == -1);
 }
 
 // metoda sprawdza czy stos jest pełny
 public boolean czyPelny() {
  // zwracamy prawdę lub fałsz
  return (top == wektor.length);
 }
 
 // metoda "podgląda" co jest na wierzchołku stosu
 public int peek() {
  // zwracamy element z wierzchołka stosu (nie modyfikujemy zmiennej top)
  return wektor[top];
 }
 
 // metoda wyświetla wszystkie elementy stanowiące stos
 public void wyswietl() {
  // w pętli do wierzchołka stosu
  for(int i = 0; i <= top; i++) 
   // wyświetlamy poszczególne elementy
   System.out.print(wektor[i] + " ");

  System.out.println();
 }
 
 // metoda zwraca rozmiar stosu (liczbę jego elementów)
 public int rozmiar() {
  return top + 1; 
 }
}

/**
 * Test kolejki liczb całkowitych
 * @author kodatnik.blogspot.com 
 */ 
public class TestKolejki {

 public static void main(String args[]) {
    
  // zakładamy nowy stos o rozmiarze 20
  Stos s = new Stos(20);
     
  // odkładamy kolejne wartości na stos
  s.push(12);
  s.push(8);
  s.push(39);
     
  // wyświetlamy zawartość stosu
  s.wyswietl();
     
  // wyświetlamy element znajdujący się na szczycie (bez jego ściągania)
  System.out.println(s.peek());
     
  // ściągamy element ze stosu
  s.pop();     
      
  // wyświetlamy zawartość stosu
  s.wyswietl();     
 }
}

Uruchomiona aplikacja:

12 8 39 
39
12 8

Powyższy stos jest statyczny, jego rozmiar ustalamy podczas tworzenia obiektu (nie mamy możliwości jego zmiany w trakcie działania). Przechowujemy dane tylko jednego typu (int), co w większości zastosowań może okazać się niewystarczające. Lepszym rozwiązaniem jest zastosowanie do implementacji stosu list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia stosów przechowujących dowolny typ danych).

Stos jest często wykorzystywany w algorytmice jak również w większości aplikacji, z którymi pracujemy codziennie (np. operacja cofnij w edytorach tekstu czy grafiki).