Deque în Python – Tutorial cu exemple

Dacă sunteți un dezvoltator Python, probabil că ați auzit de o deque sau „coadă dublă”. Este un instrument puternic care poate crește eficiența aplicației dvs. și poate accelera performanța acesteia.

Un deque este un tip de date de container specializat care oferă operații mai rapide de adăugare și pop de la ambele capete ale containerului. Acest lucru îl face un instrument valoros pentru implementarea cozilor și stivelor, care sunt tipuri comune de date asemănătoare liste în calcul.

Este o structură de date de nivel scăzut și foarte optimizată, care este foarte utilă pentru o varietate de aplicații. Ca programator Python, un deque este un instrument pe care veți dori să îl aveți în arsenalul dvs.

Continuați să citiți pentru a afla mai multe despre Deques și despre cum le puteți implementa în codul dvs. Python !

Cuprins

• Ce este un Deque?
  • Caracteristicile unui Python Deque
  • Aplicații ale lui A Deque
• Cum să creați și să inițializați un Deque
  • Folosind funcția deque().
  • Inițializarea unui Deque cu Elemente
• Cum se efectuează operațiuni comune Deque
  • Adăugarea de elemente la un Deque
  • Adăugarea mai multor elemente de date la un Deque
  • Eliminarea elementelor dintr-un Deque
  • Îndepărtarea tuturor elementelor dintr-un Deque
  • Accesarea elementelor unui Deque
  • Modificarea elementelor unui Deque
• Cum să lucrați cu un Deque ca coadă
  • Folosind metodele append() și popleft().
  • Verificarea dacă o coadă Deque este goală
• Lucrul cu Deque ca o stivă
  • Folosind metodele append() și pop().
  • Verificarea unui obiect Deque gol
• Ce este un Deque restricționat?
  • • Intrare restricționată Deque
    • Ieșire restricționată Deque
• Să încheiem asta

Ce este un Deque?

Dacă sunteți nou în Python sau în programarea computerelor în general, s-ar putea să vă întrebați ce este un deque. Deque înseamnă „ coadă cu două capete ” și este o structură de date care vă permite să adăugați și să eliminați elemente de la ambele capete ale cozii.

Este similar cu o coadă obișnuită, dar cu flexibilitatea suplimentară de a putea adăuga și elimina elemente atât din față, cât și din spate a cozii. Acest lucru este posibil deoarece deque-ul lui Python este implementat ca o listă dublu legată.

În Python, deques sunt implementate folosind modulul de colecții, care oferă o clasă deque. Această clasă oferă o serie de metode pentru adăugarea și eliminarea elementelor din deque.

De asemenea, oferă funcții pentru alte operațiuni utile, cum ar fi rotirea deque-ului sau ștergerea completă.

Caracteristicile unui Python Deque

Spre deosebire de o listă obișnuită, care are o complexitate de timp O(n) pentru operațiunile de adăugare și pop, o deque oferă o complexitate de timp O(1). Acest lucru îl face semnificativ mai rapid și eficient în memorie pentru aceste operațiuni de citire și scriere.

Iată câteva caracteristici suplimentare Python deque pe care ar trebui să le cunoașteți:

• Este o structură de date mutabilă.

• Poate stoca mai multe tipuri de date, de exemplu, numere întregi, tupluri, matrice etc.

• Acceptă operațiuni de indexare, dar nu de tăiere.

• Nu acceptă sortarea la loc

• Acceptă funcții și operații iterabile comune încorporate, cum ar fi în , sorted() , len() , reverse() etc.

Aplicații ale lui A Deque

Decurile sunt utile dintr-o varietate de motive. De exemplu, ele pot fi folosite pentru a implementa o coadă sau o stivă, ambele fiind structuri de date comune în informatică.

Ele pot fi, de asemenea, utilizate pentru a procesa eficient datele în timp real, cum ar fi în aplicațiile de streaming sau în sistemele care necesită acces rapid la date.

Pe lângă faptul că sunt folosite pentru cozi și stive, deques-urile pot fi folosite și pentru implementarea algoritmilor de căutare pe lățimea întâi. De asemenea, sunt utile pentru menținerea unei ferestre glisante de articole într-o secvență mai mare.

Cum să creați și să inițializați un Deque

Puteți crea un deque folosind o funcție încorporată din modulul de colecții. Să aruncăm o privire atentă asupra modului în care puteți crea și completa această structură de date.

Folosind funcția deque().

