Üdvözlöm, Ön a szó jelentését keresi. A DICTIOUS-ban nem csak a szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a szót egyes és többes számban mondani. Minden, amit a szóról tudni kell, itt található. A szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Főnév

std::queue (tsz. std::queues)

  1. (informatika) A sor (queue) egy FIFO (First-In, First-Out) elven működő adatszerkezet, amelyben az elsőként hozzáadott elem kerül először feldolgozásra.
  • O(1) időben lehet elemet beszúrni (push()) és eltávolítani (pop()).
  • Automatikusan növekvő méretű (dinamikusan allokált).
  • Az első elemet (front()) és az utolsó elemet (back()) könnyen elérhetjük.
  • A háttérben dupla végű sor (deque) implementációt használ.



1. std::queue alapvető használata C++ STL-ben

A std::queue az alapértelmezett sor típusa C++-ban.

Példa: Alapvető sor műveletek

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // Elembeszúrás
    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Első elem (front): " << q.front() << std::endl;
    std::cout << "Utolsó elem (back): " << q.back() << std::endl;

    // Sor kiírása és kiürítése
    std::cout << "Sor elemei: ";
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    
    return 0;
}

Kimenet:

Első elem (front): 10
Utolsó elem (back): 30
Sor elemei: 10 20 30

🔹 Magyarázat:
- push(x) – hozzáad egy elemet a sor végéhez. - front() – lekérdezi az első elemet. - back() – lekérdezi az utolsó elemet. - pop() – eltávolítja az első elemet. - empty() – ellenőrzi, hogy a sor üres-e.



2. std::queue műveletek és időkomplexitás

Művelet Leírás Időkomplexitás
push(value) Elem beszúrása a sor végére O(1)
pop() Az első elem eltávolítása O(1)
front() Az első elem lekérdezése O(1)
back() Az utolsó elem lekérdezése O(1)
size() Sor méretének lekérdezése O(1)
empty() Ellenőrzi, hogy üres-e a sor O(1)



3. Kétszeresen végű sor (std::deque vs std::queue)

A std::queue háttérben std::deque-ot használ, amely lehetővé teszi az elemek beszúrását és törlését mindkét végén.

Ha szükséged van egy olyan sorra, ahol mind az elejére, mind a végére lehet elemet hozzáadni és törölni, akkor std::deque jobb választás.

Példa: std::deque használata

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    dq.push_back(10);  // Végére beszúrás
    dq.push_front(5);  // Elejére beszúrás
    dq.push_back(15);

    std::cout << "Első elem: " << dq.front() << std::endl;
    std::cout << "Utolsó elem: " << dq.back() << std::endl;

    dq.pop_front();  // Az első elem eltávolítása
    dq.pop_back();   // Az utolsó elem eltávolítása

    std::cout << "Maradék elem: " << dq.front() << std::endl;

    return 0;
}

Kimenet:

Első elem: 5
Utolsó elem: 15
Maradék elem: 10

4. Saját Queue megvalósítása láncolt listával

Ha STL konténerek nélkül szeretnénk egy dinamikus sort megvalósítani, használhatunk egy egyszeresen láncolt listát.

Példa: Láncolt listával megvalósított sor

#include <iostream>

// Csomópont struktúra
struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

// Sor osztály láncolt lista alapján
class Queue {
private:
    Node* front;
    Node* rear;
    
public:
    Queue() : front(nullptr), rear(nullptr) {}

    // Elem beszúrása
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (!rear) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Elem eltávolítása
    void dequeue() {
        if (!front) return;
        Node* temp = front;
        front = front->next;
        if (!front) rear = nullptr;  // Ha a sor kiürült
        delete temp;
    }

    // Az első elem lekérése
    int getFront() {
        return front ? front->data : -1;  // Ha üres, -1-et ad vissza
    }

    // Ellenőrzi, hogy üres-e
    bool isEmpty() {
        return front == nullptr;
    }

    // Destruktor (memóriaszivárgás elkerülése)
    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

// Főprogram
int main() {
    Queue q;
    
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "Első elem: " << q.getFront() << std::endl;
    
    q.dequeue();
    std::cout << "Eltávolítás után első elem: " << q.getFront() << std::endl;

    return 0;
}

Kimenet:

Első elem: 10
Eltávolítás után első elem: 20

🔹 Magyarázat:
- Egyszeresen láncolt lista (Node struktúra) segítségével tároljuk az elemeket. - enqueue(value) – Hozzáad egy elemet a sor végére. - dequeue() – Eltávolítja az első elemet. - getFront() – Lekérdezi az első elemet.



5. std::queue vs. std::stack vs. std::priority_queue

Konténer Működés Legjobb használati eset
std::queue FIFO Elsőként érkező elem először kerül feldolgozásra
std::stack LIFO Legutoljára érkező elem kerül először feldolgozásra
std::priority_queue Sorrendezett Mindig a legnagyobb (vagy legkisebb) prioritású elem jön először
  • Ha időrendben szeretnél feldolgozni adatokat, akkor queue a megfelelő választás.
  • Ha utolsóként érkező elemet akarod először feldolgozni, akkor használj stack-et.
  • Ha prioritások szerint kell dolgoznod, akkor priority_queue a legjobb.



Összegzés

FIFO (First-In, First-Out) sorrendben dolgozik.
O(1) műveletek: gyors beszúrás és törlés.
Dinamikusan növekszik, memóriát automatikusan kezel.
Dupla végű verzióhoz (deque) vagy prioritási szabályokhoz (priority_queue) más STL konténerek ajánlottak.