C TIPS: STOG

Stog je struktura koja obično služi za pohranu podataka. Ideja je slijedeća: gurnete jedan objekt na stog, nešto napravite, gurnete drugi objekt na stog, opet nešto radite, uzmete natrag drugi objekt sa stoga, uzmete natrag prvi objekt sa stoga, pa opet nešto stavite na stog, itd. Vjerojatno ste primjetili da objekte vadite sa stoga u suprotnom redoslijedu od onoga kojim su oni stavljani na stog. Stručno govoreći, mehanizam se zove LIFO ("Last in, first out", odnosno u prevodu "zadnji unutra, prvi van"), ili pak FILO (samo okrenite, pa ste opet na istom), važno je samo da termine ne pobrkate sa FIFO ("First in, first out", "prvi unutra, prvi van"), ili pak LILO (jako rijetko, ali znači isto što i prethodno, "Last in, Last out", tj. zadnji unutra, zadnji van). Stog se može iskoristiti na najrazličitije načine. Zamislite samo ovo: imate polje brojeva koje želite sortirati. Nadite u polju najveći i gurnite ga na stog (i maknite iz polja); ponavljajte ovo tako dugo dok ima brojeva u polju. Kada polje ostane prazno, povadite onoliko elemenata sa stoga koliko je elemenata bilo polju i vraćajte ih u polje od prve pozicije na dalje. Što ste dobili? Sortirano polje! Naravno, ima daleko boljih i bržih algoritama za sortiranja, ali tek toliko da spomenem da se i to može stogom. Nadalje, stog je vrlo koristan kod rekurzija, a pogotovo kada rekurzivne funkcije pretvarate u nerekurzivne. Tada se obavezno koristi stog.

IZVEDBE STOGA: POLJE
Jedan od čestih načina kako napraviti stog je pomoću polja. Polje se puni od početka prema kraju, a elementi se vade od kraja prema početku. Za demonstraciju ćemo ilustrirati stog integera. Evo kako bi to izgledalo u C-u:

source kod

int DodajNaStog( int *stog, int *vrh, int max, int podatak ) {
  (*vrh)++;
  if( *vrh >= max ) { (*vrh)--; return 1; }
  stog[*vrh] = podatak;
  return 0;
}

int SkiniSaStoga( int *stog, int *vrh, int *podatak ) {
  if( *vrh < 0 ) return 1;
  *podatak = stog[*vrh];
  (*vrh)--;
  return 0;
}

void main( void ) {
  int stog[20], vrh, max;
  int a,b,c,t;

  max = 20;
  vrh = -1;

  a = 10; b = 15; c = 20;

  printf( "Dodajem %d\n", a );
  DodajNaStog( stog, &vrh, max, a );
  printf( "Dodajem %d\n", b );
  DodajNaStog( stog, &vrh, max, b );
  printf( "Dodajem %d\n", c );
  DodajNaStog( stog, &vrh, max, c );

  SkiniSaStoga( stog, &vrh, &t );
  printf( "Skidam %d\n", t );
  SkiniSaStoga( stog, &vrh, &t );
  printf( "Skidam %d\n", t );
  SkiniSaStoga( stog, &vrh, &t );
  printf( "Skidam %d\n", t );
}

