Deque In Python – Opplæring med eksempler

Hvis du er en Python-utvikler, har du sannsynligvis hørt om en deque, eller "dobbeltende kø." Det er et kraftig verktøy som kan øke applikasjonens effektivitet og øke hastigheten på ytelsen.

En deque er en spesialisert beholderdatatype som gir raskere tilføy- og pop-operasjoner fra begge ender av beholderen. Dette gjør det til et verdifullt verktøy for å implementere køer og stabler, som er vanlige listelignende datatyper i databehandling.

Det er en lavt nivå og svært optimalisert datastruktur som er veldig nyttig for en rekke applikasjoner. Som Python-programmerer er en deque et verktøy du vil ha i arsenalet ditt.

Fortsett å lese for å lære mer om Deques og hvordan du kan implementere dem i din !

Innholdsfortegnelse

• Hva er en Deque?
  • Funksjoner av A Python Deque
  • Applikasjoner av A Deque
• Hvordan lage og initialisere en Deque
  • Bruke deque()-funksjonen
  • Initialisere en Deque med Elements
• Hvordan utføre vanlige deque-operasjoner
  • Legge til elementer i en Deque
  • Legge til flere dataelementer til en Deque
  • Fjerning av elementer fra en Deque
  • Fjerne alle elementer fra en Deque
  • Tilgang til Elements of a Deque
  • Endre elementer i en Deque
• Hvordan jobbe med en Deque som en kø
  • Bruke append() og popleft() metoder
  • Sjekker om en Deque Queue er tom
• Arbeide med Deque som en stabel
  • Bruke append() og pop() metoder
  • Se etter et tomt Deque-objekt
• Hva er en begrenset Deque?
  • • Inndatabegrenset Deque
    • Utgangsbegrenset Deque
• La oss avslutte dette

Hva er en Deque?

Hvis du er ny på Python eller dataprogrammering generelt, lurer du kanskje på hva en deque er. Deque står for " double-ended queue ", og det er en datastruktur som lar deg legge til og fjerne elementer fra begge ender av køen.

Det ligner på en vanlig kø, men med den ekstra fleksibiliteten å kunne legge til og fjerne elementer både foran og bak i køen. Dette er mulig fordi Pythons deque er implementert som en dobbeltlenket liste.

I Python implementeres deques ved hjelp av samlingsmodulen, som gir en deque-klasse. Denne klassen gir en rekke metoder for å legge til og fjerne elementer fra deque.

Den gir også funksjoner for andre nyttige operasjoner som å rotere deque eller tømme den helt.

Funksjoner av A Python Deque

I motsetning til en vanlig liste, som har en O(n)-tidskompleksitet for append- og popoperasjoner, gir en deque en O(1)-tidskompleksitet. Dette gjør det betydelig raskere og minneeffektivt for disse lese-og-skrive-operasjonene.

Her er noen flere Python-deque-funksjoner du bør vite om:

• Det er en foranderlig datastruktur.

• Den kan lagre flere datatyper, for eksempel heltall, tupler, arrays, etc.

• Den støtter indeksering, men ikke skjæreoperasjoner.

• Den støtter ikke sortering på stedet

• Den støtter vanlige innebygde iterable funksjoner og operasjoner som i , sorted() , len() , reverse() , etc.

Applikasjoner av A Deque

Deques er nyttige av en rekke årsaker. For eksempel kan de brukes til å implementere en kø eller en stabel, som begge er vanlige datastrukturer innen informatikk.

De kan også brukes til å behandle data effektivt i sanntid, for eksempel i strømmeapplikasjoner eller i systemer som krever rask tilgang til data.

I tillegg til å bli brukt til køer og stabler, kan deques også brukes til å implementere bredde-første søkealgoritmer. De er også nyttige for å opprettholde et skyvevindu med elementer i en større sekvens.

Hvordan lage og initialisere en Deque

Du kan lage en deque ved å bruke en innebygd funksjon fra samlingsmodulen. La oss se nærmere på hvordan du kan lage og fylle opp denne datastrukturen.

Bruke deque()-funksjonen

For å lage en deque i Python, kan du bruke den innebygde deque()- funksjonen fra samlingsmodulen. Denne funksjonen returnerer et nytt tomt deque-objekt som du kan bruke til å implementere en dobbel-ended kø.

Her er et eksempel på hvordan du oppretter et tomt deque-objekt:

from collections import deque 

my_deque = deque() 

Du kan også lage en deque med innledende elementer ved å sende en iterabel (liste, tuppel, etc.) til deque()- funksjonen. Dequen vil bli initialisert med elementene i iterable, fra venstre til høyre.

Her er et eksempel:

from collections import deque

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

Initialisere en Deque med Elements

