Deque In Python – Handledning med exempel

Om du är en Python-utvecklare har du förmodligen hört talas om en deque, eller "dubbelkö". Det är ett kraftfullt verktyg som kan öka din applikations effektivitet och påskynda dess prestanda.

En deque är en specialiserad containerdatatyp som erbjuder snabbare append- och popoperationer från båda ändarna av containern. Detta gör det till ett värdefullt verktyg för att implementera köer och stackar, som är vanliga listliknande datatyper inom datoranvändning.

Det är en lågnivå och mycket optimerad datastruktur som är mycket användbar för en mängd olika applikationer. Som Python-programmerare är en deque ett verktyg som du kommer att vilja ha i din arsenal.

Fortsätt läsa för att lära dig mer om Deques och hur du kan implementera dem i din !

Innehållsförteckning

• Vad är en Deque?
  • Funktioner i A Python Deque
  • Tillämpningar av A Deque
• Hur man skapar och initierar en Deque
  • Använda funktionen deque()
  • Initiera en Deque med Elements
• Hur man utför vanliga deque-operationer
  • Lägga till element till en Deque
  • Lägga till flera dataelement till en Deque
  • Ta bort element från en Deque
  • Ta bort alla element från en Deque
  • Tillgång till Elements of a Deque
  • Ändra delar av en Deque
• Hur man arbetar med en Deque som kö
  • Använder metoderna append() och popleft().
  • Kontrollera om en Deque-kö är tom
• Arbeta med Deque som en stack
  • Använder metoderna append() och pop()
  • Söker efter ett tomt Deque-objekt
• Vad är A Restricted Deque?
  • • Input Begränsad Deque
    • Output Begränsad Deque
• Låt oss avsluta detta

Vad är en Deque?

Om du är ny på Python eller datorprogrammering i allmänhet, kanske du undrar vad en deque är. Deque står för " double-ended queue " och det är en datastruktur som låter dig lägga till och ta bort element från båda ändarna av kön.

Det liknar en vanlig kö men med den extra flexibiliteten att kunna lägga till och ta bort element från både fram- och baksidan av kön. Detta är möjligt eftersom Pythons deque är implementerad som en dubbellänkad lista.

I Python implementeras deques med hjälp av samlingsmodulen, som tillhandahåller en deque-klass. Den här klassen tillhandahåller ett antal metoder för att lägga till och ta bort element från dequen.

Den tillhandahåller också funktioner för andra användbara operationer som att rotera dequen eller rensa den helt.

Funktioner i A Python Deque

Till skillnad från en vanlig lista, som har en O(n)-tidskomplexitet för append- och popoperationer, ger en deque en O(1)-tidskomplexitet. Detta gör den betydligt snabbare och minneseffektiv för dessa läs-och-skriv-operationer.

Här är några fler Python-deque-funktioner du bör känna till:

• Det är en föränderlig datastruktur.

• Det kan lagra flera datatyper, t.ex. heltal, tupler, arrayer, etc.

• Det stöder indexering, men inte skivningsoperationer.

• Den stöder inte sortering på plats

• Den stöder vanliga inbyggda itererbara funktioner och operationer som in , sorted() , len() , reverse() , etc.

Tillämpningar av A Deque

Deques är användbara av en mängd olika anledningar. De kan till exempel användas för att implementera en kö eller en stack, som båda är vanliga datastrukturer inom datavetenskap.

De kan också användas för att effektivt bearbeta data i realtid, till exempel i streamingapplikationer eller i system som kräver snabb åtkomst till data.

Förutom att användas för köer och stackar, kan deques också användas för att implementera bredd-först sökalgoritmer. De är också användbara för att upprätthålla ett glidande fönster med föremål i en större sekvens.

Hur man skapar och initierar en Deque

Du kan skapa en deque med en inbyggd funktion från samlingsmodulen. Låt oss ta en närmare titt på hur du kan skapa och fylla upp denna datastruktur.

Använda funktionen deque()

För att skapa en deque i Python kan du använda den inbyggda deque()- funktionen från samlingsmodulen. Den här funktionen returnerar ett nytt tomt deque-objekt som du kan använda för att implementera en dubbeländad kö.

