Lekce 2 - Implementace zásobníku v jazyce C

V minulé lekci, Úvod do kolekcí a datových struktur v jazyce C, jsme si uvedli kolekce a implementovali zásobník (stack).

Dnes dokončíme naši implementaci zásobníku (LIFO).

Naše jednoduchá implementace zásobníku z minula používala globální proměnnou header, která ukazovala na vrchol zásobníku. Říkali jsme si, že to není úplně šťastné řešení a že kolekci dnes ještě vylepšíme. Nejdříve ale vysvětlení, proč je používání globální proměnné header nesprávné.

Problém globální proměnné

Pokud bychom náš zásobník používali takto, fungoval by, ale mohli bychom v každém programu použít pouze jeden zásobník. Pro pochopení principu kolekce to stačilo, ale pojďme to udělat lépe. Vrchol zásobníku si budeme ukládat lokálně a každé funkci ho předáme parametrem. Tak zásobníků můžeme mít neomezené množství.

push()

Funkci push() změníme takto:

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;
}

Funkci přibyl jeden parametr, header. Tento parametr je v podstatě reprezentant zásobníku, pouze přes něj se k zásobníku dostaneme. V paměti vypadá situace následovně:

Ty dvě hvězdičky před parametrem jsou sice zvláštní, ale říkají, že je to ukazatel na ukazatel na položku ITEM. Pokud je pro vás syntaxe ukazatelů cizí, velmi doporučuji prvně projít kurz Dynamická práce s pamětí v jazyce C.

Řetězení ukazatelů je zde nutné, protože vrchol zásobníku se ve funkcích push() a pop() mění, když se položka přidává nebo odebírá. A kdybychom si předali pouze ukazatel na hodnotu vrcholu, nemohli bychom samotný lokální ukazatel, který používá uživatel kolekce, upravit, a ukazoval by na starou adresu.

Kromě parametru se změnily pouze dva řádky, v nichž přibyly dvě hvězdičky.

pop()

Ve funkci pop() zas přibyl pouze jeden nový parametr, čtyři hvězdičky a dvě závorky:

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

Jde pouze o to, že parametr ukazuje na ukazatel na vrchol zásobníku.

peek()

Podobně ve funkci peek() je pouze jednoduchá úprava:

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

Ono to vypadá absurdně, že vrátíme to, co posíláme, v pozdějších lekcích si to vysvětlíme. Jelikož funkce peek() v zásobníku nic nemění, stačí nám pouze odkaz na vrchol zásobníku.

print_collection()

V print_collection() přibude parametr, ukazatel na vrchol zásobníku. Podobně jako peek() funkce nic nemění, tak stačí pouze odkaz na vrchol zásobníku:

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 ve funkci main() toho musíme změnit hodně. Místo ukazatele na vrchol zásobníku totiž musíme zadat adresu ukazatele na vrchol zásobníku:

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;
}

Proměnná zasobnik je ukazatel na vrchol zásobníku. Do funkcí push(), pop() a print_collection() předáváme adresu tohoto ukazatele &zasobnik. Takto si můžeme vytvořit libovolné množství zásobníků a přistupovat k nim.

Nové funkce

Naši implementaci zásobníku můžeme dokončit ještě přidáním dvou jednoduchých, ale užitečných funkcí.

empty()

Funkce empty() vrátí 1, pokud je zásobník prázdný a 0, pokud má alespoň jednu položku:

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

length()

Funkce length() vrátí počet položek 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;
}

Funkce prochází od vrcholu zásobníku po jeho dno a při každém průchodu zvýší counter_item o jedna. Nakonec funkce counter_item vrátí jako návratovou hodnotu.

Zásobník je ke stažení v příloze níže.

V příští lekci, Implementace fronty v jazyce C, budeme implementovat jednoduchou frontu v jazyce C.

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.