Deque In Python - Zelfstudie met voorbeelden

Als je een Python-ontwikkelaar bent, heb je waarschijnlijk wel eens gehoord van een deque of 'dubbele wachtrij'. Het is een krachtige tool die de efficiëntie van uw applicatie kan verhogen en de prestaties kan versnellen.

Een deque is een gespecialiseerd containergegevenstype dat snellere append- en pop-bewerkingen biedt vanaf beide uiteinden van de container. Dit maakt het een waardevol hulpmiddel voor het implementeren van wachtrijen en stapels, die veelvoorkomende lijstachtige gegevenstypen zijn in de informatica.

Het is een low-level en sterk geoptimaliseerde datastructuur die erg handig is voor een verscheidenheid aan toepassingen. Als Python-programmeur is een deque een tool die je in je arsenaal wilt hebben.

Blijf lezen om meer te weten te komen over Deques en hoe u ze in uw Python-code kunt implementeren !

Inhoudsopgave

• Wat is een Deque?
  • Kenmerken van een Python-deque
  • Toepassingen van A Deque
• Een deque maken en initialiseren
  • De functie deque() gebruiken
  • Een deque initialiseren met elementen
• Hoe gemeenschappelijke deque-bewerkingen uit te voeren
  • Elementen toevoegen aan een Deque
  • Meerdere gegevenselementen toevoegen aan een deque
  • Elementen uit een deque verwijderen
  • Alle elementen uit een deque verwijderen
  • Toegang tot elementen van een deque
  • Elementen van een deque wijzigen
• Hoe te werken met een deque als een wachtrij
  • De methoden append() en popleft() gebruiken
  • Controleren of een dequeue leeg is
• Werken met Deque als een stapel
  • De methoden append() en pop() gebruiken
  • Controleren op een leeg deque-object
• Wat is een beperkte deque?
  • • Invoer beperkte deque
    • Uitvoer beperkte deque
• Laten we dit afronden

Wat is een Deque?

Als Python of computerprogrammering in het algemeen nieuw voor je is, vraag je je misschien af ​​wat een deque is. Deque staat voor " dubbele wachtrij ", en het is een gegevensstructuur waarmee u elementen aan beide uiteinden van de wachtrij kunt toevoegen en verwijderen.

Het is vergelijkbaar met een gewone wachtrij, maar met de extra flexibiliteit om elementen aan zowel de voor- als achterkant van de wachtrij toe te voegen en te verwijderen. Dit is mogelijk omdat de deque van Python is geïmplementeerd als een dubbel gelinkte lijst.

In Python worden deques geïmplementeerd met behulp van de collections-module, die een deque-klasse biedt. Deze klasse biedt een aantal methoden voor het toevoegen en verwijderen van elementen uit de deque.

Het biedt ook functies voor andere handige bewerkingen, zoals het roteren van de deque of het volledig wissen ervan.

Kenmerken van een Python-deque

In tegenstelling tot een gewone lijst, die een O(n)-tijdcomplexiteit heeft voor append- en pop-bewerkingen, biedt een deque een O(1)-tijdcomplexiteit. Dit maakt het aanzienlijk sneller en geheugenefficiënter voor deze lees- en schrijfbewerkingen.

Hier zijn nog enkele Python deque-functies die u moet kennen:

• Het is een veranderlijke gegevensstructuur.

• Het kan meerdere gegevenstypen opslaan, bijvoorbeeld gehele getallen, tuples, arrays, enz.

• Het ondersteunt indexering, maar geen slicing-bewerkingen.

• Het ondersteunt geen interne sortering

• Het ondersteunt algemene ingebouwde itereerbare functies en bewerkingen zoals in , sort() , len() , reverse() , etc.

Toepassingen van A Deque

Deques zijn om verschillende redenen nuttig. Ze kunnen bijvoorbeeld worden gebruikt om een ​​wachtrij of een stapel te implementeren, beide veelgebruikte gegevensstructuren in de informatica.

Ze kunnen ook worden gebruikt om gegevens efficiënt in realtime te verwerken, zoals in streaming-applicaties of in systemen die snelle toegang tot gegevens vereisen.

Behalve dat ze worden gebruikt voor wachtrijen en stapels, kunnen deques ook worden gebruikt voor het implementeren van zoekalgoritmen voor het eerst zoeken. Ze zijn ook handig voor het onderhouden van een schuifvenster met items in een grotere volgorde.

Een deque maken en initialiseren

U kunt een deque maken met behulp van een ingebouwde functie van de collecties-module. Laten we eens nader bekijken hoe u deze gegevensstructuur kunt maken en vullen.

De functie deque() gebruiken

