Red (Queue)

Red (queue) je osnovna struktura podataka koja spada u linearne strukture i funkcioniše po principu FIFO (First In – First Out). To znači da se element koji je prvi ubačen u red prvi i izbacuje iz njega.

Zbog očuvanja redosleda obrade, red se često koristi u programiranju i algoritmima, posebno kod BFS obilaska grafova, simulacija procesa i obrade zadataka u operativnim sistemima.

U ovoj lekciji biće objašnjene osnovne operacije nad redom, njegova implementacija u jeziku C++ i veza sa algoritmima nad grafovima i stablima.

Osnovna ideja reda

Red je struktura podataka koja omogućava obradu elemenata isključivo u redosledu njihovog dolaska. Korisnik nema slobodan pristup elementima u sredini ili na kraju reda, već može raditi samo sa elementom na početku.

Za razliku od steka, gde se pristupa poslednjem dodatom elementu, red garantuje pravednu obradu podataka po FIFO principu.

Primer iz svakodnevnog života je red u banci – osoba koja prva stane u red, prva dolazi na šalter, bez obzira na to ko dolazi kasnije.

Osnovne operacije nad redom

• enqueue – dodavanje elementa na kraj reda
• dequeue – uklanjanje elementa sa početka reda
• front – pristup prvom elementu reda
• empty – provera da li je red prazan

Sve osnovne operacije nad redom imaju vremensku složenost O(1).

Automatski rad reda kroz primer koda

U ovom primeru prati se izvršavanje jednostavnog koda i automatski se prikazuje stanje reda (queue) nakon svake operacije. Red funkcioniše po principu FIFO.

1  enqueue(1)
2  enqueue(2)
3  dequeue()
4  enqueue(3)

Interaktivni zadatak: Pogodi ispis (Red)

Posmatraj sledeći kod koji koristi red (queue). Pre nego što klikneš na dugme, pokušaj da predvidiš ispis.

enqueue(10);
enqueue(20);
enqueue(30);
cout << dequeue() << " ";
enqueue(40);
cout << dequeue();

Šta će biti ispisano?

Kako razmišljati?
Red radi po principu prvi ušao – prvi izašao (FIFO). Svaki dequeue() uklanja i vraća element sa početka reda, dok enqueue() dodaje element na kraj reda.

Mini uporedni zadatak: Stek vs Red (vizuelno)

Isti niz operacija primenjuje se nad stek i nad redom. Pokušaj da predvidiš ispis, a zatim proveri rezultat i pogledaj kako se strukture razlikuju.

add(1)
add(2)
add(3)
print(remove())
add(4)
print(remove())

Napomena:

• Stek: add = push, remove = pop
• Red: add = enqueue, remove = dequeue

C++ STL – konkretne metode za std::queue

U C++ standardnoj biblioteci (``) postoji klasa std::queue koja implementira red (queue) koristeći unutrašnju strukturu kao što je deque ili list. Ovo omogućava jednostavnu upotrebu reda bez ručne implementacije. Slede glavne metode:

• push(x) – dodaje element na kraj reda (odgovara enqueue)
• pop() – uklanja element sa početka reda (odgovara dequeue, ne vraća vrednost)
• front() – pristupa prvom elementu reda, bez uklanjanja
• back() – pristupa poslednjem elementu reda, bez uklanjanja
• empty() – vraća true ako je red prazan
• size() – vraća broj elemenata u redu
• emplace(...) – direktno konstruiše element na kraju reda (C++11+)
• swap(q2) – zamena sadržaja dva reda

Napomena: std::queue ne podržava direktan pristup elementima po indeksu i nema iteratore, jer je apstraktna struktura tipa FIFO.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue q;

    // Dodavanje elemenata (enqueue)
    q.push(10);
    q.push(20);
    q.push(30);

    // Pristup prvom i poslednjem elementu
    cout << "Prvi: " << q.front() << ", Poslednji: " << q.back() << endl;

    // Uklanjanje elementa sa početka (dequeue)
    q.pop();

    cout << "Nakon pop, prvi element: " << q.front() << endl;

    // Provera veličine i da li je red prazan
    cout << "Veličina: " << q.size() << ", Prazan? " << q.empty() << endl;

    return 0;
}