Prvi parametar obje funkcije je polje koje glumi stog. Parametri koji se predaju uz ovaj su i pozicija zadnjeg elementa koji je upisan na stog, te kapacitet stoga. Funkcije su izvedene tako da vračaju pokazatelj uspješnosti izvođenja tražene operacije: 0 ako je operacija uspjela, odnosno 1 ako je došlo do greške. Pogledajmo kako radi funkcija DodajNaStog. Pokazivač vrha stoga povečava se za jedan. Zatim provjeravamo jesmo li prekoračili kapacitet polja. Ako jesmo, vračamo pokazivač vrha stoga na prethodnu vrijednost i prekidamo funkciju sa porukom greške. Inače na stog pohranjujemo dani podatak i vračamo nulu. Funkcija SkiniSaStoga prvo provjerava ima li uopće elemenata na stogu. Ako nema, vrača se poruka greške. Inače se podatak kopira u predanu varijablu, pokazivač vrha stoga se smanjuje za jedan i funkcija vrača nulu kao znak da je podatak uspješno pročitan. U funkciji main krećemo sa deklaracijom polja za stog te varijablama za čuvanje vrha stog i njegove veličine. Zatim deklariramo još tri integera koja ćemo pohraniti na stog, i konačno jedan integer u kojeg ćemo spremati vrijednosti sa stoga. Kapacitet stoga postavljamo na 20, vrh na -1 jer je stog prazan. Funkcijama DodajNaStog dodajemo sva tri elementa na stog, a funkcijama SkiniSaStoga vrijednosti skidamo sa stoga i ispisujemo na ekran. Na ekranu se dobije (prema očekivanjima):

Dodajem 10
Dodajem 15
Dodajem 20
Skidam 20
Skidam 15
Skidam 10

Koristite li u svom programu često ovu strukturu, moram vas upozoriti na dva ozbiljna nedostatka. Prvi vrijedi općenito. Pogledajte deklaracije funkcija za dodavanje i skidanje sa stoga. Prenosi se jako puno suvišnih parametara što usporava program. Ovo treba izbjeći. U nastavku ću pokazati kako. Drugo upozorenje vrijedi ako umjesto integera na stog stavljate veće objekte, poput velikih struktura (typedef struct). Primjetite da funkcija za dodavanje na stog predaje objekt by value. To znači da funkcija prima kopiju cijelog objekta, što je opet loše po vaše performanse. Zato funkciju za dodavanje treba preurediti tako da prima samo adresu onoga što će pohraniti na stog.

POBOLJŠANJA U PRISTUPU

Definirajmo strukturu koja će sve podatke potrebne za funkcioniranje stoga objediniti. Npr.

typedef struct {
  void *stog;           // ovo ce biti polje u koje spremamo podatke
  int max;             // Kapacitet polja
  int vrh;             // Indeks poslijednjeg upisanog objekta
  int objvel;          // Velicina jednog objekta
} TStog;

Ako dobro održavamo ovu strukturu, funkcijama za dodavanje biti će dovoljno predati samo pointer na ovu strukturu jer su u njoj zapisani svi potrebni podaci. Nadalje, prepišimo funkcije za dodavanje tako da znaju iskoristiti ove podatke. I konačno, uvažimo predaju objekata funkcijama preko pokazivača na objekte (by reference), umjesto dosadašnjeg by value. Dobiti ćemo:

// Dodavanje objekta na stog; umjesto objekta predaje se pointer na objekt
int DodajNaVelikiStog( TStog *stog, void *podatak ) {
  stog->vrh++;
  if( stog->vrh >= stog->max ) { stog->vrh--; return 1; }
  memcpy( (char*)stog->stog + stog->vrh*stog->objvel, podatak, stog->objvel );
  return 0;
}

// Uzimanje objekta sa stoga
int SkiniSaStoga( TStog *stog, void *podatak ) {
  if( stog->vrh < 0 ) return 1;
  memcpy( podatak, (char*)stog->stog + stog->vrh*stog->objvel, stog->objvel );
  stog->vrh--;
  return 0;
}

Kod je funkcionalno ostao identičan onome sa početka. Pojavile su se samo neke razlike. Ona koju odmah uočavate je zasigurno poziv funkcije memcpy umjesto klasičnog dodjeljivanja. Razlog ovome je činjenica su funkcije napisane tako da rade sa svim mogućim veličinama objekata, a s druge strane, ta veličina unapred nije poznata. Jedini način kako ovo riješiti je pogledati u strukturu TStog koliko je objekt velik, i onda pozvati funkciju za kopiranje memorije da toliko bajtova prekopira sa stoga u našu varijablu (ili obratno, ovisi o funkciji). I druga izmjena je zamjena poziva by value sa pozivom by reference.