Om een ​​deque in Python te maken, kunt u de ingebouwde deque()- functie van de collecties-module gebruiken. Deze functie retourneert een nieuw leeg deque-object dat u kunt gebruiken om een ​​dubbele wachtrij te implementeren.

Hier is een voorbeeld van het maken van een leeg deque-object:

from collections import deque 

my_deque = deque() 

U kunt ook een deque maken met beginelementen door een iterable (lijst, tuple, etc.) door te geven aan de functie deque() . De deque wordt geïnitialiseerd met de elementen in de iterable, van links naar rechts.

Hier is een voorbeeld:

from collections import deque

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

Een deque initialiseren met elementen

U kunt ook een lege deque met elementen initialiseren met behulp van verschillende methoden. Een manier om dit te doen is door de methoden append() en appendleft() te gebruiken om elementen aan de deque toe te voegen vanaf respectievelijk de rechter- en linkerkant.

Hier is een voorbeeld:

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)

Na het uitvoeren van deze code bevat de deque de elementen [3, 1, 2].

Een andere manier om een ​​deque met elementen te initialiseren, is door een lijst met elementen door te geven aan de functie deque() .

Hier is een voorbeeld:

from collections import deque

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

Door deze code uit te voeren, wordt een deque-object gemaakt met de elementen [1, 2, 3] .

Over het algemeen is het maken en initialiseren van een deque in Python eenvoudig en kan worden gedaan met behulp van de ingebouwde deque() functie. U kunt dit ook doen door elementen aan een lege deque toe te voegen met behulp van de methoden append() en appendleft() .

Hoe gemeenschappelijke deque-bewerkingen uit te voeren

Er zijn veel bewerkingen die u kunt uitvoeren op deque-objecten in Python. Laten we eens kijken naar enkele van de meer populaire.

Elementen toevoegen aan een Deque

U kunt elementen aan een Python- deque toevoegen met behulp van de methoden append() en appendleft() . De methode append() voegt een element toe aan het rechteruiteinde van de deque terwijl de methode appendleft() een element toevoegt aan de linkerkant van de deque.

Hier is een voorbeeld:

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

Meerdere gegevenselementen toevoegen aan een deque

Als u gegevenselementen niet één voor één aan een deque wilt toevoegen, kunt u het proces versnellen met de functies extend() of extendleft() . Deze functies nemen een iterable op en voegen de inhoud van de iterable toe aan respectievelijk het einde of de linkerkant van de deque.

Hier is een voorbeeld:

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)

In de bovenstaande code voegt de functie extend() de meerdere waarden in de cont tuple toe aan het einde van de deque. Vervolgens voegt de functie extendleft() de meerdere gegevenselementen in de volledige lijst toe aan het linkeruiteinde van de deque.

Elementen uit een deque verwijderen

U kunt elementen uit een Python-deque verwijderen met behulp van de methoden pop() en popleft() . De methode pop() verwijdert het meest rechtse element van de deque en retourneert dit, terwijl de methode popleft() het meest linkse element van de deque verwijdert en retourneert.

Hier is een voorbeeld:

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

U kunt ook een specifieke waarde uit een deque verwijderen met behulp van de functie remove() . De functie verwijdert de eerste keer dat de opgegeven waarde voorkomt uit de deque.

Hier is een voorbeeld:

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

Als het element niet wordt gevonden, retourneert Python een ValueError .

Alle elementen uit een deque verwijderen

Om alle elementen uit een Deque te verwijderen en terug te brengen naar een lege staat, kunnen we de functie clear() gebruiken. Dit is hoe het werkt:

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

Om een ​​deque als wachtrij te gebruiken, kunt u de methode append() gebruiken om elementen aan het rechteruiteinde van de deque toe te voegen. Bovendien kunt u de methode popleft() gebruiken om elementen aan de linkerkant van de deque te verwijderen.

Dit is een zeer efficiënte manier om een ​​wachtrij in Python te implementeren. Hier is een voorbeeld:

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

Zoals je kunt zien, voegt de methode append() elementen toe aan het rechteruiteinde van de deque en verwijdert de methode popleft() elementen aan de linkerkant van de deque.

Dit is precies wat we nodig hebben in een wachtrij-implementatie.

Controleren of een dequeue leeg is

Om te controleren of een deque leeg is, kunt u de niet- operator gebruiken. Hier is een voorbeeld:

from collections import deque 

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

Dit geeft de uitvoer " Wachtrij is leeg " omdat de wachtrij leeg is. Als u elementen aan de deque toevoegt, is deze niet langer leeg.

Concluderend, het gebruik van een deque als wachtrij in Python is zeer efficiënt en eenvoudig te implementeren.

Werken met Deque als een stapel