Du kan også initialisere en tom deque med elementer ved å bruke ulike metoder. En måte å gjøre dette på er å bruke metodene append() og appendleft() for å legge til elementer til deque fra henholdsvis høyre og venstre side.

Her er et eksempel:

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)

Etter å ha kjørt denne koden, vil dequen inneholde elementene [3, 1, 2].

En annen måte å initialisere en deque med elementer er å sende en liste over elementer til deque() -funksjonen.

Her er et eksempel:

from collections import deque

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

Å kjøre denne koden vil lage et deque-objekt som inneholder elementene [1, 2, 3] .

Totalt sett er det enkelt å opprette og initialisere en deque i Python og kan gjøres ved å bruke den innebygde deque()- funksjonen. Du kan også gjøre dette ved å legge til elementer i en tom deque ved å bruke metodene append() og appendleft() .

Hvordan utføre vanlige deque-operasjoner

Det er mange operasjoner du kan utføre på deque-objekter i Python. La oss sjekke ut noen av de mer populære.

Legge til elementer i en Deque

Du kan legge til elementer i en deque ved å bruke metodene append() og appendleft() . Append ()- metoden legger til et element til høyre ende av deque mens appendleft()- metoden legger til et element til venstre ende av deque.

Her er et eksempel:

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

Legge til flere dataelementer til en Deque

Hvis du ikke vil legge til dataelementer i en deque en etter en, kan du fremskynde prosessen med funksjonene extend() eller extendleft() . Disse funksjonene tar inn en iterabel og legger til den iterables innhold til henholdsvis slutten eller venstre ende av dequen.

Her er et eksempel:

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)

I koden ovenfor legger funksjonen extend() til de flere verdiene i fortsettelse til slutten av dequen. Deretter legger extendleft() -funksjonen til de flere dataelementene i hele listen til venstre ende av dequen.

Fjerning av elementer fra en Deque

Du kan fjerne elementer fra en Python-deque ved å bruke pop() og popleft() metodene. Pop () -metoden fjerner og returnerer elementet lengst til høyre i deque mens popleft() -metoden fjerner og returnerer elementet lengst til venstre i deque.

Her er et eksempel:

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

Du kan også fjerne en bestemt verdi fra en deque ved å bruke remove() -funksjonen. Funksjonen fjerner den første forekomsten av den angitte verdien fra dequen.

Her er et eksempel:

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

Hvis elementet ikke blir funnet, vil Python returnere en ValueError .

Fjerne alle elementer fra en Deque

For å fjerne alle elementene fra en Deque og returnere den til en tom tilstand, kan vi bruke clear()- funksjonen. Slik fungerer det:

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

Tilgang til Elements of a Deque

Du kan få tilgang til elementer i en Python-deque ved å bruke indekseringsoperatoren [] . Du kan også bruke en negativ verdi i indekseringsoperatoren for å få tilgang til deque-elementene fra høyre.

Indekseringen starter fra 0 for elementet lengst til venstre og -1 for elementet lengst til høyre. Her er et eksempel:

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 

Endre elementer i en Deque

Du kan endre elementer i en Python-deque ved å bruke indekseringsoperatoren " [] " og tilordningsoperatoren " = ". Her er et eksempel:

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) 

I koden ovenfor endrer indekseringsoperatøren de første og siste elementene i deksjonen til henholdsvis 10 og 50.

Dette er de grunnleggende operasjonene du kan utføre på et deque-objekt i Python. Med disse operasjonene kan du effektivt implementere ulike datastrukturer som køer, stabler og mer.

Hvordan jobbe med en Deque som en kø

Du kan bruke en deque i Python for å implementere en kødatastruktur. En kø er en abstrakt datatype som opererer på en først inn først ut (FIFO) basis.

Hva dette betyr er at du kan legge til nye elementer fra den ene enden av køen og skyve ut gamle elementer fra den andre enden.

En god måte å forklare dette på er en linje i en butikk. Vanligvis vil den første personen som ankommer være i spissen for køen og vil bli tatt hånd om først.

Nyankomne må gå bakerst i køen og vente på tur. Så, den første inn vil være den første som blir besvart, mens den sist inn vil være den sist ivaretatt.

Her er hvordan du kan bruke en deque til å implementere køer.

Bruke append() og popleft() metoder

For å bruke en deque som en kø, kan du bruke append()- metoden for å legge til elementer til høyre i dequen. I tillegg kan du bruke popleft()- metoden for å fjerne elementer fra venstre ende av deque.

Dette er en veldig effektiv måte å implementere en kø i Python. Her er et eksempel:

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

Som du kan se, legger append()- metoden til elementer til høyre ende av deque, og popleft()- metoden fjerner elementer fra venstre ende av deque.

