Deque je kratica za Double-Ended Queue. To je posebna vrsta strukture podataka koja vam omogućuje učinkovito dodavanje i uklanjanje elemenata s oba kraja.

Za razliku od normalnih redova (koji obično slijede prvi ušao prvi izašao), deque podržava i FIFO i LIFO operacije. To ga čini vrlo fleksibilnim i korisnim u aplikacijama iz stvarnog svijeta kao što su problemi s kliznim prozorom za raspored zadataka i obrada podataka u stvarnom vremenu.

Primjer:

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

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

Zašto nam treba deque

• Podržava O(1) vrijeme za dodavanje/uklanjanje elemenata s oba kraja.
• Učinkovitiji je od popisa za front-end operacije.
• Može funkcionirati i kao red (FIFO) i kao stog (LIFO).
• Idealno za planiranje problema s kliznim prozorom i obradu podataka u stvarnom vremenu.
• Nudi moćne ugrađene metode poput dodatilijevo() popleft() i rotirati().

Vrste ograničenog deque unosa

• Input Restricted Deque :  Unos je ograničen na jednom kraju dok je brisanje dopušteno na oba kraja.
• Izlaz ograničen deque : izlaz je ograničen na jednom kraju, ali je umetanje dopušteno na oba kraja.

Operacije na deque 

Evo tablice s popisom ugrađenih operacija deque-a u Pythonu s opisima i njihovom odgovarajućom vremenskom složenošću:

slušaj luku

Dodavanje i brisanje stavki iz reda čekanja

• dodati(x): Dodaje x na desni kraj dequea.
• dodati lijevo(x): Dodaje x na lijevi kraj dequea.
• proširiti (iterable): Dodaje sve elemente od iterable do desnog kraja.
• produži lijevo (iterabilno): Dodaje sve elemente od iterable do lijevog kraja (obrnutim redoslijedom).
• ukloniti (vrijednost): Uklanja prvo pojavljivanje navedene vrijednosti iz dequea. Ako vrijednost nije pronađena, javlja se ValueError.
• pop(): Uklanja i vraća element s desnog kraja.
• popleft(): Uklanja i vraća element s lijevog kraja.
• jasan(): Uklanja sve elemente iz dequea.

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) 

Izlaz:

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

Pristup stavci i duljina dequea

• Indeksiranje: Pristupite elementima po položaju koristeći pozitivne ili negativne indekse.
• samo(): Vraća broj elemenata u dequeu.

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 

Rotacija brojanja i preokret dequea

• broj(vrijednost): Ova metoda broji broj pojavljivanja određenog elementa u dequeu.
• rotiraj(n): Ova metoda rotira deque za n koraka. Pozitivan n rotira udesno, a negativan n ulijevo.
• obrnuto(): Ova metoda obrće redoslijed elemenata u dequeu.

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