I još se jedna stvar da napraviti. Iako biste mogli TStog inicijalizirati ručno (vidi dolje), ipak bi bilo bolje napisati funkciju koja će to napraviti za nas. Dakle, ovo što slijedi nemojte raditi ukoliko želite imalo čitljiv kod:

void main( void ) {
  double polje[20];
  TStog stog;

  stog.stog = polje;
  stog.max = 20;
  stog.vrh = -1;
  stog.objvel = sizeof(double);

  ...
  // Sada dalje koristiti za funkcije &stog
}

Daleko bi bilo bolje iskoristiti funkcije za kreiranje stoga dinamički (dakle nikakvo double polje[20]!) kao što je dolje prikazano. Dan je i prikaz funkcija za kreiranje i oslobađanje stoga.

// Kreiranje stoga i alociranje potrebne memorije
TStog *KreirajStog( int VelObjekta, int velicina ) {
  TStog *stog;

  stog = malloc(sizeof(TStog));                           // Alociraj jednu strukturu TStog
  if( stog == NULL ) return NULL;
  stog->stog = malloc(VelObjekta*velicina);               // Alociraj polje za stog
  if( stog->stog == NULL ) { free(stog); return NULL; }
  stog->max = velicina;
  stog->vrh = -1;
  stog->objvel = VelObjekta;
  return stog;
}

// Oslobada memoriju zauzetu stogom
void OslobodiStog( TStog *stog ) {
  if(stog==NULL) return;
  if(stog->stog!=NULL) free(stog->stog);
  free(stog);
}

void main( void ) {
  TStog *stog;   // Pointer na stog

  // Kreirajmo stog za 20 objekata
  stog = KreirajStog( sizeof(double), 20 );
  if( stog == NULL ) { printf("Nema dosta memorije.\n"); return; }

  // ....
  // Ovdje nesto raditi sa stogom, sada se funkcijama predaje samo stog a ne &stog
  // ....

  // Oslobodimo stog
  OslobodiStog( stog );
}

source kod

Ono što se može raditi sa stogom su naravno pozivi funkcija DodajNaVelikiStog i SkiniSaStoga i to poslijednje dvije implementacije (ne one sa samoga pocetka vec one koje smo modificirali!).

Još da spomenem nedostatak ovakve izvedbe stoga: nepromjenjiv kapacitet. Zapravo, ovo bi se moglo eliminirati tako da kada se otkrije da je stog pun pokušamo realocirati stog za veči kapacitet, pa ga poslije smanjivati kada se dovoljno isprazni. No to se ne radi tako. Ako je potreban dinamički stog (pogotovo za veče strukture podataka), tada se stog može napraviti na slijedeči način:

IZVEDBE STOGA: LISTA

Eh, da. Još jednom sve iz početka. Prvo, ako ne razumijete liste, pročitajte si tekst C Tips: Liste. Onda nastavite čitati dalje. Ja ću u nastavku za ostvarivanje stoga koristiti slijedeću strukturu člana liste:

typedef struct SCvorStogListe {
  struct SCvorStogListe *Prethodni;
  char x;
} StogLista;