Här är ett exempel på hur man skapar ett tomt deque-objekt:

from collections import deque 

my_deque = deque() 

Du kan också skapa en deque med initiala element genom att skicka en iterabel (lista, tupel, etc.) till deque()- funktionen . Dequen kommer att initieras med elementen i iterablen, från vänster till höger.

Här är ett exempel:

from collections import deque

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

Initiera en Deque med Elements

Du kan också initiera en tom deque med element med olika metoder. Ett sätt att göra detta är att använda metoderna append() och appendleft() för att lägga till element till dequen från höger respektive vänster sida.

Här är ett exempel:

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)

Efter att ha kört den här koden kommer dequen att innehålla elementen [3, 1, 2].

Ett annat sätt att initiera en deque med element är att skicka en lista med element till deque()- funktionen.

Här är ett exempel:

from collections import deque

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

Genom att köra den här koden skapas ett deque-objekt som innehåller elementen [ 1, 2, 3] .

Sammantaget är det enkelt att skapa och initiera en deque i Python och kan göras med den inbyggda deque()- funktionen. Du kan också göra detta genom att lägga till element i en tom deque med metoderna append() och appendleft() .

Hur man utför vanliga deque-operationer

Det finns många operationer du kan utföra på deque-objekt i Python. Låt oss kolla in några av de mer populära.

Lägga till element till en Deque

Du kan lägga till element till en deque med metoderna append() och appendleft() . Metoden append() lägger till ett element till den högra änden av dequen medan appendleft() -metoden lägger till ett element till den vänstra änden av dequen.

Här är ett exempel:

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

Lägga till flera dataelement till en Deque

Om du inte vill lägga till dataelement till en deque en efter en kan du påskynda processen med funktionerna extend() eller extendleft() . Dessa funktioner tar in en iterabel och lägger till den iterables innehåll i slutet respektive vänsterkanten av dequen.

Här är ett exempel:

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 ovan lägger funktionen extend() till de multipla värdena i fortsättningen till slutet av dequen. Därefter lägger funktionen extendleft() till de flera dataelementen i den fullständiga listan till den vänstra änden av dequen.

Ta bort element från en Deque

Du kan ta bort element från en Python-deque med metoderna pop() och popleft() . Metoden pop() tar bort och returnerar elementet längst till höger i dequen medan popleft() -metoden tar bort och returnerar elementet längst till vänster i dequen.

Här är ett exempel:

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 också ta bort ett specifikt värde från en deque med funktionen remove() . Funktionen tar bort den första förekomsten av det angivna värdet från dequen.

Här är ett exempel:

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

Om elementet inte hittas kommer Python att returnera ett ValueError .

Ta bort alla element från en Deque

För att ta bort alla element från en Deque och återställa den till ett tomt tillstånd, kan vi använda clear()- funktionen. Så här fungerar 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([])

Tillgång till Elements of a Deque

Du kan komma åt element i en Python-deque med indexeringsoperatorn [] . Du kan också använda ett negativt värde i indexeringsoperatorn för att komma åt deque-elementen från höger.

Indexeringen börjar från 0 för elementet längst till vänster och -1 för elementet längst till höger. Här är ett exempel:

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 

Ändra delar av en Deque

Du kan modifiera element i en Python-deque med indexeringsoperatorn " [] " och tilldelningsoperatorn " = ". Här är ett exempel:

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 ovanstående kod ändrar indexeringsoperatören de första och sista delarna av dequen till 10 respektive 50.

Det här är de grundläggande operationerna du kan utföra på ett deque-objekt i Python. Med dessa operationer kan du effektivt implementera olika datastrukturer som köer, stackar och mer.

Hur man arbetar med en Deque som kö

Du kan använda en deque i Python för att implementera en ködatastruktur. En kö är en abstrakt datatyp som fungerar på basis av först in först ut (FIFO) .

Vad detta betyder är att du kan lägga till nya föremål från ena änden av kön och trycka ut gamla föremål från den andra änden.

