Deque v Pythonu – výukový program s příklady

Pokud jste vývojář Pythonu, pravděpodobně jste slyšeli o deque neboli „dvojité frontě“. Je to mocný nástroj, který může zvýšit efektivitu vaší aplikace a urychlit její výkon.

Deque je specializovaný datový typ kontejneru, který nabízí rychlejší operace připojení a otevření z obou konců kontejneru. Díky tomu je cenným nástrojem pro implementaci front a zásobníků, což jsou běžné datové typy podobné seznamům ve výpočetní technice.

Je to nízkoúrovňová a vysoce optimalizovaná datová struktura, která je velmi užitečná pro různé aplikace. Jako programátor Pythonu je deque jedním z nástrojů, který budete chtít mít ve svém arzenálu.

Pokračujte ve čtení, abyste se dozvěděli více o Deques a jak je můžete implementovat do svého !

Obsah

• Co je to Deque?
  • Vlastnosti A Python Deque
  • Aplikace A Deque
• Jak vytvořit a inicializovat Deque
  • Pomocí funkce deque().
  • Inicializace Deque pomocí prvků
• Jak provádět běžné operace deque
  • Přidání prvků do Deque
  • Přidání více datových prvků do A Deque
  • Odebrání prvků z Deque
  • Odebrání všech prvků z Deque
  • Přístup k prvkům Deque
  • Úprava prvků Deque
• Jak pracovat s Deque jako s frontou
  • Použití metod append() a popleft().
  • Kontrola, zda je fronta Deque prázdná
• Práce s Deque jako Stack
  • Použití metod append() a pop().
  • Kontrola prázdného objektu Deque
• Co je Restricted Deque?
  • • Input Restricted Deque
    • Omezený výstup Deque
• Pojďme to zabalit

Co je to Deque?

Pokud s Pythonem nebo počítačovým programováním obecně začínáte, možná vás zajímá, co je to deque. Deque znamená „ dvojitá fronta “ a je to datová struktura, která vám umožňuje přidávat a odebírat prvky z obou konců fronty.

Je to podobné jako u běžné fronty, ale s přidanou flexibilitou možnosti přidávat a odebírat prvky z přední i zadní části fronty. To je možné, protože Pythonův deque je implementován jako dvojitě propojený seznam.

V Pythonu jsou deques implementovány pomocí modulu collections, který poskytuje třídu deque. Tato třída poskytuje řadu metod pro přidávání a odebírání prvků z deque.

Poskytuje také funkce pro další užitečné operace, jako je otočení deque nebo jeho úplné vymazání.

Vlastnosti A Python Deque

Na rozdíl od běžného seznamu, který má časovou složitost O(n) pro operace připojení a pop, poskytuje deque časovou složitost O(1). Díky tomu je pro tyto operace čtení a zápisu výrazně rychlejší a efektivnější z hlediska paměti.

Zde jsou některé další funkce Python deque, o kterých byste měli vědět:

• Jde o proměnlivou datovou strukturu.

• Může ukládat více typů dat, např. celá čísla, n-tice, pole atd.

• Podporuje indexování, ale ne operace krájení.

• Nepodporuje třídění na místě

• Podporuje běžné vestavěné iterovatelné funkce a operace jako in , sorted() , len() , reverse() atd.

Aplikace A Deque

Deques jsou užitečné z různých důvodů. Lze je například použít k implementaci fronty nebo zásobníku, což jsou oba běžné datové struktury v informatice.

Lze je také použít k efektivnímu zpracování dat v reálném čase, například ve streamovacích aplikacích nebo v systémech, které vyžadují rychlý přístup k datům.

Kromě použití pro fronty a zásobníky lze deques také použít k implementaci algoritmů prohledávání do šířky. Jsou také užitečné pro udržování posuvného okna položek ve větším pořadí.

Jak vytvořit a inicializovat Deque

Deque můžete vytvořit pomocí vestavěné funkce z modulu collections. Pojďme se blíže podívat na to, jak můžete vytvořit a naplnit tuto datovou strukturu.

Pomocí funkce deque().

Chcete-li vytvořit deque v Pythonu, můžete použít vestavěnou funkci deque() z modulu collections. Tato funkce vrací nový prázdný objekt deque, který můžete použít k implementaci dvojité fronty.

Zde je příklad, jak vytvořit prázdný objekt deque:

from collections import deque 

my_deque = deque() 

Můžete také vytvořit deque s počátečními prvky předáním iterovatelné (seznam, n-tice atd.) funkci deque() . Deque bude inicializován s prvky v iterable, zleva doprava.

Zde je příklad:

from collections import deque

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

Inicializace Deque pomocí prvků