Kako vidite, koristiti ćemo jednostruko povezanu listu, ali povezanu unatrag. Razlog ovome je taj što implementacija funkcija za dodavanje i skidanje na stog ne zahtjeva slijedeći čvor, već samo prethodni. Stoga je razumno ono što ne koristimo izbaciti van! Osim ovoga uočite i član nazvan x, tipa char, odnosno zauzeća 1 bajt. Čemu on služi? Pa lista osim svog uređenja treba sadržavati i nekakve podatke. Na početku strukture nalazi se pokazivač na prethodni čvor. Iza toga slijedi mjesto za podatke. Prvi bajt tih podataka upravo je x. I ne dajte se prevariti. Nećemo pamtiti samo jedan podatak. Uzmimo npr. da želimo pohraniti jedan double. Tada bi umjesto char x trebalo stajati double x. Zatim bismo alocirali jednu takvu strukturu i dodali je u listu. No ako piše char x, kao kod nas, tada je očito da nam je struktura premala. Koliko? Pa sizeof(double)-sizeof(char) tj. 8-1 što je 7 bajtova manjka. Da li je to problem? Pa zapravo i nije. Kada ćemo alocirati strukturu, umjesto malloc(sizeof(StogLista)) koristiti ćemo malloc(sizeof(StogLista)+sizeof(double)-1). Ovime smo dobili strukturu koja je upravo dovoljno velika da zapamti naš double! Kako ćemo ga pohraniti? Pa početak mu je tamo gdje se nalazi x. Zbog toga sve što trebamo učiniti je uzeti adresu od x, ukalupiti je u pointer na double (što možemo jer smo si alocirali dovoljno memorije u strukturi!), i zatim preko pointera dodijeliti vrijednost! Zbog toga što funkcije pišemo tako da rade sa proizvoljnim veličinama objekata, umjesto dodjeljivanja koristiti ćemo funkciju za kopiranje memorije memcpy. Nadalje, da bi funkcije znale kako dodavati i skidati sa stoga, potreban im je pokazivač na listu, te informacija o veličini objekta. To su već dva podatka. Poučeni iskustvom iz prethodno opisane izvedbe stoga preko polja, sve te podatke potrpati ćemo u jednu strukturu pa funkcijama za dodavanje i skidanje predavati samo pointer na tu strukturu u kojoj su sadržani svi relevantni podaci za rad obiju funkcija. Strukturu ćemo nazvati TDStog (D od dinamičkog, da ga ne miješamo sa gornjom deklaracijom statičkog stoga). I opet ćemo napisati i funkcije za kreiranje te strukture te za brisanje te strukture. Pogledajmo prvo kako izgleda deklaracija same TDStog strukture te funkcija za njezino kreiranje i brisanje:

typedef struct {
  StogLista *stog;  // lista
  int objvel;       // velicina objekta
} TDStog;

TDStog *KreirajDinStog( int velicina_objekta ) {
  TDStog *stog;

  stog = malloc( sizeof(TDStog) );
  if( stog == NULL ) return NULL;
  stog->stog = NULL;
  stog->objvel = velicina_objekta;
  return stog;
}

void OslobodiDinStog( TDStog *stog ) {
 void *podatak;

 if( stog == NULL ) return;

 if( stog->stog != NULL ) {
  podatak = malloc( stog->objvel);
  while(!SkiniSaDinStog(stog,podatak));
 }
 free(stog);
}

Kako vidite, struktura TDStog pamti samo pokazivač na listu i veličinu objekta. Podatak o maksimalnom kapacitetu i trenutnom vrhu stoga nema potrebe pamtiti eksplicitno preko još dva parametra. Razlog tomu je da kapacitet stoga ovisi samo o količini slobodne memorije pa ne možemo fiksno odrediti kapacitet, a i ne želimo fiksan kapacitet! S sdruge strane, podatak o vrhu stoga pamti se preko same liste jer ona uvjek pokazuje na vrh stoga, a ne na prvi alocirani element! Zato i koristimo umjesto Slijedeći član pokazivač Prethodni član da bismo znali ići prema početku. Funkcija KreirajDinStog alocira mjesto za jednu TDStog strukturu, te inicijalizira listu na praznu, i veličinu objekta na predanu veličinu. Ukoliko je alokacija uspjela, vrača se pokazivač na strukturu, inaće se vrača NULL. Funkcija za oslobađanje stoga OslobodiDinStog prije samog oslobađanja strukture TDStog mora provjeriti je li lista prazna. Ako nije, treba i nju osloboditi. Za oslobađanje liste kreira se mjesto za jedan objekt stoga, i poziva se funkcija SkiniSaDinStog tako dugo dok ima elemenata na stogu. Onog trena kada nestane elemenata, znači da je i lista nestala! Na taj način oslobođena je lista, pa se konačno oslobađa i TDStog struktura. I time je funkcija gotova. Sada ćemo pokazati kako trebaju izgledati funkcije za dodavanje na stog i skidanje sa stoga:

