Deque je kratica za Double-Ended Queue. To je posebna vrsta podatkovne strukture, ki vam omogoča učinkovito dodajanje in odstranjevanje elementov z obeh koncev.

V nasprotju z običajnimi čakalnimi vrstami (ki običajno sledijo First In First Out) deque podpira operacije FIFO in LIFO. Zaradi tega je zelo prilagodljiv in uporaben v aplikacijah iz resničnega sveta, kot so težave z drsnimi okni pri načrtovanju opravil in obdelava podatkov v realnem času.

primer:

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

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

Zakaj potrebujemo deque

• Podpira čas O(1) za dodajanje/odstranjevanje elementov z obeh koncev.
• Je učinkovitejši od seznamov za front-end operacije.
• Lahko deluje tako kot čakalna vrsta (FIFO) kot sklad (LIFO).
• Idealno za načrtovanje težav z drsečimi okni in obdelavo podatkov v realnem času.
• Ponuja zmogljive vgrajene metode, kot je pripni levo() popleft() in zavrti().

Vrste omejenega vnosa deque

• Deque z omejenim vnosom :  Vnos je omejen na enem koncu, medtem ko je brisanje dovoljeno na obeh koncih.
• Izhod omejen Deque : izhod je omejen na enem koncu, vstavljanje pa je dovoljeno na obeh koncih.

Operacije na deque 

Tukaj je tabela s seznamom vgrajenih operacij deque v Pythonu z opisi in njihovimi ustreznimi časovnimi kompleksnostmi:

java je prazna

Dodajanje in brisanje elementov iz čakalne vrste

• pripni(x): Doda x na desni konec deque.
• pripni levo(x): Doda x na levi konec deque.
• podaljšati (iterable): Doda vse elemente od iterable do desnega konca.
• podaljšano levo (iterabilno): Doda vse elemente od ponovljivega do levega konca (v obratnem vrstnem redu).
• odstrani (vrednost): Odstrani prvo pojavitev podane vrednosti iz deque. Če vrednost ni najdena, sproži ValueError.
• pop(): Odstrani in vrne element z desnega konca.
• popleft(): Odstrani in vrne element z levega konca.
• počisti(): Odstrani vse elemente iz 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) 

Izhod:

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

Dostop do predmeta in dolžina deque

• Indeksiranje: Dostop do elementov po položaju z uporabo pozitivnih ali negativnih indeksov.
• samo(): Vrne število elementov 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 

Štetje vrtenja in obračanja deque

• štetje (vrednost): Ta metoda šteje število pojavitev določenega elementa v deque.
• vrti (n): Ta metoda zavrti deque za n korakov. Pozitivni n se vrti v desno, negativni n pa v levo.
• obratno(): Ta metoda obrne vrstni red elementov 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])