FIFO
Főnév
FIFO (tsz. FIFOs)
A FIFO (First In, First Out) adatszerkezet és elv lényege, hogy az elemeket ugyanabban a sorrendben kezeljük, ahogy beérkeztek: az elsőként betett elem kerül először kiszedésre, a legutoljára betett pedig utoljára. Ez az egyszerű, de rendkívül hasznos viselkedés számtalan valós és számítógépes alkalmazás alapja: a várósorok, a processzorküldő sorok, az üzenetsorok, network packet buffering, nyomtatási feladatok kezelése, stb.
1. Az elv és definíció
- „Elsőként be”: amikor egy új adat (vagy „ügyfél”, „feladat”, „csomag” stb.) érkezik, azt a sor végére helyezzük („enqueue”).
- „Elsőként ki”: amikor ki akarunk venni egy elemet, mindig a sor legrégebbi, legrégebbi, vagyis legkorábban érkezett elemet szedjük ki („dequeue”).
- Ez a viselkedés hasonlít a postára várakozók sorára: aki elsőnek áll be, az kapja meg először a szolgáltatást.
Formálisan a FIFO egy véges sor (queue), amelynek két alapművelete van:
- enqueue(x) – az
xelem beszúrása a sor végére. - dequeue() → y – a sor elején álló elem eltávolítása és visszaadása.
További, opcionális segédműveletek:
- peek() → y – anélkül, hogy eltávolítanánk, visszaadja a sor elején álló elemet.
- isEmpty() → bool – igaz, ha nincs több elem a sorban.
- isFull() → bool – (ha fix méretű sor) igaz, ha megtelt.
2. Miért fontos a FIFO?
- Fairness (tisztességesség) A FIFO biztosítja, hogy minden érkező feldolgoztatásra kerüljön, és senki ne várjon „örökkön‐örökké” a sor végén. Minden új belépő után nyomon követhető, ki következik legelőször.
- Időbeli sorrend fenntartása Ha időben fontos a beérkezési sorrend (pl. network csomagok sorrendjének visszaállítása), a FIFO garantálja, hogy az elküldött sorrendben kapjuk vissza az adatokat – legalábbis a gyűjtőponton belül.
- Egyszerűség és hatékonyság A FIFO műveletek idő- és helyigénye általában O(1), azaz konstans idő alatt végrehajtható mind enqueue, mind dequeue, ha megfelelő belső adatstruktúrát (körkörös puffer, láncolt lista) használunk.
3. FIFO implementációk
3.1. Láncolt lista alapú
Egy egyszeresen láncolt lista head (első) és tail (utolsó) mutatóval:
struct Node {
int value;
Node* next;
Node(int v): value(v), next(nullptr) {}
};
class LinkedQueue {
Node* head; // front
Node* tail; // rear
public:
LinkedQueue(): head(nullptr), tail(nullptr) {}
~LinkedQueue() {
while (!isEmpty()) dequeue();
}
void enqueue(int x) {
Node* n = new Node(x);
if (!tail) {
head = tail = n;
} else {
tail->next = n;
tail = n;
}
}
int dequeue() {
if (!head) throw std::runtime_error("Üres sor");
int v = head->value;
Node* tmp = head;
head = head->next;
if (!head) tail = nullptr;
delete tmp;
return v;
}
bool isEmpty() const { return head == nullptr; }
};
- Előny: dinamikusan növekszik, amíg van memória.
- Hátrány: minden betétel és kilépés során új objektumot kell allokálni/felszabadítani.
3.2. Körkörös puffer (cirkuláris tömb)
Fix méretű tömb használata front és rear indexszel, modulo méret:
class CircularQueue {
int* data;
int capacity;
int front, rear;
int count; // éppen tárolt elemek száma
public:
CircularQueue(int cap): capacity(cap), front(0), rear(0), count(0) {
data = new int[capacity];
}
~CircularQueue(){ delete[] data; }
void enqueue(int x) {
if (count == capacity) throw std::runtime_error("Sor megtelt");
data[rear] = x;
rear = (rear + 1) % capacity;
++count;
}
int dequeue() {
if (count == 0) throw std::runtime_error("Üres sor");
int v = data[front];
front = (front + 1) % capacity;
--count;
return v;
}
bool isEmpty() const { return count == 0; }
bool isFull() const { return count == capacity; }
};
- Előny: nincs dinamikus allokáció minden műveletnél, konstans memóriaigény, kis overhead.
- Hátrány: fix kapacitás, előre kell méretezni.
4. FIFO műveletek komplexitása
| Művelet | Láncolt lista | Körkörös puffer |
|---|---|---|
| enqueue (betesz) | O(1) | O(1) |
| dequeue (kivesz) | O(1) | O(1) |
| peek/front | O(1) | O(1) |
| isEmpty | O(1) | O(1) |
| memory overhead | pointerok | tömb |
5. FIFO felhasználási területek
Operációs rendszerek
- Process scheduling (kész sor): Round‐robin időosztásnál a végrehajtandó folyamatok sorba állnak.
- I/O teljesítési sor: lemezműveletek, hálózati kérések.
Nyomtatási sor Minden felhasználótól érkező nyomtatási feladat enqueue→kilépéskor dequeue.
Hálózati pufferelés Csomagok sorban állnak be a routerben vagy switch‐ben, FIFO‐ban tárolva.
Üzenetsorok Üzenetszolgáltató rendszerekben (RabbitMQ, Kafka egyszerű sorok) a producerek enqueue, a consumer dequeue.
Szélességi keresés (BFS) gráfokban A BFS algoritmus a FIFO elvre épül:
std::queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }
Esemény‐vezérelt rendszerek GUI események, hálózati események sorba kerülnek, és sorban feldolgozódnak.
6. FIFO vs. LIFO
- FIFO (queue): elsőként be, elsőként ki.
- LIFO (stack): utolsóként be, elsőként ki („Last In, First Out”).
Mindkettő az adatok átmeneti tárolását biztosítja, de más‐más sorrendet:
| Tulajdonság | FIFO | LIFO |
|---|---|---|
| Műveletsorrend | érkezési sorrend | fordított érkezési sorrend |
| Alkalmazás | várósor, BFS, üzenetsor | függvénnyivás, RPN kifejezésértékelés |
| Adatszerkezet | queue | stack |
7. Pár nyelvi és könyvtári megoldás
C++ STL:
#include <queue> std::queue<int> q; // belsőleg deque<int> q.push(5); int x = q.front(); q.pop();
Java:
Queue<Integer> q = new LinkedList<>(); q.add(5); int x = q.remove();
Python (collections.deque):
from collections import deque q = deque() q.append(5) x = q.popleft()
8. Összefoglalás
A FIFO sor alapvető adatszerkezet, amely garantálja:
- Tisztességes kiszolgálást: aki első, az kap kiszolgálást elsőként.
- O(1) műveleteket megfelelő belső implementációval (láncolt lista vagy körkörös tömb).
- Széleskörű alkalmazást: operációs rendszer, hálózat, nyomtató, BFS, üzenetsor, eseménykezelés.
Minden olyan helyzetben, ahol a beérkezési sorrend megőrzése kritikus, a FIFO a helyes választás. Javítja a rendszer előreláthatóságát, megakadályozza a „éhenhalást” (starvation), és egyszerű, linearizált struktúrát nyújt a párhuzamos vagy aszinkron folyamatok koordinálásához.