Deque w Pythonie – samouczek z przykładami

Jeśli jesteś programistą Pythona, prawdopodobnie słyszałeś o deque, czyli „kolejce dwustronnej”. To potężne narzędzie, które może zwiększyć wydajność Twojej aplikacji i przyspieszyć jej działanie.

Deque to wyspecjalizowany typ danych kontenera, który oferuje szybsze operacje dołączania i otwierania z obu końców kontenera. To czyni go cennym narzędziem do implementacji kolejek i stosów, które są typami danych przypominającymi listy w informatyce.

Jest to niskopoziomowa i wysoce zoptymalizowana struktura danych, która jest bardzo przydatna w różnych zastosowaniach. Jako programista Pythona, deque jest jednym z narzędzi, które będziesz chciał mieć w swoim arsenale.

Czytaj dalej, aby dowiedzieć się więcej o Deques i o tym, jak możesz je zaimplementować w kodzie Pythona !

Spis treści

• Co to jest Deque?
  • Cechy A Python Deque
  • Zastosowania A Deque
• Jak utworzyć i zainicjować Deque
  • Korzystanie z funkcji deque().
  • Inicjowanie Deque z elementami
• Jak wykonywać typowe operacje Deque
  • Dodawanie elementów do Deque
  • Dodawanie wielu elementów danych do Deque
  • Usuwanie elementów z Deque
  • Usuwanie wszystkich elementów z Deque
  • Dostęp do elementów Deque
  • Modyfikowanie elementów Deque
• Jak pracować z Deque jako kolejką
  • Używanie metod append() i popleft().
  • Sprawdzanie, czy kolejka Deque jest pusta
• Praca z Deque jako stosem
  • Używanie metod append() i pop().
  • Sprawdzanie pustego obiektu Deque
• Co to jest Restricted Deque?
  • • Deque z ograniczeniami wejściowymi
    • Deque z ograniczeniami wyjściowymi
• Podsumujmy to

Co to jest Deque?

Jeśli jesteś nowy w Pythonie lub programowaniu komputerowym w ogóle, możesz się zastanawiać, czym jest deque. Deque oznacza „ podwójnie zakończoną kolejkę ” i jest to struktura danych, która umożliwia dodawanie i usuwanie elementów z obu końców kolejki.

Jest podobny do zwykłej kolejki, ale z dodatkową elastycznością polegającą na możliwości dodawania i usuwania elementów zarówno z przodu, jak iz tyłu kolejki. Jest to możliwe, ponieważ deque w Pythonie jest zaimplementowane jako podwójnie połączona lista.

W Pythonie deques są implementowane przy użyciu modułu collections, który udostępnia klasę deque. Ta klasa udostępnia wiele metod dodawania i usuwania elementów z deque.

Zapewnia również funkcje do innych przydatnych operacji, takich jak obracanie deque lub całkowite wyczyszczenie.

Cechy A Python Deque

W przeciwieństwie do zwykłej listy, która ma złożoność czasową O(n) dla operacji dołączania i pop, deque zapewnia złożoność czasową O(1). Dzięki temu operacje odczytu i zapisu są znacznie szybsze i wydajniejsze pod względem pamięci.

Oto kilka dodatkowych funkcji deque w Pythonie, o których powinieneś wiedzieć:

• Jest to zmienna struktura danych.

• Może przechowywać wiele typów danych, np. liczby całkowite, krotki, tablice itp.

• Obsługuje indeksowanie, ale nie operacje krojenia.

• Nie obsługuje sortowania w miejscu

• Obsługuje typowe wbudowane funkcje i operacje iteracyjne, takie jak in , sorted() , len() , reverse() itp.

Zastosowania A Deque

Deques są przydatne z różnych powodów. Na przykład można ich użyć do zaimplementowania kolejki lub stosu, z których oba są typowymi strukturami danych w informatyce.

Mogą być również wykorzystywane do wydajnego przetwarzania danych w czasie rzeczywistym, na przykład w aplikacjach strumieniowych lub w systemach wymagających szybkiego dostępu do danych.

Oprócz tego, że są używane do kolejek i stosów, deques mogą być również używane do implementacji algorytmów wyszukiwania wszerz. Są również przydatne do utrzymywania przesuwanego okna elementów w większej sekwencji.

Jak utworzyć i zainicjować Deque

Możesz utworzyć deque za pomocą wbudowanej funkcji z modułu collections. Przyjrzyjmy się bliżej, jak możesz utworzyć i wypełnić tę strukturę danych.

Korzystanie z funkcji deque().

