A deque a Double-Ended Queue rövidítése. Ez egy speciális típusú adatstruktúra, amely lehetővé teszi az elemek hatékony hozzáadását és eltávolítását mindkét végéről.
A normál várólistáktól eltérően (amelyek általában a First In First Out parancsot követik) a deque támogatja a FIFO és a LIFO műveleteket is. Ez nagyon rugalmassá és hasznossá teszi a valós alkalmazásokban, mint például a feladatütemezési csúszóablak problémák és a valós idejű adatfeldolgozás.
Példa:
Pythonfrom collections import deque # Declaring deque de = deque(['name''age''DOB']) print(de)
Kimenet
deque(['name' 'age' 'DOB'])
Miért van szükségünk dekára?
- Támogatja az O(1) időt az elemek hozzáadásához/eltávolításához mindkét végéről.
- Hatékonyabb, mint a listák a front-end műveletekhez.
- Működhet sorként (FIFO) és veremként (LIFO) is.
- Ideális csúszóablak problémák ütemezéséhez és valós idejű adatfeldolgozáshoz.
- Erőteljes beépített módszereket kínál, mint pl appendleft() popleft() és forog().
A korlátozott deque bemenet típusai
- Input Restricted Deque : A bevitel az egyik végén korlátozott, míg a törlés mindkét végén megengedett.
- Kimenet Korlátozott Deque : a kimenet az egyik végén korlátozott, de a beillesztés mindkét végén megengedett.
Műveletek a deque-n
Íme egy táblázat, amely felsorolja a Python deque beépített műveleteit leírásokkal és a hozzájuk tartozó időbeli összetettségekkel együtt:
hogyan lehet zenét letölteni
| Művelet | Leírás | Idő összetettsége |
|---|---|---|
| hozzáfűzés(x) | Hozzáadxa deque jobb végére. | O(1) |
| bal oldali függelék (x) | Hozzáadxa deque bal végére. | O(1) |
| pop() | Eltávolít és visszaad egy elemet a deque jobb végéről. | O(1) |
| popleft() | Eltávolít és visszaad egy elemet a deque bal végéből. | O(1) |
| kiterjeszthető (iterálható) | Hozzáadja az összes elemet inneniterablea deque jobb végére. | Rendben van) |
| kinyújtott bal (iterálható) | Hozzáadja az összes elemet inneniterablea deque bal végére (fordított sorrend). | Rendben van) |
| eltávolítás(érték) | Eltávolítja az első előfordulásátvaluea deque-ből. EmeliValueErrorha nem találják. | On) |
| forgatás (n) | Elforgatja a deque-tnlépések jobbra. Hana negatív balra forog. | Rendben van) |
| világos() | Eltávolítja az összes elemet a deque-ből. | On) |
| szám(érték) | Számolja az előfordulások számátvaluea deque-ben. | On) |
| index(érték) | Az első előfordulás indexét adja visszavaluea deque-ben. EmeliValueErrorha nem találják. | On) |
| fordított() | Megfordítja a deque elemeit a helyükön. | On) |
Sorból álló elemek hozzáfűzése és törlése
- hozzáfűzés(x): Hozzáadja x-et a deque jobb végéhez.
- bal oldali függelék (x): Hozzáadja x-et a deque bal végéhez.
- kiterjeszthető (iterálható): Minden elemet hozzáad az iterálhatótól a jobb végéhez.
- kinyújtott bal (iterálható): Minden elemet hozzáad az iterálhatótól a bal véghez (fordított sorrendben).
- eltávolítás(érték): Eltávolítja a megadott érték első előfordulását a deque-ből. Ha az érték nem található, akkor ValueError-t vet fel.
- pop(): Eltávolít és visszaad egy elemet a jobb oldalról.
- popleft(): Eltávolít és visszaad egy elemet a bal oldalról.
- világos(): Eltávolítja az összes elemet a deque-ből.
from collections import deque dq = deque([10 20 30]) # Add elements to the right dq.append(40) # Add elements to the left dq.appendleft(5) # extend(iterable) dq.extend([50 60 70]) print('After extend([50 60 70]):' dq) # extendleft(iterable) dq.extendleft([0 5]) print('After extendleft([0 5]):' dq) # remove method dq.remove(20) print('After remove(20):' dq) # Remove elements from the right dq.pop() # Remove elements from the left dq.popleft() print('After pop and popleft:' dq) # clear() - Removes all elements from the deque dq.clear() # deque: [] print('After clear():' dq)
Kimenet:
After extend([50 60 70]): deque([5 10 20 30 40 50 60 70])
After extendleft([0 5]): deque([5 0 5 10 20 30 40 50 60 70])
After remove(20): deque([5 0 5 10 30 40 50 60 70])
After pop and popleft: deque([0 5 10 30 40 50 60])
After clear(): deque([])
A tétel elérése és a deque hossza
- Indexelés: Hozzáférés az elemekhez pozíció szerint pozitív vagy negatív indexekkel.
- csak(): A deque elemeinek számát adja vissza.
import collections dq = collections.deque([1 2 3 3 4 2 4]) # Accessing elements by index print(dq[0]) print(dq[-1]) # Finding the length of the deque print(len(dq))
Kimenet
1 4 7
Gróf forgatás és visszafordítás egy deque
- szám(érték): Ez a módszer megszámolja egy adott elem előfordulásának számát a deque-ben.
- forgatás (n): Ez a módszer n lépéssel elforgatja a deque-t. A pozitív n jobbra, a negatív n pedig balra forog.
- fordított(): Ez a módszer megfordítja az elemek sorrendjét a deque-ben.
from collections import deque # Create a deque dq = deque([10 20 30 40 50 20 30 20]) # 1. Counting occurrences of a value print(dq.count(20)) # Occurrences of 20 print(dq.count(30)) # Occurrences of 30 # 2. Rotating the deque dq.rotate(2) # Rotate the deque 2 steps to the right print(dq) dq.rotate(-3) # Rotate the deque 3 steps to the left print(dq) # 3. Reversing the deque dq.reverse() # Reverse the deque print(dq)
Kimenet
3 2 deque([30 20 10 20 30 40 50 20]) deque([20 30 40 50 20 30 20 10]) deque([10 20 30 20 50 40 30 20])