Můžete také inicializovat prázdný deque s prvky pomocí různých metod. Jedním ze způsobů, jak toho dosáhnout, je použít metody append() a appendleft() k přidání prvků do deque z pravé a levé strany.

Zde je příklad:

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 spuštění tohoto kódu bude deque obsahovat prvky [3, 1, 2].

Dalším způsobem, jak inicializovat deque s prvky, je předat seznam prvků funkci deque() .

Zde je příklad:

from collections import deque

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

Spuštěním tohoto kódu se vytvoří objekt deque obsahující prvky [1, 2, 3] .

Celkově je vytvoření a inicializace deque v Pythonu přímočaré a lze jej provést pomocí vestavěné funkce deque() . Můžete to také provést přidáním prvků do prázdného deque pomocí metod append() a appendleft() .

Jak provádět běžné operace deque

Existuje mnoho operací, které můžete provádět s objekty deque v Pythonu. Pojďme se podívat na některé z nejpopulárnějších.

Přidání prvků do Deque

Prvky do deque můžete přidat pomocí metod append() a appendleft() . Metoda append () přidá prvek na pravý konec deque, zatímco metoda appendleft() přidá prvek na levý konec deque.

Zde je příklad:

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

Přidání více datových prvků do A Deque

Pokud nechcete přidávat datové prvky do deque jeden po druhém, můžete proces urychlit pomocí funkcí extend() nebo extendleft() . Tyto funkce převezmou iterovatelnou a připojí její obsah na konec nebo levý konec deque.

Zde je příklad:

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)

V kódu výše funkce extend() připojí více hodnot v n-tice cont na konec deque. Dále funkce extendleft() připojí více datových prvků v úplném seznamu na levý konec deque.

Odebrání prvků z Deque

Prvky z deque Pythonu můžete odstranit pomocí metod pop() a popleft() . Metoda pop() odstraňuje a vrací prvek deque nejvíce vpravo, zatímco metoda popleft() odstraňuje a vrací prvek deque nejvíce vlevo.

Zde je příklad:

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

Můžete také odstranit konkrétní hodnotu z deque pomocí funkce remove() . Funkce odstraní první výskyt zadané hodnoty z deque.

Zde je příklad:

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

Pokud prvek není nalezen, Python vrátí ValueError .

Odebrání všech prvků z Deque

Chcete-li odstranit všechny prvky z Deque a vrátit jej do prázdného stavu, můžeme použít funkci clear() . Funguje to takto:

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

Přístup k prvkům Deque

K prvkům deque Pythonu můžete přistupovat pomocí operátoru indexování [] . Pro přístup k prvkům deque zprava můžete také použít zápornou hodnotu v operátoru indexování.

Indexování začíná od 0 pro prvek nejvíce vlevo a -1 pro prvek zcela vpravo. Zde je příklad:

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 

Úprava prvků Deque

Prvky deque v Pythonu můžete upravit pomocí operátoru indexování „ [] “ a operátoru přiřazení „ = “. Zde je příklad:

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) 

Ve výše uvedeném kódu operátor indexování změní první a poslední prvek deque na 10, respektive 50.

Toto jsou základní operace, které můžete provádět s objektem deque v Pythonu. Pomocí těchto operací můžete efektivně implementovat různé datové struktury, jako jsou fronty, zásobníky a další.

Jak pracovat s Deque jako s frontou

K implementaci datové struktury fronty můžete v Pythonu použít deque. Fronta je abstraktní datový typ, který funguje na principu FIFO (first in first out) .

To znamená, že můžete přidávat nové položky z jednoho konce fronty a vytlačovat staré položky z druhého konce.

Dobrým způsobem, jak to vysvětlit, je řada v obchodě. První osoba, která dorazí, bude obvykle v čele řady a bude se jí věnovat jako první.

Nově příchozí budou muset zamířit na konec fronty a počkat, až na ně přijde řada. Takže první příchozí bude prvním zodpovězeným, zatímco poslední příchozí bude tím posledním.

Zde je návod, jak můžete použít deque k implementaci front.

Použití metod append() a popleft().

Chcete-li použít deque jako frontu, můžete použít metodu append() k přidání prvků na pravý konec deque. Navíc můžete použít metodu popleft() k odstranění prvků z levého konce deque.

Toto je velmi efektivní způsob, jak implementovat frontu v Pythonu. Zde je příklad:

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 vidíte, metoda append() přidává prvky na pravý konec deque a metoda popleft() odstraňuje prvky z levého konce deque.

To je přesně to, co potřebujeme v implementaci fronty.

Kontrola, zda je fronta Deque prázdná

