2. diel - Implementácia zásobníka v jazyku C

V minulej lekcii, Úvod do kolekcií a dátových štruktúr v jazyku C , sme si uviedli kolekcie a implementovali zásobník (stack).

Dnes dokončíme našu implementáciu zásobníka (LIFO).

Naša jednoduchá implementácia zásobníka z minula používala globálnej premennej header, ktorá ukazovala na vrchol zásobníka. Hovorili sme si, že to nie je úplne šťastné riešenie a že kolekciu dnes ešte vylepšíme. Najskôr ale vysvetlenie, prečo je používanie globálne premenné header nesprávne.

Problém globálne premenné

Ak by sme náš zásobník používali takto, fungoval by, ale mohli by sme v každom programe použiť len jeden zásobník. Pre pochopenie princípu kolekcia to stačilo, ale poďme to urobiť lepšie. Vrchol zásobníka si budeme ukladať lokálne a každej funkcii ho odovzdáme parametrom. Tak zásobníkov môžeme mať neobmedzené množstvo.

push()

Funkciu push() zmeníme nasledovne:

struct ITEM* push( struct ITEM **header, int new_number)
{
    struct ITEM* new_item = (struct ITEM*)malloc(sizeof(struct ITEM));
    if (new_item == NULL)
        return NULL;
    new_item->number = new_number;
    new_item->next = NULL;
    new_item->next = *header;
    *header = new_item;
    return new_item;
}

Funkciu pribudol jeden parameter, header. Tento parameter je v podstate reprezentant zásobníku, iba cez neho sa k zásobníku dostaneme. V pamäti vyzerá situácia nasledovne:

Tie dve hviezdičky pred parametrom sú síce zvláštne, ale hovoria, že je to ukazovateľ na ukazovateľ na položku ITEM. Ak je pre vás syntaxe ukazovateľov cudzie, veľmi odporúčam prvýkrát prejsť kurz Dynamická práca s pamäťou v jazyku C.

Reťazenie ukazovateľov je tu nutné, pretože vrchol zásobníka sa vo funkciách push() a pop() mení, keď sa položka pridáva alebo odoberá. A keby sme si odovzdali iba ukazovateľ na hodnotu vrchole, nemohli by sme samotný lokálny ukazovateľ, ktorý používa používateľ kolekcie, upraviť, a ukazoval by na starú adresu.

Okrem parametra sa zmenili iba dva riadky, v ktorých pribudli dve hviezdičky.

pop()

Vo funkcii pop() zas pribudol iba jeden nový parameter, štyri hviezdičky a dve zátvorky:

struct ITEM* pop( struct ITEM **header )
{
    struct ITEM* old_item;
    if (*header == NULL)
        return NULL;
    old_item = *header;
    *header = (*header)->next;
    return old_item;
}

Ide len o to, že parameter ukazuje na ukazovateľ na vrchol zásobníka.

peek()

Podobne vo funkcii peek() je len jednoduchá úprava:

struct ITEM* peek( struct ITEM *header )
{
    return header;
}

Ono to vyzerá absurdne, že vrátime to, čo posielame, v neskorších lekciách si to vysvetlíme. Keďže funkcia peek() v zásobníku nič nemení, stačí nám len odkaz na vrchol zásobníka.

print_collection()

V print_collection() pribudne parameter, ukazovateľ na vrchol zásobníka. Podobne ako peek() funkcia nič nemení, tak stačí len odkaz na vrchol zásobníka:

void print_collection( struct ITEM* header)
{
    int i = 1;
    struct ITEM* item;
    printf("PRINT COLLECTION START:\r\n");
    item = header;
    while (item != NULL)
    {
        printf("%2d: %4d\r\n", i, item->number);
        i++;
        item = item->next;
    }
    printf("PRINT COLLECTION END.\r\n");
}

main()

Ale vo funkcii main() toho musíme zmeniť veľa. Miesto ukazovatele na vrchol zásobníka totiž musíme zadať adresu ukazovatele na vrchol zásobníka:

int main()
{
    struct ITEM* zasobnik = NULL;
    struct ITEM* polozka = NULL;
    push( &zasobnik, 11 );
    push( &zasobnik, 7 );
    push( &zasobnik, 8 );
    print_collection(zasobnik);
    polozka = pop(&zasobnik);
    if( polozka != NULL)
    {
        printf("Item from stack: %d\r\n", polozka->number);
        free(polozka);
    }
    else
    {
        printf("Stack is empty\r\n");
    }
    push(&zasobnik, -88);
    push(&zasobnik, 100);
    print_collection(zasobnik);
    free( pop(&zasobnik) );
    pop(&zasobnik);
    print_collection(zasobnik);
    free( pop(&zasobnik) );
    free(pop(&zasobnik));
    if( pop(&zasobnik) == NULL )
    {
        printf("Stack is empty\r\n");
    }
    print_collection(zasobnik);
    getchar();
    return 0;
}

Premenná zasobnik je ukazovateľ na vrchol zásobníka. Do funkcií push(), pop() a print_collection() odovzdávame adresu tohto ukazovateľa &zasobnik. Takto si môžeme vytvoriť ľubovoľné množstvo zásobníkov a pristupovať k nim.

Nové funkcie

Naši implementáciu zásobníka môžeme dokončiť ešte pridaním dvoch jednoduchých, ale užitočných funkcií.

empty()

Funkcia empty() vráti 1, ak je zásobník prázdny a 0, ak má aspoň jednu položku:

int empty(struct ITEM* header )
{
    if (header == NULL)
        return 1;
    else
        return 0;
}

length()

Funkcia length() vráti počet položiek v zásobníku:

int length(struct ITEM* header)
{
    int counter_item = 0;
    struct ITEM* item;
    item = header;
    while (item != NULL)
    {
        counter_item++;
        item = item->next;
    }
    return counter_item;
}

Funkcia prechádza od vrcholu zásobníka po jeho dno a pri každom priechode zvýši counter_item o jedna. Nakoniec funkcie counter_item vráti ako návratovú hodnotu.

Zásobník je k stiahnutiu v prílohe nižšie.

V budúcej lekcii, Implementácia fronty v jazyku C , budeme implementovať jednoduchú front v jazyku C.

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.