queue

Angol

Főnév

queue (tsz. queues)

1. sor

Ige

queue (alapjelen, egyes szám harmadik személy queues, folyamatos melléknévi igenév queuing, második és harmadik alakja queued)

1. sorban áll

Főnév

queue (tsz. 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.

További információk

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

Francia

Kiejtés

• IPA: /kø/

Főnév

queue nn (plural queues)

1. sor

További információk

• queue - Szótár.net (fr-hu)
• queue - Reverso (fr-en)
• queue - Robert
• queue - Larousse
• queue - TLFI
• queue - Google (fr-en)
• queue - Яндекс (fr-ru)
• queue - Wikidata
• queue - Wikipédia (francia)