Net als wachtrijen zijn stapels een ander voorbeeld van abstracte gegevenstypen die u kunt gebruiken bij het organiseren van gegevens. In tegenstelling tot wachtrijen, werken stapels op een last in first out (LIFO) manier.

Dit betekent dat het laatste element in de deque het eerste element zal zijn. Hier leest u hoe u dit kunt implementeren met behulp van de onderliggende gegevensstructuur.

De methoden append() en pop() gebruiken

Wanneer u Deque als een stapel gebruikt, kunt u elementen aan de bovenkant van de stapel toevoegen met behulp van de methode append() . Deze methode voegt het element toe aan het rechteruiteinde van de deque.

Op dezelfde manier kunt u elementen van de bovenkant van de stapel verwijderen met behulp van de pop() methode. Deze methode verwijdert en retourneert het meest rechtse element van de deque.

Stel dat u bijvoorbeeld een deque heeft met de naam " my_stack " en u wilt een element toevoegen aan de bovenkant van de stapel. U kunt de volgende code gebruiken:

 my_stack.append(5) 

Hierdoor wordt element 5 toegevoegd aan de bovenkant van de stapel.

Als je het bovenste element van de stapel wilt verwijderen, kun je de methode pop() gebruiken: `

bal = my_stack.pop() 

print(bal)
# Output: 5

Hiermee wordt het meest rechtse element van de deque verwijderd en geretourneerd, in dit geval 5.

Controleren op een leeg deque-object

U kunt controleren of een deque-stack leeg is door de booleaanse operator " not " te gebruiken. Als de deque leeg is, zal " not my_deque " True retourneren . Anders wordt False geretourneerd .

Laten we bijvoorbeeld zeggen dat u een deque-stack heeft met de naam " my_deque " en u wilt controleren of deze leeg is. U kunt de volgende code gebruiken:

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

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

Dit zal " The deque is empty " afdrukken als de deque leeg is. Als het niet leeg is, is de uitvoer " De deque is niet leeg ".

Wanneer u met Deque als stapel werkt, is het belangrijk om bij te houden of de stapel leeg is of niet. Als u probeert een element uit een lege stapel te halen, krijgt u een IndexError .

Wat is een beperkte deque?

Een beperkte deque is een wachtrij met twee uiteinden met aan beide uiteinden van de deque enkele beperkingen voor het toevoegen van gegevens en pop-bewerkingen. Er zijn twee hoofdtypen beperkte deques; Invoer beperkte deque en output beperkte deques

Laten we ze eens bekijken:

Invoer beperkte deque

Met een deque met invoerbeperking kunt u gegevenselementen aan beide uiteinden van de deque pop-up of verwijderen. U kunt echter alleen gegevenselementen invoegen vanaf één uiteinde van de deque.

Dit is erg handig in toepassingen met geheugenbeperkingen. U kunt het gebruiken om gegevenselementen in chronologische volgorde toe te voegen, terwijl u de mogelijkheid behoudt om gegevens van elk uiteinde van de deque te verwijderen.

Uitvoer beperkte deque

Met een deque met uitvoerbeperking kunt u gegevens van beide uiteinden van de deque invoegen. U kunt echter alleen items verwijderen uit het ene uiteinde van de deque, het front-end.

Een deque met uitvoerbeperking is erg handig in gevallen waarin u een FIFO-gegevensstructuur moet implementeren, maar toch de functionaliteit wilt hebben om gegevens van beide kanten toe te voegen.

Laten we dit afronden

U zou nu een goed begrip moeten hebben van de deque-module in Python en hoe deze kan worden gebruikt om efficiënte wachtrijen en stapels te implementeren.

Deques zijn een veelzijdige gegevensstructuur die veel voordelen biedt ten opzichte van traditionele lijsten. Deze voordelen zijn duidelijk als het gaat om geheugenefficiënte append- en pop-bewerkingen.

Ze zijn ook een uitstekende keuze wanneer u een stapel of een dubbele wachtrij moet implementeren. Enkele van de belangrijkste voordelen van het gebruik van deques zijn:

• Efficiënte O(1) append- en pop-operaties vanaf beide uiteinden van de deque

• Snelle O(1) toegang tot de eerste en laatste elementen van de deque

• Ingebouwde ondersteuning voor thread-safe, atomaire operaties

• Flexibele methoden voor het invoegen, verwijderen en roteren van elementen in de deque

Over het algemeen is de deque-module een krachtige tool die u kan helpen bij het schrijven van efficiëntere en onderhoudbare Python-code. Of je nu aan een klein script werkt of een grootschalig project, deques zijn zeker het overwegen waard als alternatief voor traditionele lijsten of andere datastructuren!

Klaar om meer te leren over Python, bekijk onze afspeellijst hieronder