Choose your language!

---

|

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.

Slika 1: Prikaz reda (queue) – elementi se dodaju na kraj reda, a uklanjaju sa početka po FIFO principu (prvi ulazi, prvi izlazi).

Objašnjenje prikaza reda

Na slici je prikazana struktura podataka red (queue). Elementi u redu su poređani od početka ka kraju reda.

Novi elementi se uvek dodaju na kraj reda (desna strana na slici), dok se elementi uklanjaju sa početka reda (leva strana).

Strelica „Izlazi prvi!“ pokazuje smer uklanjanja elemenata iz reda. Element sa vrednošću 3 je prvi ubačen u red i zato će on prvi biti izbačen, bez obzira na to koliko je novih elemenata dodato kasnije.

Ovakvo ponašanje se naziva FIFO (First In – First Out), što znači da elementi izlaze iz reda istim redosledom kojim su u njega ušli.

Zahvaljujući ovom principu, red se često koristi u algoritmima kao što su BFS obilazak grafova, obrada zadataka i simulacije procesa.

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)

Pokreni animaciju

□ Šta ovde vidiš?
Svaka linija koda se izvršava redom. Red se menja tačno u trenutku kada se pozove enqueue ili dequeue. Elementi se dodaju na kraj reda, a uklanjaju sa početka.

Ovakav način razmišljanja je ključan za razumevanje:

• FIFO principa (First In – First Out)
• BFS algoritma (obilazak grafova)
• simulacije procesa i raspoređivanja zadataka

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?

Proveri

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

Stek (ispis):


Red (ispis):


Proveri i prikaži

Stek (LIFO)

Red (FIFO)

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;

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

bool empty() {
    return pocetak == kraj;
}

void enqueue(int x) {
    red[kraj++] = x;
}

void dequeue() {
    if (!empty()) {
        pocetak++;
    }
}

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;

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

void dequeue() {
    pocetak = (pocetak + 1) % MAX;
}

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;
Node* kraj = nullptr;

void enqueue(int x) {
    Node* novi = new Node{x, nullptr};
    if (kraj == nullptr) {
        pocetak = kraj = novi;
    } else {
        kraj->next = novi;
        kraj = novi;
    }
}

void dequeue() {
    if (pocetak != nullptr) {
        Node* tmp = pocetak;
        pocetak = pocetak->next;
        delete tmp;
        if (pocetak == nullptr)
            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.

Provera razumevanja: Isti niz operacija nad stekom i redom daje različit rezultat. Pokušaj da uočiš razliku.

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:

Stek (ispis):


Red (ispis):


Proveri odgovor

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.

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

Prikaži uputstvo

Uputstvo

• Koristi red (queue) za čuvanje osoba.
• Sve osobe dodaj u red redom.
• Dva puta ukloni element sa početka reda.
• Preostale elemente ispiši redom.

Prikaži rešenje

Rešenje

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

int main() {
    queue<int> q;
    int x;

    for(int i=0;i<4;i++) {
        cin >> x;
        q.push(x);
    }

    cout << "Usluženi: ";
    cout << q.front() << " ";
    q.pop();
    cout << q.front() << endl;
    q.pop();

    cout << "Red: ";
    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    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

Prikaži uputstvo

Uputstvo

• Ubaci sve zahteve u red.
• Redom ih uklanjaj i ispisuj.
• FIFO princip garantuje isti redosled.

Prikaži rešenje

Rešenje

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

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

    for(int i=0;i<n;i++) {
        cin >> x;
        q.push(x);
    }

    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    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

Prikaži uputstvo

Uputstvo

• U red čuvaj indekse negativnih brojeva.
• Izbacuj indekse koji izlaze iz prozora.
• Vrh reda daje odgovor za trenutni prozor.

Prikaži rešenje

Rešenje

#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];

    queue<int> q;

    for(int i=0;i<n;i++) {
        if(a[i] < 0)
            q.push(i);

        if(i >= k-1) {
            while(!q.empty() && q.front() <= i-k)
                q.pop();

            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

Prikaži uputstvo

• Ne moraš da čuvaš stvarne elemente.
• Dovoljno je brojati koliko puta se dodaje i uklanja.
• Neće biti uklanjanja iz praznog reda.

Prikaži rešenje

Rešenje (C++)

#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
        else cnt--;         // dequeue
    }

    cout << cnt;
    return 0;
}

Rešenje (Python)

s = input().strip()
cnt = 0
for c in s:
    if c == '+':
        cnt += 1
    else:
        cnt -= 1
print(cnt)

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

Prikaži uputstvo

• Koristi red.
• Prvih k elemenata ukloni iz reda.
• Na vrhu reda ostaje traženi element.

Prikaži rešenje

Rešenje (C++)

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

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

    for(int i = 0; i < n; i++) {
        cin >> x;
        q.push(x);
    }

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

    cout << q.front();
    return 0;
}

Rešenje (Python)

from collections import deque

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

for _ in range(k):
    q.popleft()

print(q[0])

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

Prikaži uputstvo

• Koristi BFS ideju sa redom.
• U red ubaci sve pozicije sa vrednošću 1.
• Širi signal po nivoima.

Prikaži rešenje

Rešenje (C++)

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

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

    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] == 1)
            q.push(i);
    }

    int time = -1;
    while(!q.empty()) {
        int sz = q.size();
        time++;
        while(sz--) {
            int i = q.front(); q.pop();
            if(i-1 >= 0 && a[i-1] == 0) {
                a[i-1] = 1;
                q.push(i-1);
            }
            if(i+1 < n && a[i+1] == 0) {
                a[i+1] = 1;
                q.push(i+1);
            }
        }
    }

    cout << time;
    return 0;
}

Rešenje (Python)

from collections import deque

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

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)

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

Odredi minimalan broj poteza da se iz x dođe do y.

Primer

Ulaz:
2 9

Izlaz:
3

Prikaži uputstvo

• Modeluj problem kao BFS u prostoru stanja.
• Koristi red za nivoe.
• Obavezno čuvaj posećena stanja.

Prikaži rešenje

Rešenje (C++)

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

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

    queue<pair<int,int>> q;
    unordered_set<int> vis;

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

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

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

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

Rešenje (Python)

from collections import deque

x, y = map(int, input().split())
q = deque([(x, 0)])
vis = set([x])

while q:
    v, d = q.popleft()
    if v == y:
        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))

---

​Prethodno
​|< Stek (Stack)

Sledeće
​​Disjoint Set Union (DSU) strukture+ >|

---