int DodajNaDinStog( TDStog *stog, void *Podatak ) {
  StogLista *Element;

  Element = malloc(sizeof(StogLista)-1+stog->objvel);
  if( Element == NULL ) return 1;
  memcpy( &Element->x, Podatak, stog->objvel );
  DodajUListu( &stog->stog, Element );
  return 0;
}

int SkiniSaDinStog( TDStog *stog, void *Podatak ) {
  StogLista *Element;

  Element = SkiniIzListe( &stog->stog );
  if( Element == NULL ) return 1;
  memcpy( Podatak, &Element->x, stog->objvel );
  free(Element);
  return 0;
}

Funkcija DodajNaDinStog prvo alocira jedan čvor za listu. Uočite več prije opisan način izračuna potrebne memorije za strukturu malloc(sizeof(StogLista)-1+stog->objvel). Provjeravamo je li alokacija uspjela i u slučaju neuspjeha vračamo 1 kao znak greške. Inače kopiramo predani podatak na odgovarajuće mjesto u strukturi (sjećate se, prvi bajt počinje na x, pa zato uzimamo adresu od x i kopiramo od te adrese na dalje). Konačno tako dobiveni čvor liste dodajemo u listu pozivom funkcije DodajUListu čiju ćemo implementaciju pokazati malo kasnije, te vračamo 0 kao znak uspjeha. Funkcija SkiniSaDinStog radi upravo obratnim redoslijedom. Prvo se sa liste uzme zadnji dodani element pozivom SkiniIzListe funkcije i provjerava se je li skidanje uspjelo. Ako nije, znači da lista više nema elemenata, tj. da je stog prazan, pa vračamo 1 i završavamo funkciju. Inače, kopiramo podatke natrag u predanu varijablu, oslobađamo memoriju zauzetu čvorom koji je čuvao podatke i vračamo 0 kao znak uspješnosti funkcije. Još nam je ostalo da pogledamo i funkcije za dodavanje u listu i brisanje iz liste.

void DodajUListu( StogLista **Lista, StogLista *Clan ) {
  Clan->Prethodni = *Lista;
  (*Lista) = Clan;
}

StogLista *SkiniIzListe( StogLista **Lista ) {
  StogLista *t;

  if( *Lista == NULL ) return NULL;
  t = *Lista;
  *Lista = (*Lista)->Prethodni;
  return t;
}

Source kod

Funkcija DodajUListu kreće od jednostavne pretpostavke. Ono što se preda kao pokazivač na listu nije pokazivač na prvi element liste, već je pokazivač na zadnji element liste. Tada je dodavanje u listu jako jednostavno. Čvor koji dodajemo postati će zadnji čvor. Njegov prethodni čvor je onda dosadašnji zadnji čvor liste a to je upravo *Lista. Ovime je zadnji čvor liste i službeno postao cvor Clan. No kako *Lista mora pokazivati na zadnji član (a trenutno pokazuje na predzadnji), vršimo i tu korekciju drugom naredbom: (*Lista) = Clan. Ovime smo opet očuvali pretpostavku uređenosti liste: *Lista opet pokazuje na zadnji element! I funkcija za skidanje iz liste SkiniIzListe koristi tu preptostavku. Prvo se provjerava je li lista prazna. Ako je, vrača se NULL i izlazi se iz funkcije. Inače, kako je *Lista pokazivač na zadnji član liste, njega upravo trebamo skinuti! Zato ga pospremamo u pomočnu varijablu t, a pokazivač *Lista korigiramo tako da pokazuje ponovno na zadnji element, koji je sada (*Lista)->Prethodni. Uočite da ako je dotični element bio jedini u listi, tada smo ovime pokazivač *Lista automatski postavili na NULL jer je prethodni element prvog elementa očito NULL!