Chcete-li zkontrolovat, zda je deque prázdný, můžete použít operátor not . Zde je příklad:

from collections import deque 

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

Tím se vypíše „ Queue is empty “, protože deque je prázdný. Pokud do deque přidáte prvky, nebude již prázdný.

Závěrem lze říci, že použití deque jako fronty v Pythonu je velmi efektivní a snadno implementovatelné.

Práce s Deque jako Stack

Stejně jako fronty jsou zásobníky dalším příkladem abstraktních datových typů, které můžete použít při organizování dat. Na rozdíl od front fungují zásobníky způsobem LIFO (poslední dovnitř první ven).

To znamená, že poslední prvek v deque bude prvním prvkem ven. Zde je návod, jak to můžete implementovat pomocí základní datové struktury.

Použití metod append() a pop().

Když používáte Deque jako zásobník, můžete přidat prvky na vrchol zásobníku pomocí metody append() . Tato metoda přidá prvek na pravý konec deque.

Podobně můžete odstranit prvky z horní části zásobníku pomocí metody pop() . Tato metoda odstraní a vrátí prvek deque zcela vpravo.

Řekněme například, že máte deque s názvem „ my_stack “ a chcete přidat prvek na vrchol zásobníku. Můžete použít následující kód:

 my_stack.append(5) 

Tím přidáte prvek 5 na vrchol zásobníku.

Pokud chcete odstranit horní prvek ze zásobníku, můžete použít metodu pop(): `

bal = my_stack.pop() 

print(bal)
# Output: 5

Tím se odstraní a vrátí prvek deque zcela vpravo, což je v tomto případě 5.

Kontrola prázdného objektu Deque

Zda je zásobník deque prázdný, můžete zkontrolovat pomocí booleovského operátoru „ not “. Pokud je deque prázdný, " not my_deque " vrátí True . V opačném případě vrátí False .

Řekněme například, že máte zásobník deque s názvem „ my_deque “ a chcete zkontrolovat, zda je prázdný. Můžete použít následující kód:

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

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

Pokud je deque prázdný , vypíše se „ The deque is empty “. Pokud není prázdný, výstup bude „ The deque is not empty “.

Při práci s Deque jako se zásobníkem je důležité sledovat, zda je zásobník prázdný nebo ne. Pokud se pokusíte vyjmout prvek z prázdného zásobníku, zobrazí se chyba IndexError .

Co je Restricted Deque?

Omezený deque je fronta s dvojitým koncem s určitými omezeními na operace připojení dat a pop na obou koncích deque. Existují dva hlavní typy omezených deques; Deque s omezeným vstupem a omezeným výstupem deques

Pojďme se na ně podívat:

Input Restricted Deque

Deque s omezeným vstupem vám umožňuje otevřít nebo odstranit datové prvky z obou konců deque. Datové prvky však můžete vkládat pouze z jednoho konce deque.

To je velmi užitečné v aplikacích s omezením paměti. Můžete jej použít k přidání datových prvků v chronologickém pořadí a zároveň zachovat možnost vyřadit data z libovolného konce deque.

Omezený výstup Deque

Deque s omezeným výstupem vám umožňuje vkládat data z obou konců deque. Položky však můžete odstranit pouze z jednoho konce deque zvaného frontend.

Deque s omezeným výstupem je velmi užitečné v případech, kdy potřebujete implementovat datovou strukturu FIFO, ale přesto chcete, aby funkce připojovala data z obou konců.

Pojďme to zabalit

Nyní byste měli dobře rozumět modulu deque v Pythonu a tomu, jak jej lze použít k implementaci efektivních front a zásobníků.

Deques jsou všestranná datová struktura, která nabízí mnoho výhod oproti tradičním seznamům. Tyto výhody jsou zřejmé, pokud jde o paměťově efektivní operace připojení a pop.

Jsou také skvělou volbou, když potřebujete implementovat zásobník nebo dvojitou frontu. Některé z klíčových výhod používání deques zahrnují:

• Efektivní operace O(1) append a pop z obou konců deque

• Rychlý přístup O(1) k prvnímu a poslednímu prvku deque

• Vestavěná podpora pro atomické operace bezpečné pro vlákna

• Flexibilní metody pro vkládání, vyjímání a otáčení prvků v deque

Celkově je modul deque mocným nástrojem, který vám může pomoci psát efektivnější a udržovatelnější kód Pythonu. Ať už pracujete na malém skriptu nebo na velkém projektu, deques rozhodně stojí za zvážení jako alternativa k tradičním seznamům nebo jiným datovým strukturám!

Jste připraveni dozvědět se více o Pythonu, podívejte se na náš seznam skladeb níže