queue data type

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.

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

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).

• 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            # peek
  q.popleft()         # dequeue
  empty = not q
  

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.

• 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>.

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.

• 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)