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:

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