Pentru a crea un deque în Python, puteți utiliza funcția încorporată deque() din modulul de colecții. Această funcție returnează un nou obiect deque gol pe care îl puteți folosi pentru a implementa o coadă cu două capete.

Iată un exemplu despre cum să creați un obiect deque gol:

from collections import deque 

my_deque = deque() 

De asemenea, puteți crea un deque cu elemente inițiale prin trecerea unui iterabil (listă, tuplu etc.) la funcția deque() . Deque-ul va fi inițializat cu elementele din iterabil, de la stânga la dreapta.

Iată un exemplu:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

Inițializarea unui Deque cu Elemente

De asemenea, puteți inițializa un deque gol cu ​​elemente folosind diferite metode. O modalitate de a face acest lucru este să utilizați metodele append() și appendleft() pentru a adăuga elemente la deque din partea dreaptă și, respectiv, din stânga.

Iată un exemplu:

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

După rularea acestui cod, deque-ul va conține elementele [3, 1, 2].

O altă modalitate de a inițializa un deque cu elemente este să treci o listă de elemente la funcția deque() .

Iată un exemplu:

from collections import deque

my_deque = deque([1, 2, 3]) 

Rularea acestui cod va crea un obiect deque care conține elementele [1, 2, 3] .

În general, crearea și inițializarea unui deque în Python este simplă și se poate face folosind funcția încorporată deque() . De asemenea, puteți face acest lucru prin adăugarea de elemente la o deque goală folosind metodele append() și appendleft() .

Cum se efectuează operațiuni comune Deque

Există multe operații pe care le puteți efectua asupra obiectelor deque în Python. Să vedem câteva dintre cele mai populare.

Adăugarea de elemente la un Deque

Puteți adăuga elemente la un deque Python folosind metodele append() și appendleft() . Metoda append() adaugă un element la capătul drept al deque-ului, în timp ce metoda appendleft() adaugă un element la capătul stâng al deque-ului.

Iată un exemplu:

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

Adăugarea mai multor elemente de date la un Deque

Dacă nu doriți să adăugați elemente de date la un deque unul câte unul, puteți accelera procesul cu funcțiile extend() sau extendleft() . Aceste funcții preiau un iterabil și adaugă conținutul iterabilului la sfârșitul sau, respectiv, la capătul din stânga deque-ului.

Iată un exemplu:

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

În codul de mai sus, funcția extend() adaugă valorile multiple din continutul la sfârșitul dequei. Apoi, funcția extendleft() adaugă mai multe elemente de date din lista completă la capătul din stânga deque-ului.

Eliminarea elementelor dintr-un Deque

Puteți elimina elemente dintr-un deque Python folosind metodele pop() și popleft() . Metoda pop() elimină și returnează elementul cel mai din dreapta al deque-ului, în timp ce metoda popleft() elimină și returnează elementul cel mai din stânga al deque-ului.

Iată un exemplu:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

De asemenea, puteți elimina o anumită valoare dintr-un deque folosind funcția remove() . Funcția elimină prima apariție a valorii specificate din deque.

Iată un exemplu:

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

Dacă elementul nu este găsit, Python va returna o valoare ValueError .

Îndepărtarea tuturor elementelor dintr-un Deque

Pentru a elimina toate elementele dintr-un Deque și a-l readuce într-o stare goală, putem folosi funcția clear() . Iată cum funcționează:

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

Accessing Elements of a Deque

You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.

The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

Modifying Elements of a Deque

You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.

These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.

How to Work with a Deque as a Queue

You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.

What this means is that you can append new items from one end of the queue and push out old items from the other end.

A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.

New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.

Here’s how you can use a deque to implement queues.

Using append() and popleft() Methods

Pentru a utiliza un deque ca coadă, puteți folosi metoda append() pentru a adăuga elemente la capătul din dreapta al deque-ului. În plus, puteți folosi metoda popleft() pentru a elimina elemente din capătul din stânga deque-ului.

Aceasta este o modalitate foarte eficientă de a implementa o coadă în Python. Iată un exemplu:

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

După cum puteți vedea, metoda append() adaugă elemente la capătul drept al deque-ului, iar metoda popleft() elimină elemente din capătul stâng al deque-ului.

Acesta este exact ceea ce avem nevoie într-o implementare de coadă.

Verificarea dacă o coadă Deque este goală

Pentru a verifica dacă un deque este gol, puteți utiliza operatorul not . Iată un exemplu:

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

Aceasta va afișa „ Coada este goală ”, deoarece deque-ul este gol. Dacă adăugați elemente la deque, acesta nu va mai fi gol.

În concluzie, folosirea unui deque ca coadă în Python este foarte eficientă și ușor de implementat.