Ovaj primer pokazuje praktičnu upotrebu reda u C++ STL-u i povezuje apstraktne operacije enqueue/dequeue sa realnim metodama push/pop.

Implementacija reda pomoću niza

Jednostavna implementacija reda može se ostvariti pomoću niza i dva indeksa: jedan pokazuje na početak reda, a drugi na kraj reda.

#include <iostream>
using namespace std;

// Maksimalna veličina niza za red
const int MAX = 100;

// Niz koji čuva elemente reda
int red[MAX];

// Indeksi početka i kraja reda
int pocetak = 0, kraj = 0;

// Provera da li je red prazan
bool empty() {
    return pocetak == kraj;
}

// Dodavanje elementa u red (enqueue)
void enqueue(int x) {
    // Dodajemo element na kraj reda i pomeramo kraj
    red[kraj++] = x;
    // Napomena: kod običnog niza, ne radimo modulo, pa prostor može ostati neiskorišćen
}

// Uklanjanje elementa sa početka reda (dequeue)
void dequeue() {
    if (!empty()) {
        pocetak++; // Samo pomeramo početak
        // Napomena: element ostaje u nizu, ali više nije u redu
    }
}

// Dohvatanje prvog elementa reda bez uklanjanja
int front() {
    return red[pocetak];
}

Ovakva implementacija može dovesti do neiskorišćenog prostora u nizu, pa se u praksi često koristi cirkularni red.

Cirkularni red

Kod cirkularnog reda, kraj niza se „spaja” sa početkom, čime se prostor u nizu koristi efikasnije. Indeksi se pomeraju pomoću operatora modulo.

const int MAX = 100;
int red[MAX];
int pocetak = 0, kraj = 0;

// Dodavanje elementa u red
void enqueue(int x) {
    red[kraj] = x;
    kraj = (kraj + 1) % MAX; // Pomak sa wrap-around
}

// Uklanjanje elementa sa početka reda
void dequeue() {
    pocetak = (pocetak + 1) % MAX; // Pomak sa wrap-around
}

Implementacija reda pomoću povezane liste

Red se može implementirati i pomoću povezane liste, što eliminiše ograničenje fiksne veličine.

struct Node {
    int val;
    Node* next;
};

Node* pocetak = nullptr; // Prvi element reda
Node* kraj = nullptr;    // Poslednji element reda

// Dodavanje elementa u red
void enqueue(int x) {
    Node* novi = new Node{x, nullptr}; // Kreiranje novog čvora
    if (kraj == nullptr) {
        // Ako je red prazan, novi čvor je i početak i kraj
        pocetak = kraj = novi;
    } else {
        kraj->next = novi; // Povezujemo novi čvor na kraj
        kraj = novi;       // Pomeramo kraj
    }
}

// Uklanjanje elementa sa početka reda
void dequeue() {
    if (pocetak != nullptr) {
        Node* tmp = pocetak;       // Sačuvamo čvor za brisanje
        pocetak = pocetak->next;   // Pomeramo početak
        delete tmp;                // Oslobađamo memoriju
        if (pocetak == nullptr)    // Ako je red sada prazan
            kraj = nullptr;
    }
}

Primena reda

Red se veoma često koristi u algoritmima i sistemima:

• BFS (Breadth-First Search) obilazak grafova
• Obilazak stabala po nivoima
• Simulacije procesa i raspoređivanje zadataka
• Algoritmi za najkraći put u grafovima bez težina

Veza sa grafovima i stablima

Kod BFS obilaska grafova, red se koristi za čuvanje čvorova koji čekaju da budu obrađeni. Bez razumevanja rada reda, BFS algoritam je teško u potpunosti shvatiti.

U lekcijama o grafovima i stablima red će se koristiti kao osnovna pomoćna struktura.

Mini uporedni zadatak: Stek vs Red

