Deque je skratka pre Double-Ended Queue. Ide o špeciálny typ dátovej štruktúry, ktorá umožňuje efektívne pridávať a odstraňovať prvky z oboch koncov.

Na rozdiel od bežných radov (ktoré zvyčajne nasledujú po prvom dnu, prvý von) deque podporuje operácie FIFO aj LIFO. Vďaka tomu je veľmi flexibilný a užitočný v aplikáciách v reálnom svete, ako sú problémy s plánovaním úloh s posuvnými oknami a spracovanie údajov v reálnom čase.

Príklad:

from collections import deque # Declaring deque  de = deque(['name''age''DOB']) print(de) 

deque(['name' 'age' 'DOB']) 

Prečo potrebujeme deque

• Podporuje čas O(1) na pridávanie/odstraňovanie prvkov z oboch koncov.
• Pre front-end operácie je to efektívnejšie ako zoznamy.
• Môže fungovať ako front (FIFO) aj zásobník (LIFO).
• Ideálne na plánovanie problémov s posuvnými oknami a spracovanie údajov v reálnom čase.
• Ponúka výkonné vstavané metódy ako napr appendleft() popleft() a otočiť ().

Typy obmedzeného vstupu Deque

• Obmedzený vstup Deque :  Vstup je obmedzený na jednom konci, zatiaľ čo odstránenie je povolené na oboch koncoch.
• Obmedzený výstup Deque : výstup je obmedzený na jednom konci, ale vkladanie je povolené na oboch koncoch.

Operácie na deque 

Tu je tabuľka so zoznamom vstavaných operácií deque v Pythone s popismi a ich zodpovedajúcou časovou zložitosťou:

diskrétna matematická negácia

Pridávanie a odstraňovanie vyradených položiek

• pripojiť (x): Pridáva x na pravý koniec deque.
• appendleft(x): Pridá x na ľavý koniec deque.
• rozšíriť (opakovateľné): Pridá všetky prvky z iterovateľného na pravý koniec.
• predĺžiť vľavo (opakovateľné): Pridá všetky prvky z iterovateľného na ľavý koniec (v opačnom poradí).
• odstrániť (hodnota): Odstráni prvý výskyt zadanej hodnoty z deque. Ak sa hodnota nenájde, vyvolá chybu ValueError.
• pop(): Odstráni a vráti prvok z pravého konca.
• popleft(): Odstráni a vráti prvok z ľavého konca.
• jasné(): Odstráni všetky prvky z deque.

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) 

výstup:

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([])

Prístup k položke a dĺžka deque

• Indexovanie: Prístup k prvkom podľa pozície pomocou kladných alebo záporných indexov.
• len(): Vráti počet prvkov v deque.

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

1 4 7 

Count Rotation and Reverse of the deque

• počet (hodnota): Táto metóda počíta počet výskytov konkrétneho prvku v deque.
• otočiť (n): Táto metóda otáča deque o n krokov. Kladné n sa otáča doprava a záporné n sa otáča doľava.
• spätne(): Táto metóda obráti poradie prvkov v deque.

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) 

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