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
double-ended queue (tsz. double-ended queues)
- (informatika) A deque, teljes nevén double-ended queue (kétvégű sor), egy olyan adatstruktúra, amely lehetővé teszi az elemek beszúrását és eltávolítását mindkét végén – vagyis elöl és hátul is. Nevének jelentése: kétvégű sor, vagy kétoldali sor.
Ez egy általánosítása a sima sornak (queue), ahol csak az egyik végére szúrhatunk be (hátul), és a másik végéről vehetünk ki (elöl).
2. Főbb műveletek (ADT leírás)
A deque absztrakt adattípus az alábbi fő műveleteket támogatja:
- insertFront(x): elem beszúrása az elejére
- insertBack(x): elem beszúrása a végére
- removeFront(): elem eltávolítása az elejéről
- removeBack(): elem eltávolítása a végéről
- front(): az első elem lekérdezése (nem törli)
- back(): az utolsó elem lekérdezése (nem törli)
- isEmpty(): üres-e a sor?
- size(): hány elem van benne?
Megjegyzés: Ezek a műveletek (ideális implementációban) mind O(1) időben végrehajthatók.
3. Motiváció, felhasználási példa
A deque nagyon hasznos, amikor mindkét irányból rugalmasan kell tudni kezelni az adatokat. Néhány tipikus alkalmazás:
- Visszalépés-előrelépés (undo/redo) algoritmusok
- Palindrom-ellenőrzés (karakterek összehasonlítása két végéről)
- Szintaxis-ellenőrzés (zárójelek, matematikai kifejezések)
- Interaktív programok input bufferelése
- Optimalizálás algoritmusok (pl. sliding window maximum/minimum)
- BFS (Breadth-First Search) algoritmusok bizonyos optimalizált változatai
- LRU cache (Least Recently Used cache algoritmus)
4. Implementációk
A deque implementálható többféleképpen:
a) Dinamikus tömb
- Körkörös tömbbel (circular array): előre/hátra léptetve, wraparound kezeléssel.
- Előnye: gyors, fix méretnél nagyon hatékony.
- Hátránya: méretezhetőség; ha kinőjük, újra kell allokálni.
b) Láncolt lista
- Kétirányú (doubly linked list): minden elem mutat az előző és a következő elemre.
- Előnye: bármilyen méret, gyors beszúrás/törlés két végén.
- Hátránya: minden elem többlet memóriát igényel (mutatók), lassabb random elérés.
c) STL és magas szintű nyelvek
- C++:
std::deque
- Python:
collections.deque
- Java:
ArrayDeque, LinkedList (Deque interface)
5. Példák
C++ STL
#include <deque>
#include <iostream>
int main() {
std::deque<int> dq;
dq.push_back(1); //
dq.push_front(2); //
dq.push_back(3); //
dq.push_front(4); //
dq.pop_back(); //
dq.pop_front(); //
std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << "\n";
return 0;
}
Python
from collections import deque
dq = deque()
dq.append(1) # back
dq.appendleft(2) # front
dq.append(3)
dq.appendleft(4)
print(dq) # deque()
dq.pop() # removes 3
dq.popleft() # removes 4
print(dq) # deque()
print("Front:", dq, "Back:", dq)
6. Fontosabb tulajdonságok
- Nem azonos a sima queue-val vagy stack-kel!
- A deque egyszerre működhet stack-ként is (csak egyik vég) és queue-ként is.
- Bármely végén beszúrhatunk vagy törölhetünk.
7. Specializált változatok
- Input-restricted deque: csak hátul lehet beszúrni, de elöl/hátul törölni.
- Output-restricted deque: csak elöl lehet törölni, de elöl/hátul beszúrni.
8. Elméleti háttér
ADT szinten a deque műveletekhez nincs szükség a belső működés ismeretére. Mindegy, hogy tömb, lista vagy bármi más, a lényeg a műveletek garantált (gyors) végrehajtása.
Matematikai szempontból a deque egy sorozat, melynek mindkét végéhez hozzáférünk.
9. További megjegyzések
- A deque (különösen tömb alapú) lehetőséget ad arra is, hogy gyorsan elérjük bármelyik végét, de középre lassabb a beszúrás.
- Sokszor használják cache-ekben (pl. LRU implementáció), ahol a legutoljára használt elem előre kerül, a legrégebbi hátra, és onnan törlődik.
- Python deque például thread-safe (bizonyos műveletei), emiatt gyakran használják producer-consumer modellekben.
10. Példa alkalmazás: Palindrom ellenőrzés
from collections import deque
def is_palindrome(s):
d = deque(s)
while len(d) > 1:
if d.popleft() != d.pop():
return False
return True
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False
11. Miért jobb néha, mint csak a queue vagy a stack?
- Rugalmas: amikor nem tudod előre, hogy melyik végén lesz szükség a műveletekre.
- Optimalizált algoritmusok: sliding window, BFS optimalizációk, backtracking.
12. Összegzés
A deque egy nagyon erős, rugalmas, gyors adatszerkezet, amely lehetővé teszi az elemek kezelését mindkét végén – szemben a szokásos stack vagy queue adattípusokkal. A programozásban a deque univerzális megoldás, ha mindkét végre gyors elérés kell.