Ett bra sätt att förklara detta är en rad i en butik. Vanligtvis kommer den första personen som anländer att stå i spetsen för linjen och tas om hand först.

Nyanlända måste gå längst bak i kön och vänta på sin tur. Så den först in kommer att vara den först besvarade, medan den sist in kommer att vara den senast behandlade.

Så här kan du använda en deque för att implementera köer.

Använder metoderna append() och popleft().

För att använda en deque som en kö kan du använda metoden append() för att lägga till element till höger i dequen. Dessutom kan du använda metoden popleft() för att ta bort element från den vänstra änden av dequen.

Detta är ett mycket effektivt sätt att implementera en kö i Python. Här är ett exempel:

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

As you can see, the append() method adds elements to the right end of the deque, and the popleft() method removes elements from the left end of the deque.

This is exactly what we need in a queue implementation.

Checking if a Deque Queue is Empty

To check if a deque is empty, you can use the not operator. Here is an example:

from collections import deque 

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

This will output “Queue is empty” because the deque is empty. If you add elements to the deque, it will no longer be empty.

In conclusion, using a deque as a queue in Python is very efficient and easy to implement.

Working with Deque as a Stack

Just like queues, stacks are another example of abstract data types that you can use in organizing data. Unlike queues, stacks operate in a last in first out (LIFO) fashion.

This means the last element into the deque will be the first element out. Here’s how you can implement this using the underlying data structure.

Using append() and pop() Methods

When using Deque as a stack, you can add elements to the top of the stack using the append() method. This method adds the element to the right end of the deque.

Similarly, you can remove elements from the top of the stack using the pop() method. This method removes and returns the rightmost element of the deque.

For example, let’s say you have a deque called “my_stack” and you want to add an element to the top of the stack. You can use the following code:

 my_stack.append(5) 

This will add the element 5 to the top of the stack.

If you want to remove the top element from the stack, you can use the pop() method: `

bal = my_stack.pop() 

print(bal)
# Output: 5

This will remove and return the rightmost element of the deque, which in this case is 5.

Checking for an Empty Deque Object

You can check if a deque stack is empty by using the boolean operator “not“. If the deque is empty, “not my_deque” will return True. Otherwise, it will return False.

For example, let’s say you have a deque stack called “my_deque” and you want to check if it is empty. You can use the following code:

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

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

This will print “The deque is empty” if the deque is empty. If it is not empty, the output will be “The deque is not empty“.

When working with Deque as a stack, it is important to keep track of whether the stack is empty or not. If you try to pop an element from an empty stack, you will get an IndexError.

What is A Restricted Deque?

A restricted deque is a double-ended queue with some restrictions placed on data append and pop operations on either end of the deque. There are two main types of restricted deques; Input restricted deque and output restricted deques

Let’s look at them:

Input Restricted Deque

An input-restricted deque allows you to pop or delete data elements from both ends of the deque. However, you can only insert data elements from one end of the deque.

This is very useful in applications with memory constraints. You can use it to add data elements in chronological order while retaining the ability to discard data from any end of the deque.

Output Restricted Deque

An output-restricted deque allows you to insert data from both ends of the deque. However, you can only delete items from one end of the deque called the front end.

An output-restricted deque is very useful in cases where you need to implement a FIFO data structure, but still want the functionality to append data from both ends.

Let’s Wrap This UP

By now, you should have a good understanding of the deque module in Python and how it can be used to implement efficient queues and stacks.

Deques are a versatile data structure that offers many advantages over traditional lists. These advantages are apparent when it comes to memory-efficient append and pop operations.

They are also a great choice when you need to implement a stack or a double-ended queue. Some of the key benefits of using deques include:

• Efficient O(1) append and pop operations from both ends of the deque

• Fast O(1) access to the first and last elements of the deque

• Built-in support for thread-safe, atomic operations

• Flexible methods for inserting, removing, and rotating elements in the deque

Overall, the deque module is a powerful tool that can help you write more efficient and maintainable Python code. Whether you are working on a small script or a large-scale project, deques are definitely worth considering as an alternative to traditional lists or other data structures!

Redo att lära dig mer om Python, kolla in vår spellista nedan