Posmatraj isti niz operacija, ali primenjen nad stek i nad redom. Pre nego što klikneš na dugme, pokušaj da predvidiš ispis.

add(1)
add(2)
add(3)
print(remove())
add(4)
print(remove())

Pretpostavi da:

• kod steka → add = push, remove = pop
• kod reda → add = enqueue, remove = dequeue

Unesi rezultate:

Primer zadatka: Simulacija reda procesa

Pretpostavimo da operativni sistem koristi red za obradu procesa. Svaki proces koji stiže dodaje se na kraj reda, a proces koji je prvi u redu dobija pravo na izvršavanje.

U red redom stižu procesi sa identifikatorima: 1, 2, 3, 4.

Nakon toga se obrađuju prva dva procesa iz reda.

Zadatak

Odredi redosled izvršavanja procesa i stanje reda nakon obrade prva dva procesa.

Rešenje

Procesi se u red dodaju redom kako pristižu:

• Red nakon dolaska procesa: 1, 2, 3, 4

Prvi proces koji se izvršava je proces 1, jer je on prvi ubačen u red. Nakon toga se izvršava proces 2.

• Izvršeni procesi: 1, 2
• Stanje reda nakon obrade: 3, 4

Ovaj primer jasno pokazuje FIFO princip rada reda – procesi se izvršavaju tačno onim redosledom kojim su stigli.

Primer rada cirkularnog reda

Prikazaćemo kako cirkularni red funkcioniše prilikom dodavanja i uklanjanja elemenata. Koristi se FIFO princip, a indeksi se pomeraju modulo MAX.

// Cirkularni red
#include <iostream>
using namespace std;

const int MAX = 5; // manja veličina radi lakše vizualizacije
int red[MAX];
int pocetak = 0, kraj = 0;

// Provera da li je red prazan
bool empty() { return pocetak == kraj; }

// Dodavanje elementa
void enqueue(int x) {
    red[kraj] = x;
    kraj = (kraj + 1) % MAX;
}

// Uklanjanje elementa
void dequeue() {
    if (!empty()) pocetak = (pocetak + 1) % MAX;
}

// Ispis trenutnog stanja reda
void printRed() {
    cout << "Red: ";
    int i = pocetak;
    while (i != kraj) {
        cout << red[i] << " ";
        i = (i + 1) % MAX;
    }
    cout << endl;
}

int main() {
    enqueue(10); printRed(); // Red: 10
    enqueue(20); printRed(); // Red: 10 20
    enqueue(30); printRed(); // Red: 10 20 30
    dequeue(); printRed();   // Red: 20 30
    enqueue(40); printRed(); // Red: 20 30 40
    enqueue(50); printRed(); // Red: 20 30 40 50
    enqueue(60); printRed(); // Red: 20 30 40 50 60 (wrap-around)
    return 0;
}

□ Napomena: Kada kraj dođe do MAX, modulo operator vraća ga na početak. Na ovaj način se iskorišćava ceo niz, bez „mrtvih“ elemenata.

Primer BFS obilaska grafova

