queue data type (tsz. queue data types)
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. |
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;
}
};
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; }
};
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
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) |
enqueue
-elnek, a fogyasztók dequeue
-olják.
std::priority_queue
(heap‐alapú).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.