queue data type

Angol

Főnév

queue data type (tsz. queue data types)

1. (informatika) A Queue ADT (Abstract Data Type) egy FIFO (First‐In, First‐Out) szemléletű konténer, amelyben az elsőként betett elem kerül először ki. A sort az érkezési sorrendben történő feldolgozás természetes megvalósítására használjuk: nyomtatási job-ok, üzenetsorok, BFS bejárás, producer–consumer mintázat stb.

---

1. Alapműveletek

Művelet	Szignatúra	Leírás
create	Queue<T> Q;	Üres sor létrehozása.
enqueue(x)	Q.enqueue(x)	x elem beszúrása a sor végébe.
dequeue()	T x = Q.dequeue()	A sor elejéről eltávolítja és visszaadja a legkorábban érkezett elemet.
front() / peek()	T x = Q.front()	Visszaadja (de nem távolítja el) a sor elejét.
isEmpty()	bool b = Q.empty()	Igaz, ha a sor üres.
size()	size_t n = Q.size()	A sorban jelenleg tárolt elemek száma.
clear()	(nem mindig beépített)	Az összes elem törlése.

---

2. Implementációs stratégiák

2.1. Keresztül dinamikus tömb (ciklikus buffer)

template<typename T>
class Queue {
    T* data;
    size_t cap, head, tail, count;
public:
    Queue(size_t initial=16)
      : data(new T[initial]), cap(initial), head(0), tail(0), count(0)
    {}
    ~Queue(){ delete[] data; }
    void enqueue(const T& x) {
        if(count == cap) resize(cap*2);
        data[tail] = x;
        tail = (tail+1) % cap;
        ++count;
    }
    T dequeue() {
        T x = data[head];
        head = (head+1) % cap;
        --count;
        return x;
    }
    T& front() { return data[head]; }
    bool empty() const { return count==0; }
    size_t size() const { return count; }
private:
    void resize(size_t newCap) {
        T* tmp = new T[newCap];
        for(size_t i=0;i<count;++i)
            tmp[i] = data[(head+i)%cap];
        delete[] data;
        data=tmp;
        cap=newCap;
        head=0;
        tail=count;
    }
};

• enqueue: amortizált O(1) (szükség esetén átméretezés O(n))
• dequeue: O(1)
• front, empty, size: O(1)
• Memória: O(capacity)

2.2. Láncolt lista

template<typename T>
class Queue {
    struct Node { T value; Node* next; };
    Node *head, *tail;
    size_t count;
public:
    Queue(): head(nullptr), tail(nullptr), count(0) {}
    ~Queue(){ while(!empty()) dequeue(); }
    void enqueue(const T& x) {
        Node* node=new Node{x,nullptr};
        if(tail) tail->next=node;
        else head=node;
        tail=node;
        ++count;
    }
    T dequeue() {
        Node* tmp=head;
        T x=tmp->value;
        head=head->next;
        if(!head) tail=nullptr;
        delete tmp;
        --count;
        return x;
    }
    T& front() { return head->value; }
    bool empty() const { return head==nullptr; }
    size_t size() const { return count; }
};

• enqueue, dequeue, front, empty, size mind O(1).
• Memória: O(n) + overhead (pointerek).

---

3. Standard könyvtárak

• C++ STL

  #include <queue>
  std::queue<int> q;
  q.push(1);          // enqueue
  int x = q.front();  // peek
  q.pop();            // dequeue
  bool b = q.empty();
  

  Alapértelmezett belső tárolás: deque<T>.

• Java

  Queue<Integer> q = new LinkedList<>();
  q.add(1);           // enqueue
  int x = q.peek();   // peek
  q.remove();         // dequeue
  boolean b = q.isEmpty();
  

• Python

  from collections import deque
  q = deque()
  q.append(1)         # enqueue
  x = q[0]            # peek
  q.popleft()         # dequeue
  empty = not q
  

---

4. Komplexitások összefoglaló

Implementáció	enqueue	dequeue	front/peek	empty/size
Array (circular)	amort. O(1)	O(1)	O(1)	O(1)
Linked list	O(1)	O(1)	O(1)	O(1)

---

5. Használati minták

1. Graf bejárás (BFS) Szélességi keresés során a „következő” csúcsokat sorba tesszük, onnan dolgozzuk fel.
2. Producer–Consumer Többszálú környezetben a termelők enqueue-elnek, a fogyasztók dequeue-olják.
3. Nyomtatási- vagy üzenetsor A beérkező feladatok sorrendjében kerülnek kiszolgálásra.
4. Szint szerinti feldolgozás Adatfolyamok, időzített események, streaming.

---

6. Speciális változatok

• Priority Queue (nem szigorúan FIFO): minden elemhez prioritás tartozik, mindig a legmagasabb prioritású kerül kielőször. C++: std::priority_queue (heap‐alapú).
• Double‐Ended Queue (Deque): beszúrás és eltávolítás mindkét végén O(1). C++: std::deque / std::stack/std::queue adapterek. Java: ArrayDeque<E>.

---

Összefoglalás

A Queue ADT a sorban álló elemek természetes FIFO kezelését valósítja meg egyszerű, O(1) műveletekkel. Dinamikus tömbös ciklikus buffer vagy láncolt lista implementációval is megvalósítható, és a standard könyvtárakban minden modern nyelv támogatja beépítve. Alapvető építőelem algoritmusokban (BFS), párhuzamos mintázatokban (producer–consumer) és bármikor, amikor a feldolgozás sorrendje az érkezés sorrendjével esik egybe.

További információk

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