Prikaz BFS-a nad jednostavnim grafom pomoću reda. Red čuva čvorove koji čekaju da budu obrađeni.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    const int N = 5; // broj čvorova
    int graf[N][N] = {
        {0,1,1,0,0},
        {1,0,0,1,0},
        {1,0,0,1,1},
        {0,1,1,0,1},
        {0,0,1,1,0}
    };
    bool visited[N] = {false};
    queue<int> q;

    int start = 0;
    visited[start] = true;
    q.push(start);

    cout << "BFS redosled obilaska: ";

    while(!q.empty()) {
        int cvor = q.front(); q.pop();
        cout << cvor << " ";

        for(int i=0; i<N; i++) {
            if(graf[cvor][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
    cout << endl;
    return 0;
}

□ Objašnjenje: - Početni čvor se stavlja u red. - Dok red nije prazan: uklanjamo čvor sa početka i obilazimo njegove susede. - Susedi koji još nisu posećeni se dodaju u red. - Red garantuje da se čvorovi obrađuju **po nivou**, što je ključ BFS-a.

Zadaci za vežbu — Red (Queue)

1. Simulacija reda u banci

Tekst zadatka

U red u banci redom dolaze osobe sa brojevima: 5 3 8 2. Nakon toga se uslužuju prve dve osobe. Potrebno je ispisati redosled usluživanja i stanje reda nakon toga.

Primer

Ulaz:
5 3 8 2

Izlaz:
Usluženi: 5 3
Red: 8 2

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q; // Red (FIFO) za čuvanje osoba
    int x;

    // Učitavanje četiri osobe i dodavanje u red
    for(int i = 0; i < 4; i++) {
        cin >> x;
        q.push(x); // enqueue
    }

    // Usluživanje prvih dve osobe
    cout << "Usluženi: ";
    cout << q.front() << " "; // pogled na prvi element
    q.pop();                          // uklanjanje iz reda
    cout << q.front() << endl;
    q.pop();

    // Ispis stanja preostalih osoba u redu
    cout << "Red: ";
    while(!q.empty()) {
        cout << q.front() << " "; // ispis svakog elementa
        q.pop();                            // uklanjanje iz reda
    }
    return 0;
}

2. Obrada zahteva (FIFO)

Tekst zadatka

Dat je niz zahteva koji stižu na server. Server uvek obrađuje zahtev koji je prvi stigao. Ispisati redosled obrade zahteva.

Primer

Ulaz:
4
10 20 30 40

Izlaz:
10 20 30 40

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    queue<int> q; // FIFO red za zahteve

    // Učitavanje n zahteva i dodavanje u red
    for(int i = 0; i < n; i++) {
        cin >> x;
        q.push(x);
    }

    // Ispis redosleda obrade
    while(!q.empty()) {
        cout << q.front() << " "; // pogled na prvi zahtev
        q.pop();                            // uklanjanje iz reda
    }
    return 0;
}

3. Prvi negativan broj u svakom prozoru

Tekst zadatka

Dat je niz od n celih brojeva i veličina prozora k. Za svaki podniz dužine k ispisati prvi negativan broj. Ako ne postoji, ispisati 0.

Primer

Ulaz:
8 3
12 -1 -7 8 -15 30 16 28

Izlaz:
-1 -1 -7 -15 -15 0

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; i++) 
        cin >> a[i]; // učitavanje niza

    queue<int> q; // red čuva indekse negativnih brojeva

    for(int i = 0; i < n; i++) {
        // Ako je trenutni element negativan, dodaj indeks u red
        if(a[i] < 0)
            q.push(i);

        // Kada prozor dostigne veličinu k
        if(i >= k - 1) {
            // Izbacujemo indekse koji više nisu u prozoru
            while(!q.empty() && q.front() <= i - k)
                q.pop();

            // Ispis prvog negativnog broja u prozoru ili 0 ako nema negativnog
            if(q.empty()) 
                cout << "0 ";
            else 
                cout << a[q.front()] << " ";
        }
    }
    return 0;
}

Zadaci za vežbu — Red (Queue) (Takmičarski nivo)

4. Broj elemenata u redu u datom trenutku

Tekst zadatka

Dat je niz operacija nad redom: + znači dodavanje elementa u red, a - znači uklanjanje elementa iz reda. Red je u početku prazan. Potrebno je odrediti koliko elemenata ostaje u redu nakon svih operacija.

Primer

Ulaz:
++-++-

Izlaz:
2

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;

    int cnt = 0; // broj elemenata u redu
    for(char c : s) {
        if(c == '+') cnt++; // enqueue - povećavamo broj elemenata
        else cnt--;         // dequeue - smanjujemo broj elemenata
    }

    cout << cnt; // broj elemenata koji ostaju
    return 0;
}

s = input().strip()
cnt = 0
for c in s:
    if c == '+':
        cnt += 1  # enqueue
    else:
        cnt -= 1  # dequeue
print(cnt)      # preostali elementi u redu