STOG ZA VARIJABILNE VELIČINE OBJEKATA

Recimo da na stog želite pospremati stringove. Naravno da je to jedan od najopćenitijih tipova podataka koji može biti dugačak od jednog znaka do cijelog teksta neke npr. pjesme ili slično. Tada naravno nećete za svaki element stoga alocirati po megabajt jer to jednostavno nema smisla. Za tu svrhu biti će potrebno samo malo modificirati naše rutine. Primjer će biti dan za dinamički stog, no i za statički se na identičan način može postići isto.

typedef struct SCvorStogListeV {
  struct SCvorStogListeV *Prethodni;      // ovo je isto kao i prije
  char *x;                                // umjesto jednog bajta, treba nam pointer
} StogListaV;

typedef struct {
  StogListaV *stog;  // lista
} TDVStog;

// Ovo je ostalo identicno! Bez promjena
void DodajUListuV( StogListaV **Lista, StogListaV *Clan ) {
  Clan->Prethodni = *Lista;
  (*Lista) = Clan;
}

// Ovo je ostalo identicno! Bez promjena
StogListaV *SkiniIzListeV( StogListaV **Lista ) {
  StogListaV *t;

  if( *Lista == NULL ) return NULL;
  t = *Lista;
  *Lista = (*Lista)->Prethodni;
  return t;
}

int DodajNaDinStogV( TDVStog *stog, char *Podatak ) {
  StogListaV *Element;
  int Duljina;

  Element = malloc(sizeof(StogListaV));                   // Alociramo tocno jednu strukturu
  if( Element == NULL ) return 1;
  Duljina = strlen(Podatak)+1;
  Element->x = malloc(Duljina);                           // Alociramo buffer za string
  if(Element->x==NULL) { free(Element); return 1; }       // Neuspjeh? Van!
  strcpy(Element->x,Podatak);                             // Kopiraj u buffer
  DodajUListuV( &stog->stog, Element );                   // Dodaj u listu
  return 0;
}

int SkiniSaDinStogV( TDVStog *stog, char *Podatak ) {
  StogListaV *Element;

  Element = SkiniIzListeV( &stog->stog );                 // Uzmi element
  if( Element == NULL ) return 1;
  strcpy( Podatak, Element->x);                           // Iskopiraj iz buffera
  free(Element->x);                                       // Oslobodi buffer
  free(Element);                                          // Oslobodi strukturu
  return 0;
}

// Ovo je novo
int DajPotrebnuVelicinu( TDVStog *stog ) {
  if( stog->stog == NULL ) return -1;
  return strlen(stog->stog->x )+1;                        // Vrati duljinu podatka sa stoga
}

// Ostalo isto; samo je izbacen objvel podatak koji se ne koristi
TDVStog *KreirajDinStogV(void) {
  TDVStog *stog;

  stog = malloc( sizeof(TDVStog) );
  if( stog == NULL ) return NULL;
  stog->stog = NULL;
  return stog;
}

// Malo modificirano, vidi opis dolje
void OslobodiDinStogV( TDVStog *stog ) {
 char *podatak;
 int pv;

 if( stog == NULL ) return;

 while(-1!=(pv=DajPotrebnuVelicinu(stog))) {             // Ponavljaj dok ima elemenata
  podatak = malloc(pv);                                  // Alociraj potreban buffer
  SkiniSaDinStogV(stog,podatak);                         // Skini podatak
  free(podatak);                                         // Oslobodi buffer
 }
 free(stog);                                             // Oslobodi stog
}

