/*
 * Implementacja stosu za pomoca malych struktur przechowujacych liczbe
 * calkowita.  Ten model zaklada, ze w danej chwili dysponujemy wskaznikiem na
 * najwyzszy element stosu (wierzcholek). Tylko przez ten element mamy dostep
 * do elementow kolejnych.
 *
 * [c] piotao, 20051127
 */

#include <stdio.h>
#include <stdlib.h>

/* Struktura "element_stosu" to prosty rekord (struct), ktory zawiera
 * informacje przechowywane na stosie.  W kazdej instancji tej struktury
 * znajduje sie zmienna 'liczba', oraz wskaznik na bardziej zaglebiony element
 * o takiej samej budowie (ktory trzymac moze jednakze juz inna liczbe).
 * Lancuch elementow konczy sie, gdy wartosc ostatniego elementu
 * 'element_stosu' wynosi NULL.
 */

typedef struct element_stosu {
	int liczba;                       // dane trzymane na stosie (tutaj zwykla liczba)
	struct element_stosu *ponizej;    // poprzedni element stosu (obecny element to wierzcholek)
} Stos;

/* Operacja push na stosie sluzy do wstawienia na stos dodatkowego elementu.
 * Funkcja zwraca wierzcholek stosu, zatem mozna ja wywolac nadpisujac porzedni
 * wierzcholek:
 *
 * stos = push(liczba,stos);
 */

Stos *push(int liczba, Stos *stos){
	Stos *nowy;                              // zmienna pomocnicza na nowy element
	nowy = (Stos *) malloc( sizeof(Stos) );  // alokacja pamieci na nowy element
	nowy->ponizej = stos;                    // w nowym ustawiamy wskazanie na poprzedni
	nowy->liczba  = liczba;                  // zapamietujemy tez liczbe (czyli nasze dane)
	return nowy;                             // zwracamy adres nowego wierzcholka
}

/* Funkcja pop dane z wierzcholka stosu i zwraca je. Wierzcholek stosu jest
 * przy tej operacji usuwany, a caly stos skraca sie o jeden element. Dlatego
 * mozna te funkcje wykorzystac do ostatecznego pobierania informacji ze
 * stosu.
 *
 * int i = get(stos);
 */
int get(Stos *stos){
	int liczba = stos->liczba;   // pobieramy liczbe z wierzcholka stosu
	Stos *s = stos;              // zapamietujemy wierzcholek stosu
	stos = stos->ponizej;        // skracamy stos ustawiajac wierzholek na poprzedni element
	free(s);                     // usuwamy z pamieci stary wierzcholek
	return liczba;               // zwracamy liczbe przechowana w usunietym wierzcholku
}

/* wypisywanie elementow stosu bez jego niszczenia (jak w liscie jednokierunkowej) */
void print(Stos *s){
	Stos *i;
	i = s;
	while(i != NULL){
		printf("%i -> ",i->liczba);
		i = i->ponizej;
	}
	printf("NULL\n");
}

/* rekurencyjne wypisywanie elementow stosu (zapetli sie przy odwolaniach cyklicznych) */
void rprint(Stos *s){
	if(s!=NULL){
		printf("%i -> ",s->liczba);
		rprint(s->ponizej);
	}
	else{
		printf("NULL\n");
	}
}

/* Zdejmowanie wierzcholka stosu poprzez jego odcinanie. Caly wierzcholek staje
 * jest jednoelementowym stosem, a oryginalny stos jest skracany o jeden
 * element.  Pozostala czesc stosu jest skracana i wyprowadzana na zewnatrz
 * funkcji poprzez wskaznik stosu (dlatego jest **stos). */

Stos *pop(Stos **stos){
	Stos *s;             // zmienna do pamietania wierzcholka stosu
	s = *stos;           // zapamietujemy wierzcholek stosu w zmiennej 'gorny'
	*stos = s->ponizej;  // skracamy stos
	s->ponizej = NULL;   // ucinamy ze starego wierzcholka pozostale elementy
	return s;            // zwracamy stary wierzcholek stosu
}

int main(){
	Stos *s,*z;
	s = push(1,NULL); print(s);	rprint(s);
	s = push(2,s);    print(s);	rprint(s);
	s = push(22,s);   print(s); rprint(s);
	z = pop(&s);      print(s); rprint(s); print(z); rprint(z);
	z = push(33,z);   print(s); rprint(s); print(z); rprint(z);
	z = push(44,z);   print(s); rprint(s); print(z); rprint(z);
	return 0;
}