Dette er akkurat det vi trenger i en køimplementering.

Sjekker om en Deque Queue er tom

For å sjekke om en deque er tom, kan du bruke not- operatøren. Her er et eksempel:

from collections import deque 

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

Dette vil sende ut " Køen er tom " fordi deksjonen er tom. Hvis du legger til elementer i listen, vil den ikke lenger være tom.

Avslutningsvis er det veldig effektivt og enkelt å implementere å bruke en deque som kø i Python.

Arbeide med Deque som en stabel

Akkurat som køer, er stabler et annet eksempel på abstrakte datatyper som du kan bruke til å organisere data. I motsetning til køer, fungerer stabler på en sist inn først ut-måte (LIFO).

Dette betyr at det siste elementet i deque vil være det første elementet ut. Slik kan du implementere dette ved å bruke den underliggende datastrukturen.

Bruke append() og pop() metoder

Når du bruker Deque som en stabel, kan du legge til elementer på toppen av stabelen ved å bruke append()- metoden. Denne metoden legger til elementet til høyre ende av deque.

På samme måte kan du fjerne elementer fra toppen av stabelen ved å bruke pop()- metoden. Denne metoden fjerner og returnerer elementet lengst til høyre i dequen.

La oss for eksempel si at du har en deque kalt " my_stack " og du vil legge til et element på toppen av stabelen. Du kan bruke følgende kode:

 my_stack.append(5) 

Dette vil legge til element 5 til toppen av stabelen.

Hvis du vil fjerne det øverste elementet fra stabelen, kan du bruke pop()-metoden: `

bal = my_stack.pop() 

print(bal)
# Output: 5

Dette vil fjerne og returnere elementet lengst til høyre i dequen, som i dette tilfellet er 5.

Se etter et tomt Deque-objekt

Du kan sjekke om en dequestabel er tom ved å bruke den boolske operatoren " not ". Hvis kartongen er tom, vil " not my_deque " returnere True . Ellers vil den returnere False .

La oss for eksempel si at du har en dequestabel kalt " my_deque " og du vil sjekke om den er tom. Du kan bruke følgende kode:

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

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

Dette vil skrive ut " Deque is tom " hvis deque er tom. Hvis den ikke er tom, vil utgangen være " The deque is not tom ".

Når du jobber med Deque som stack er det viktig å holde styr på om stabelen er tom eller ikke. Hvis du prøver å pop et element fra en tom stabel, vil du få en IndexError .

Hva er en begrenset Deque?

En begrenset deque er en dobbel-ended kø med noen begrensninger plassert på datatilføying og pop-operasjoner i hver ende av dequen. Det er to hovedtyper av begrensede deques; Inndatabegrensede deques og output-begrensede deques

La oss se på dem:

Inndatabegrenset Deque

En input-begrenset deque lar deg pop eller slette dataelementer fra begge ender av deque. Du kan imidlertid bare sette inn dataelementer fra den ene enden av deque.

Dette er veldig nyttig i applikasjoner med minnebegrensninger. Du kan bruke den til å legge til dataelementer i kronologisk rekkefølge samtidig som du beholder muligheten til å forkaste data fra en hvilken som helst ende av deque.

Utgangsbegrenset Deque

En utgangsbegrenset deque lar deg sette inn data fra begge ender av deque. Du kan imidlertid bare slette elementer fra den ene enden av dequen kalt frontend.

En utgangsbegrenset deque er veldig nyttig i tilfeller der du trenger å implementere en FIFO-datastruktur, men fortsatt vil ha funksjonaliteten for å legge til data fra begge ender.

La oss avslutte dette

Nå bør du ha en god forståelse av deque-modulen i Python og hvordan den kan brukes til å implementere effektive køer og stabler.

Deques er en allsidig datastruktur som gir mange fordeler i forhold til tradisjonelle lister. Disse fordelene er tydelige når det kommer til minneeffektive append- og popoperasjoner.

De er også et godt valg når du trenger å implementere en stabel eller en tosidig kø. Noen av de viktigste fordelene ved å bruke deques inkluderer:

• Effektive O(1) append og pop operasjoner fra begge ender av deque

• Rask O(1) tilgang til de første og siste elementene i dequen

• Innebygd støtte for trådsikre, atomoperasjoner

• Fleksible metoder for å sette inn, fjerne og rotere elementer i dekken

Totalt sett er deque-modulen et kraftig verktøy som kan hjelpe deg med å skrive mer effektiv og vedlikeholdbar Python-kode. Enten du jobber med et lite manus eller et storstilt prosjekt, er deques definitivt verdt å vurdere som et alternativ til tradisjonelle lister eller andre datastrukturer!

Klar til å lære mer om Python, sjekk spillelisten vår nedenfor