// Jedan primjer uporabe funkcija
void main( void ) {
  char a[] = "Ivo";      // Tri podatka, a, b i c
  char b[] = "Pero";
  char c[] = "Antimon";
  TDVStog *stog;         // Dinamicki varijabilni stog
  int pv;                // Pomocna varijabla za velicinu buffera
  char *buff;            // Pokazivac na buffer

  clrscr();

  // Kreiranje stoga
  stog = KreirajDinStogV();
  if( stog == NULL ) { printf("Nema dovoljno memorije.\n"); return; }

  // Dodavanje podataka
  printf( "Dodajem podatak: %s, duljina podatka je %d\n", a, strlen(a)+1 );
  DodajNaDinStogV( stog, a );
  printf( "Dodajem podatak: %s, duljina podatka je %d\n", b, strlen(b)+1 );
  DodajNaDinStogV( stog, b );
  printf( "Dodajem podatak: %s, duljina podatka je %d\n", c, strlen(c)+1 );
  DodajNaDinStogV( stog, c );

  // Praznjenje cijeloga stoga
  while( -1 != ( pv = DajPotrebnuVelicinu(stog) ) ) {
    buff = (char*)malloc( pv );
    if( buff != NULL ) {
     SkiniSaDinStogV( stog, buff );
     printf( "Skinut podatak: %s, duljina buffera %d\n", buff, pv );
     free(buff);
    } else printf("Nema dovoljno memorije za podatak.\n");
  }

  // Oslobadanje stoga
  OslobodiDinStogV( stog );
}

source kod

Što je novo? Iz strukture za stog izbačen je element objvel jer ga ne trebamo. Struktura čvora modificirana je utoliko što je char x prešao u char *x. Sjećate se, pamtimo string, tj char *x. Funkcija za dodavanje u listu i brisanje sa liste ostale su potpuno iste. Dodavanje na stog izmjenjeno je utoliko što uz alokaciju same strukture čvora alocira i dodatni buffer za string koji pamtimo, te u njega kopira predani string, a sve se pamti upravo preko char *x koji predstavlja pointer na alocirani buffer. I primjetite da sada ne alociramo niti bajta više nego što ga zauzima sama struktura. To je tako jer podatak pamtimo u zasebnom bufferu. Funkcija za skidanje sa dinamičkog stoga gotovo da je ostala nepromjenjena. Jedina izmjena je ta da se podatak kopira iz alociranog buffera, te se i taj buffer naknadno oslobađa. Dodana je jedna nova funkcija: DajPotrebnuVelicinu, koja provjeri ima li na stogu koji podatak. Ako ima, onda vrati duljinu potrebnog buffera koji može pohraniti onaj podatak koji će biti prvi skinut sa stoga; ako podataka nema, funkcija vrača -1. Kreiranje stoga ostalo je nepromjenjeno ( osim izbačene inicijalizacije objvel člana). Oslobađanje stoga za pražnjenje liste ulazi u vhile petlju pozivajuči za svaki član funkciju DajPotrebnuVelicinu da bi znala koliki buffer treba alocirati. Tek zatim se alocira buffer, skida se podatak, te se buffer oslobađa, i tako sve dok ima podataka. Kada je lista prazna, stog se oslobađa. Funkcija main daje jedan primjer kako ovo sve iskoristiti.

JOŠ MALO PA KRAJ

Ne, neću više ništa novoga reći o stogu. Ali jedna napomena. Budući da je ovaj tekst pisan jako opširno, tekst o strukturi zvanoj red oslanjati će se na dijelove ovoga teksta zbog toga što se red može implementirati na identične načine kao i stog. Razlika je utolika što struktura red radi na principu FIFO (prvi unutra, prvi van) za razliku od stoga koji je primjer LIFO strukture (zadnji unutra, prvi van). Dakle promjeniti će se samo funkcije za ubacivanje i skidanje sa liste (ili polja ako je statička struktura). Funkcija DodajNaStog, SkiniSaStoga, DajPotrebnuVelicinu i sve ostalo ostaje nepromjenjeno!

Zagreb, 13. veljače 1999.