Aby utworzyć deque w Pythonie, możesz użyć wbudowanej funkcji deque() z modułu collections. Ta funkcja zwraca nowy pusty obiekt deque, którego można użyć do zaimplementowania kolejki dwustronnej.

Oto przykład tworzenia pustego obiektu deque:

from collections import deque 

my_deque = deque() 

Możesz także utworzyć deque z elementami początkowymi, przekazując iterowalną (listę, krotkę itp.) do funkcji deque() . Deque zostanie zainicjowany elementami w iterowalnym, od lewej do prawej.

Oto przykład:

from collections import deque

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

Inicjowanie Deque z elementami

Możesz także zainicjować pustą deque z elementami przy użyciu różnych metod. Jednym ze sposobów na to jest użycie metod append() i appendleft() w celu dodania elementów do deque odpowiednio z prawej i lewej strony.

Oto przykład:

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)

Po uruchomieniu tego kodu deque będzie zawierało elementy [3, 1, 2].

Innym sposobem zainicjowania deque z elementami jest przekazanie listy elementów do funkcji deque() .

Oto przykład:

from collections import deque

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

Uruchomienie tego kodu spowoduje utworzenie obiektu deque zawierającego elementy [1, 2, 3] .

Ogólnie rzecz biorąc, tworzenie i inicjowanie deque w Pythonie jest proste i można to zrobić za pomocą wbudowanej funkcji deque() . Można to również zrobić, dodając elementy do pustej deque za pomocą metod append() i appendleft() .

Jak wykonywać typowe operacje Deque

Istnieje wiele operacji, które można wykonać na obiektach deque w Pythonie. Sprawdźmy niektóre z bardziej popularnych.

Dodawanie elementów do Deque

Możesz dodawać elementy do deque w Pythonie , używając metod append() i appendleft() . Metoda append () dodaje element na prawy koniec deque, podczas gdy metoda appendleft() dodaje element na lewy koniec deque.

Oto przykład:

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

Dodawanie wielu elementów danych do Deque

Jeśli nie chcesz dodawać elementów danych do deque jeden po drugim, możesz przyspieszyć ten proces za pomocą funkcji extend() lub extendleft() . Funkcje te pobierają iterowalność i dołączają zawartość iterowalności odpowiednio do końca lub lewego końca deque.

Oto przykład:

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)

W powyższym kodzie funkcja extend() dołącza wielokrotne wartości w krotce cont na końcu deque. Następnie funkcja extendleft() dołącza wiele elementów danych z pełnej listy na lewym końcu deque.

Usuwanie elementów z Deque

Możesz usuwać elementy z deque Pythona za pomocą metod pop() i popleft() . Metoda pop() usuwa i zwraca skrajny prawy element deque, podczas gdy metoda popleft() usuwa i zwraca lewy element deque.

Oto przykład:

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

Możesz także usunąć określoną wartość z deque za pomocą funkcji remove() . Funkcja usuwa pierwsze wystąpienie określonej wartości z deque.

Oto przykład:

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

Jeśli element nie zostanie znaleziony, Python zwróci ValueError .

Usuwanie wszystkich elementów z Deque

Aby usunąć wszystkie elementy z Deque i przywrócić go do stanu pustego, możemy użyć funkcji clear() . Oto jak to działa:

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

Aby użyć deque jako kolejki, możesz użyć metody append() w celu dodania elementów na prawym końcu deque. Dodatkowo możesz użyć metody popleft() do usunięcia elementów z lewego końca deque.

Jest to bardzo wydajny sposób implementacji kolejki w Pythonie. Oto przykład:

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

Jak widać, metoda append() dodaje elementy z prawego końca deque, a metoda popleft() usuwa elementy z lewego końca deque.

To jest dokładnie to, czego potrzebujemy w implementacji kolejki.

Sprawdzanie, czy kolejka Deque jest pusta

Aby sprawdzić, czy deque jest puste, możesz użyć operatora not . Oto przykład:

from collections import deque 

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

Spowoduje to wyświetlenie komunikatu „ Kolejka jest pusta ”, ponieważ deque jest pusty. Jeśli dodasz elementy do deque, nie będzie już puste.

Podsumowując, użycie deque jako kolejki w Pythonie jest bardzo wydajne i łatwe do wdrożenia.

Praca z Deque jako stosem

Podobnie jak kolejki, stosy to kolejny przykład abstrakcyjnych typów danych, których można używać do organizowania danych. W przeciwieństwie do kolejek stosy działają na zasadzie „ostatnie weszło, pierwsze wyszło” (LIFO).

