Proste działania na stosie

Stos jest strukturą danych polegającą na tym, że umieszczamy na nim dane (ang. push) i dostajemy je spowrotem (ang. pop) w odwrotnej kolejności niż umieściliśmy. Takie coś może się przydać do bardzo wielu rzeczy, na przykład obliczenie wyrażenia ONP wymaga zastosowania stosu.

Działania na stosie w języku C są bardzo proste. Aby utworzyć stos musimy zdefiniować dwie rzeczy (można je "spakować" w tzw. strukturę) - tablicę przechowującą dane (tutaj będą to liczby całkowite, typu int) oraz zmienną liczbową wskazującą ile elementów mamy na stosie (bez znaku bo liczba elementów nie może być ujemna, poczatkowo oczywiście 0):

int stos [100];
unsigned int ile = 0;

Teraz pewnie przydałyby się funkcje wykonujące działania push i pop... Otóż nie, działania te są tak proste, że nie są nawet warte definiowania funkcji. Push wygląda następująco:

stos [ile++] = wartosc;

Analogicznie pop:

zmienna = stos [--ile];

Umiejscowienie operatorów ++ i -- jest w tym przypadku kluczowe, nie można go zmienić. Dla wygody możemy również zdefiniować makra:

#define push stos[ile++]
#define pop stos[--ile]
/* od teraz zadziała "push = wartosc;" i "zmienna = pop;" */

Stos jest gotowy do użycia, ale zapomnieliśmy o ważnej rzeczy. Mianowicie, jeśli wykonamy pop na pustym stosie lub push gdy stos jest zapchany (w przykładzie pojemność wynosi 100 elementów) to dojdzie do odczytu lub zapisu poza tablicą i dostaniemy losowy wynik lub nieświadomie uszkodzimy jakieś dane (inne dane naszego programu, systemu operacyjnego - bardzo groźne, na systemach wielozadaniowych - innego programu). Możemy także uruchomić występujące w niektórych systemach (wszystkich nowoczesnych, m. in. Windows) procedury ochronne, które bez ostrzeżenia zatrzymają nasz program jako niebezpieczny. Trzeba po prostu sprawdzać czy operacja jest normalnie możliwa:

void blad ()
  {
    puts ("Błąd stosu!");
    exit (1);
  }

/* ... */

if (ile < 1) blad ();
przyklad = stos [--ile];

/* ... */

if (ile >= 100) blad (); /* zależy jaka pojemność */
stos [ile++] = przyklad;

Opakowanie stosu w strukturę, o którym wspomniałem wcześniej, mogłoby wyglądać tak:

struct stos
  {
    int dane [100];
    unsigned int ile;
  }

Wraz z kontrolami i opakowaniem sprawa coraz bardziej się komplikuje, tu przydadzą się już odpowiednie funkcje:

/* inicjalizuje nowy stos albo czyści używany ustawiając licznik elementów na zero */
void nowy (struct stos *st)
  {
    st->ile = 0;
  }

void push (struct stos *st, int wartosc)
  {
    if (st->ile >= 100) return;
    st->dane [(st->ile)++] = wartosc;
  }

/* gdy brak elementów, zwraca 0 */
int pop (struct stos *st)
  {
    if (st->ile < 1) return 0;
    return st->dane [--(st->ile)];
  }

Konieczne jest tu zastosowanie wskaźników. Na koniec przykład użycia:

/* ... */
struct stos test; int i;
nowy (&test);
push (&test, 12);
push (&test, 34);
for (i = 0; i < 3; i++)
  printf ("%d\n", pop (&test));
/* ... */

Wyjście:

34
12
0