Ugrás a tartalomhoz

FIFO

A Wikiszótárból, a nyitott szótárból

Főnév

FIFO (tsz. FIFOs)

  1. (informatika) first in, first out

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:

  1. enqueue(x) – az x elem beszúrása a sor végére.
  2. 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?

  1. 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.
  2. 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.
  3. 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

  1. 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.
  2. Nyomtatási sor Minden felhasználótól érkező nyomtatási feladat enqueue→kilépéskor dequeue.

  3. Hálózati pufferelés Csomagok sorban állnak be a routerben vagy switch‐ben, FIFO‐ban tárolva.

  4. Üzenetsorok Üzenetszolgáltató rendszerekben (RabbitMQ, Kafka egyszerű sorok) a producerek enqueue, a consumer dequeue.

  5. 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);
            }
        }
    }
    
  6. 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:

  1. Tisztességes kiszolgálást: aki első, az kap kiszolgálást elsőként.
  2. O(1) műveleteket megfelelő belső implementációval (láncolt lista vagy körkörös tömb).
  3. 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.


  • FIFO - Szótár.net (en-hu)
  • FIFO - Sztaki (en-hu)
  • FIFO - Merriam–Webster
  • FIFO - Cambridge
  • FIFO - WordNet
  • FIFO - Яндекс (en-ru)
  • FIFO - Google (en-hu)
  • FIFO - Wikidata
  • FIFO - Wikipédia (angol)