Ред

Ред (енгл. queue) је структура која функционише на принципу FIFO (first in, first out). Код ове технике податак који се први дода, први се и избацује.

Редови се користе за обраду процеса или догађаја који се извршавају према редоследу доласка. На пример, ред чекања у продавници или на шалтеру у банци.

У рачунарству редови имају велику примену у разним алгоритмима и процесима, приликом коришћења процесора и меморије, у улазно-излазним операцијама и многим другим.

Ред има две основне операције:

• додај у ред (енгл. add) додаје елемент на крај реда, и

• скини из реда (енгл. get) скида елемент са почетка реда.

И ред се може имплементирати коришћењем низа. Додавање елемента у ред одговара операцији додавања елемента на крај низа, а скидање из реда брисању првог елемента низа.

Ако користимо листу, да би се остварило додавање, поред показивача на почетак реда чува се и показивач на крај реда.

Као и у досадашњем излагању, на почетку ћемо дефинисати структуру која садржи податак и адресу следећег елемента:

#include<stdio.h>
#include<stdlib.h>
typedef struct lista 
{
    int podatak;
    struct lista* sl_adresa;
} Lista;

Додавање елемената у ред

Рекли смо да се код редова елемент ставља на крај реда. Поступак додавања елемената у ред се назива Enqueue. Овако се често назива функција за додавање елемента у ред у многим програмским језицима.

Функција садржи показивач на показивач на листу Lista, и то за први и последњи елемент реда. Ови показивачи ће ажурирати своје вредности ако ред није празан.

Меморија се додељује новом чвору помоћу функције malloc. У случају да додела није успела, програм се прекида.

Ако је последњи показивач NULL, ред је празан. Тада се постављају prvi и poslednji да буду показивач на нови чвор.

Ако ред није празан, тада се поље sl_adresa последњег чвора поставља да показује на нови чвор. На тај начин се додаје чвор на крај реда.

void dodaj_u_red(Lista** prvi, Lista** poslednji, int vrednost) 
{
    Lista* novi;
    novi = (Lista*)malloc(sizeof(Lista));
    if (novi == NULL) 
    {
        printf("Greska pri alokaciji memorije\n");
        exit(0);
    }
    novi->podatak = vrednost;
    novi->sl_adresa = NULL;
    if (*poslednji == NULL) 
    {
        *poslednji = novi;
        *prvi = *poslednji;
    }
    else 
    {
        (*poslednji)->sl_adresa = novi;
        *poslednji = novi;
    }
}

Брисање елемента из реда

Функција за брисање елемента из реда уклања први елемент из листе. Поступак скидања елемената из реда се назива dequeue. Овако се често назива функција за брисање елемента из реда у многим програмским језицима.

Ако је ред празан, и први и последњи показивач показују на NULL и исписује се порука о грешци. Након избацивања елемента, показивачи prvi и poslednji се ажурирају. Вредност избаченог елемента се враћа преко показивача vrednost.

Привремени показивач temp на почетку се поставља да буде исти као први. Затим се показивач prvi ажурира да показује на следећи елемент у реду. Тада се из реда уклања први елемент.

Ако је последњи показивач био исти као temp, то значи да је био само један елемент у реду и да је ред сада празан. Ажурира се последњи показивач на NULL, јер је ред празан.

void skini_iz_reda(Lista** prvi, Lista** poslednji, int* vrednost)
{
    Lista* temp;
    if ((*prvi == *poslednji) && (*poslednji == NULL))
    {
        printf("Red je prazan!");
        exit(0);
    }
    *vrednost = (*prvi)->podatak;
    temp = *prvi;
    *prvi = (*prvi)->sl_adresa;
    if (*poslednji == temp)
        *poslednji = (*poslednji)->sl_adresa;
    free(temp);
}

Испис елемената реда

Функција за исписивање елемената реда не разликује се од до сада обрађених функција за испис елемената листе. Пролаз кроз ред се врши помоћу показивача tekuci који на почетку добија вредност показивача на први елемент. Вредности ће се исписивати све док се не стигне до краја реда.

void ispis_reda(Lista* prvi)
{
    Lista* tekuci;
    tekuci = prvi;
    while (tekuci != NULL)
    {
        printf("%d\t", tekuci->podatak);
        tekuci = tekuci->sl_adresa;
    }
    printf("\n");
}

Брисање свих елемената из реда

Приликом брисања свих елемената реда се унутар петље креира привремени показивач temp и поставља на тренутни елемент на који показује tekuci. Показивач се ажурира да показује на следећи елемент, а меморија коју алоцира temp се брише. На тај начин се елемент уклања из реда. Петља се наставља све док се не дође до краја, односно док сви елементи у реду не буду обрисани.

На крају оба показивача, и prvi и poslednji, добијају вредност NULL, што је знак да је ред обрисан.

void obrisi_red(Lista** prvi, Lista** poslednji)
{
    Lista* trenutni = *prvi;
    while (trenutni != NULL) 
    {
        Lista* tmp = trenutni;
        trenutni = trenutni->sl_adresa;
        free(tmp);
    }
    *prvi = NULL;
    *poslednji = NULL;
}

Користећи претходно креиране функције, написати програм за симулацију основних операција у раду са редом.

Главни програм:

void dodaj_u_red(Lista** prvi, Lista** poslednji, int vrednost);
void skini_iz_reda(Lista** prvi, Lista** poslednji, int* vrednost);
void ispis_reda(Lista* prvi);
void obrisi_red(Lista** prvi, Lista** poslednji);

int main(void)
{
    Lista* prvi = NULL, * poslednji = NULL;
    int n, vrednost, i;
    printf("Unesi broj elemenata reda:\n");
    scanf("%d", &n);
    for (i = 0;i < n;i++)
    {
        printf("Unesite %d. element u red: ", i + 1);
        scanf("%d", &vrednost);
        dodaj_u_red(&prvi, &poslednji, vrednost);
    }
    printf("Elementi reda su:\n");
    ispis_reda(prvi);
    for (i = 0;i < n;i++)
    {
        printf("Brisi element reda");
        skini_iz_reda(&prvi, &poslednji, &vrednost);
        printf("\n");
        ispis_reda(prvi);
    }
    return 0;
}

Резултат извршавања програма:

Unesi broj elemenata reda:
5
Unesite 1. element u red: 3
Unesite 2. element u red: 7
Unesite 3. element u red: 1
Unesite 4. element u red: 9
Unesite 5. element u red: 15
Elementi reda su:
3       7       1       9      15
Brisi element reda
7       1       9      15
Brisi element reda
1       9      15
Brisi element reda
9      15
Brisi element reda
15