En deque står för Double-Ended Queue. Det är en speciell typ av datastruktur som låter dig lägga till och ta bort element från båda ändarna effektivt.

Till skillnad från vanliga köer (som vanligtvis följer First In First Out) stöder en deque både FIFO- och LIFO-operationer. Detta gör det mycket flexibelt och användbart i verkliga applikationer som schemaläggning av skjutfönsterproblem och databearbetning i realtid.

Exempel:

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

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

Varför behöver vi deque

• Den stöder O(1)-tid för att lägga till/ta bort element från båda ändarna.
• Det är mer effektivt än listor för front-end-operationer.
• Den kan fungera som både en kö (FIFO) och en stack (LIFO).
• Idealisk för att schemalägga problem med skjutfönster och databearbetning i realtid.
• Det erbjuder kraftfulla inbyggda metoder som appendleft() popleft() och rotera().

Typer av begränsad deque-ingång

• Input Begränsad Deque :  Indata är begränsad i ena änden medan radering är tillåten i båda ändar.
• Output Begränsad Deque : utgången är begränsad i ena änden men insättning är tillåten i båda ändarna.

Operationer på bord 

Här är en tabell som visar inbyggda operationer för en deque i Python med beskrivningar och deras motsvarande tidskomplexitet:

hur man laddar ner musik

Lägga till och ta bort köobjekt

• lägg till (x): Lägger till x till den högra änden av dequen.
• appendleft(x): Lägger till x till den vänstra änden av dequen.
• extend(iterable): Lägger till alla element från den iterbara till den högra änden.
• extendleft(iterable): Lägger till alla element från den iterbara till den vänstra änden (i omvänd ordning).
• ta bort(värde): Tar bort den första förekomsten av det angivna värdet från dequen. Om värdet inte hittas väcker det ett ValueError.
• pop(): Tar bort och returnerar ett element från den högra änden.
• popleft(): Tar bort och returnerar ett element från den vänstra änden.
• rensa(): Tar bort alla element från dequen.

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) 

Produktion:

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

Tillgång till objekt och längd på deque

• Indexering: Få tillgång till element efter position med hjälp av positiva eller negativa index.
• endast(): Returnerar antalet element i dequen.

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 

Räkna rotation och återföring av en kortspel

• count(value): Denna metod räknar antalet förekomster av ett specifikt element i dequen.
• rotera(n): Denna metod roterar dequen med n steg. Positivt n roterar åt höger och negativt n roterar åt vänster.
• motsatt(): Denna metod vänder om ordningen på elementen i dequen.

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