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:

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.  
 
 Python   
   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  ))   
    
  Produktion   
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.  
 
 Python   
   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  )   
    
  Produktion   
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])