Oznacza to, że ostatni element w deque będzie pierwszym elementem na zewnątrz. Oto jak możesz to zaimplementować przy użyciu podstawowej struktury danych.

Używanie metod append() i pop().

Używając Deque jako stosu, możesz dodawać elementy na górę stosu za pomocą metody append() . Ta metoda dodaje element do prawego końca deque.

Podobnie możesz usuwać elementy ze szczytu stosu za pomocą metody pop() . Ta metoda usuwa i zwraca skrajny prawy element deque.

Załóżmy na przykład, że masz deque o nazwie „ my_stack ” i chcesz dodać element na górę stosu. Możesz użyć następującego kodu:

 my_stack.append(5) 

Spowoduje to dodanie elementu 5 na górę stosu.

Jeśli chcesz usunąć górny element ze stosu, możesz użyć metody pop(): `

bal = my_stack.pop() 

print(bal)
# Output: 5

Spowoduje to usunięcie i zwrócenie skrajnego prawego elementu deque, którym w tym przypadku jest 5.

Sprawdzanie pustego obiektu Deque

Możesz sprawdzić, czy stos deque jest pusty, używając operatora boolowskiego „ not ”. Jeśli deque jest puste, „ not my_deque ” zwróci True . W przeciwnym razie zwróci False .

Załóżmy na przykład, że masz stos deque o nazwie „ my_deque ” i chcesz sprawdzić, czy jest pusty. Możesz użyć następującego kodu:

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

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

Spowoduje to wydrukowanie „ Deque is empty ”, jeśli deque jest pusty. Jeśli nie jest pusty, wynikiem będzie „ Deque is not empty ”.

Podczas pracy z Deque jako stosem ważne jest, aby śledzić, czy stos jest pusty, czy nie. Jeśli spróbujesz wyjąć element z pustego stosu, otrzymasz IndexError .

Co to jest Restricted Deque?

Ograniczona deque to dwustronna kolejka z pewnymi ograniczeniami nałożonymi na operacje dołączania danych i pop na obu końcach deque. Istnieją dwa główne typy ograniczonych deques; Deque z ograniczeniami wejściowymi i deque z ograniczeniami wyjściowymi

Spójrzmy na nie:

Deque z ograniczeniami wejściowymi

Deque z ograniczeniami wejściowymi umożliwia wyskakiwanie lub usuwanie elementów danych z obu końców deque. Jednak elementy danych można wstawiać tylko z jednego końca deque.

Jest to bardzo przydatne w aplikacjach z ograniczeniami pamięci. Możesz go użyć do dodawania elementów danych w porządku chronologicznym, zachowując jednocześnie możliwość odrzucania danych z dowolnego końca deque.

Deque z ograniczeniami wyjściowymi

Deque z ograniczeniem wyjściowym umożliwia wstawianie danych z obu końców deque. Możesz jednak usuwać elementy tylko z jednego końca deque, zwanego frontem.

Deque z ograniczeniem wyjściowym jest bardzo przydatne w przypadkach, gdy musisz zaimplementować strukturę danych FIFO, ale nadal chcesz, aby funkcjonalność dołączała dane z obu końców.

Podsumujmy to

Do tej pory powinieneś dobrze rozumieć moduł deque w Pythonie i to, jak można go wykorzystać do implementacji wydajnych kolejek i stosów.

Deques to wszechstronna struktura danych, która oferuje wiele zalet w porównaniu z tradycyjnymi listami. Te zalety są oczywiste, jeśli chodzi o wydajne pod względem pamięci operacje dołączania i otwierania.

Są również doskonałym wyborem, gdy trzeba zaimplementować stos lub kolejkę dwustronną. Niektóre z kluczowych zalet korzystania z deques obejmują:

• Wydajne operacje dołączania i wyskakiwania O(1) z obu końców deque

• Szybki dostęp O(1) do pierwszego i ostatniego elementu deque

• Wbudowana obsługa bezpiecznych wątkowo operacji atomowych

• Elastyczne metody wkładania, wyjmowania i obracania elementów w deque

Ogólnie rzecz biorąc, moduł deque jest potężnym narzędziem, które może pomóc w pisaniu wydajniejszego i łatwiejszego w utrzymaniu kodu w Pythonie. Niezależnie od tego, czy pracujesz nad małym skryptem, czy projektem na dużą skalę, deques są zdecydowanie warte rozważenia jako alternatywa dla tradycyjnych list lub innych struktur danych!

Jeśli chcesz dowiedzieć się więcej o Pythonie, sprawdź naszą playlistę poniżej