Lucrul cu Deque ca o stivă

La fel ca și cozile, stivele sunt un alt exemplu de tipuri de date abstracte pe care le puteți folosi în organizarea datelor. Spre deosebire de cozi, stivele funcționează într-un mod LIFO.

Aceasta înseamnă că ultimul element din deque va fi primul element care iese. Iată cum puteți implementa acest lucru folosind structura de date de bază.

Folosind metodele append() și pop().

Când utilizați Deque ca stivă, puteți adăuga elemente în partea de sus a stivei folosind metoda append() . Această metodă adaugă elementul la capătul din dreapta al dequei.

În mod similar, puteți elimina elemente din partea de sus a stivei folosind metoda pop() . Această metodă elimină și returnează elementul cel mai din dreapta al dequei.

De exemplu, să presupunem că aveți un deque numit „ my_stack ” și doriți să adăugați un element în partea de sus a stivei. Puteți folosi următorul cod:

 my_stack.append(5) 

Acest lucru va adăuga elementul 5 în partea de sus a stivei.

Dacă doriți să eliminați elementul de sus din stivă, puteți utiliza metoda pop(): `

bal = my_stack.pop() 

print(bal)
# Output: 5

Acest lucru va elimina și va returna elementul cel mai din dreapta al dequei, care în acest caz este 5.

Verificarea unui obiect Deque gol

Puteți verifica dacă o stivă deque este goală folosind operatorul boolean „ nu ”. Dacă deque-ul este gol, „ not my_deque ” va returna True . În caz contrar, va returna False .

De exemplu, să presupunem că aveți o stivă de deque numită „ my_deque ” și doriți să verificați dacă este goală. Puteți folosi următorul cod:

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

Acest lucru va afișa „ The deque is empty ” dacă deque este gol. Dacă nu este gol, ieșirea va fi „ The deque is not empty ”.

Când lucrați cu Deque ca stivă, este important să urmăriți dacă stiva este goală sau nu. Dacă încercați să scoateți un element dintr-o stivă goală, veți obține o IndexError .

Ce este un Deque restricționat?

Un deque restricționat este o coadă cu două capete, cu unele restricții aplicate operațiunilor de anexare și pop de date la fiecare capăt al deque-ului. Există două tipuri principale de deques restricționate; Intrare restricted deque și ieșire restricted deque

Să ne uităm la ele:

Intrare restricționată Deque

Un deque cu restricții de intrare vă permite să deschideți sau să ștergeți elemente de date de la ambele capete ale deque-ului. Cu toate acestea, puteți insera elemente de date doar de la un capăt al dequei.

Acest lucru este foarte util în aplicațiile cu constrângeri de memorie. Îl puteți folosi pentru a adăuga elemente de date în ordine cronologică, păstrând în același timp capacitatea de a arunca date de la orice capăt al dequei.

Ieșire restricționată Deque

Un deque restricționat la ieșire vă permite să inserați date de la ambele capete ale deque-ului. Cu toate acestea, puteți șterge articole doar de la un capăt al dequei numit front end.

Un deque restricționat la ieșire este foarte util în cazurile în care trebuie să implementați o structură de date FIFO, dar doriți totuși ca funcționalitatea să atașeze date de la ambele capete.

Să încheiem asta

Până acum, ar trebui să înțelegeți bine modulul deque din Python și cum poate fi folosit pentru a implementa cozi și stive eficiente.

Deques sunt o structură de date versatilă care oferă multe avantaje față de listele tradiționale. Aceste avantaje sunt evidente atunci când vine vorba de operațiuni de adăugare și pop eficiente din punct de vedere al memoriei.

Sunt, de asemenea, o alegere excelentă atunci când trebuie să implementați o stivă sau o coadă dublă. Unele dintre beneficiile cheie ale utilizării deques includ:

• Operații eficiente de anexare și pop O(1) de la ambele capete ale deque-ului

• Acces rapid O(1) la primul și ultimul element al dequei

• Suport încorporat pentru operațiuni atomice sigure pentru fire

• Metode flexibile pentru introducerea, îndepărtarea și rotirea elementelor în deque

În general, modulul deque este un instrument puternic care vă poate ajuta să scrieți cod Python mai eficient și mai ușor de întreținut. Indiferent dacă lucrați la un script mic sau la un proiect la scară largă, deques merită cu siguranță luate în considerare ca o alternativă la listele tradiționale sau alte structuri de date!

Gata să aflați mai multe despre Python, consultați lista noastră de redare de mai jos