5. Prvi neobrađeni zahtev

Tekst zadatka

Dat je niz zahteva i broj k obrađenih zahteva. Potrebno je ispisati ID zahteva koji će sledeći biti obrađen.

Primer

Ulaz:
5 3
10 20 30 40 50

Izlaz:
40

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, k, x;
    cin >> n >> k;
    queue<int> q;

    // Učitavanje svih zahteva u red
    for(int i = 0; i < n; i++) {
        cin >> x;
        q.push(x);
    }

    // uklanjamo prvih k zahteva (obrađeni)
    for(int i = 0; i < k; i++)
        q.pop();

    // sledeći neobrađeni zahtev je na vrhu reda
    cout << q.front();
    return 0;
}

from collections import deque

n, k = map(int, input().split())
arr = list(map(int, input().split()))
q = deque(arr)  # enqueue svih zahteva

for _ in range(k):
    q.popleft()   # dequeue obrađenih

print(q[0])      # sledeći neobrađeni zahtev

6. BFS bez grafa (širenje signala)

Tekst zadatka

Dat je niz gde 1 označava izvor signala, a 0 neobrađeno polje. Signal se širi ulevo i udesno svake sekunde. Odredi koliko je sekundi potrebno da se ceo niz popuni signalom.

Primer

Ulaz:
0 0 1 0 0

Izlaz:
2

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    queue<int> q;

    // Učitavanje niza i dodavanje izvora signala u red
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] == 1)
            q.push(i);
    }

    int time = -1; // broj sekundi, počinje od -1 jer se prvi nivo odmah procesuira
    while(!q.empty()) {
        int sz = q.size(); // broj elemenata u trenutnom "nivou"
        time++;
        while(sz--) {
            int i = q.front(); q.pop();
            // širenje signala ulevo
            if(i-1 >= 0 && a[i-1] == 0) {
                a[i-1] = 1;
                q.push(i-1);
            }
            // širenje signala udesno
            if(i+1 < n && a[i+1] == 0) {
                a[i+1] = 1;
                q.push(i+1);
            }
        }
    }

    cout << time; // minimalno vreme širenja signala
    return 0;
}

from collections import deque

n = int(input())
a = list(map(int, input().split()))
q = deque()

# dodavanje izvora signala u red
for i in range(n):
    if a[i] == 1:
        q.append(i)

time = -1
while q:
    for _ in range(len(q)):
        i = q.popleft()
        for ni in (i-1, i+1):
            if 0 <= ni < n and a[ni] == 0:
                a[ni] = 1
                q.append(ni)
    time += 1

print(time)  # minimalno vreme širenja signala

7. Minimalan broj operacija do cilja

Tekst zadatka

Dato je početno stanje x i cilj y. U jednom potezu možeš:

• uvećati broj za 1
• udvostručiti broj

Primer

Ulaz:
2 9

Izlaz:
3

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;

    queue<pair<int,int>> q;  // par {trenutni broj, broj poteza}
    unordered_set<int> vis;      // čuva posećena stanja

    q.push({x, 0});
    vis.insert(x);

    while(!q.empty()) {
        auto [v, d] = q.front(); q.pop();
        if(v == y) {  // dostignut cilj
            cout << d;
            return 0;
        }

        int a = v + 1;
        int b = v * 2;

        // proveravamo nova stanja i dodajemo u red ako nisu posećena
        if(a <= 2*y && !vis.count(a)) {
            vis.insert(a);
            q.push({a, d+1});
        }
        if(b <= 2*y && !vis.count(b)) {
            vis.insert(b);
            q.push({b, d+1});
        }
    }
    return 0;
}

from collections import deque

x, y = map(int, input().split())
q = deque([(x, 0)])  # (trenutni broj, broj poteza)
vis = set([x])        # posećena stanja

while q:
    v, d = q.popleft()
    if v == y:  # dostignut cilj
        print(d)
        break
    for nv in (v+1, v*2):
        if nv <= 2*y and nv not in vis:
            vis.add(nv)
            q.append((nv, d+1))