Deque em Python – Tutorial com exemplos

Se você é um desenvolvedor Python, provavelmente já ouviu falar de um deque, ou “fila de duas pontas”. É uma ferramenta poderosa que pode aumentar a eficiência de seu aplicativo e acelerar seu desempenho.

Um deque é um tipo de dados de contêiner especializado que oferece operações de acréscimo e remoção mais rápidas de ambas as extremidades do contêiner. Isso o torna uma ferramenta valiosa para implementar filas e pilhas, que são tipos de dados semelhantes a listas comuns na computação.

É uma estrutura de dados de baixo nível e altamente otimizada que é muito útil para uma variedade de aplicativos. Como um programador Python, um deque é uma ferramenta que você vai querer ter em seu arsenal.

Continue lendo para aprender mais sobre Deques e como você pode implementá-los em seu código Python !

Índice

• O que é um Deque?
  • Características de um Python Deque
  • Aplicações de A Deque
• Como criar e inicializar um Deque
  • Usando a função deque()
  • Inicializando um Deque com Elementos
• Como realizar operações comuns de deque
  • Adicionando elementos a um Deque
  • Adicionando vários elementos de dados a um Deque
  • Removendo Elementos de um Deque
  • Removendo todos os elementos de um Deque
  • Acessando Elementos de um Deque
  • Modificando Elementos de um Deque
• Como trabalhar com um Deque como uma fila
  • Usando métodos append() e popleft()
  • Verificando se uma Fila Deque está Vazia
• Trabalhando com Deque como uma pilha
  • Usando métodos append() e pop()
  • Verificando um Objeto Deque Vazio
• O que é um Deque Restrito?
  • • Deque restrito de entrada
    • Saída Restrita Deque
• Vamos Encerrar Isso

O que é um Deque?

Se você é novo em Python ou em programação de computadores em geral, pode estar se perguntando o que é um deque. Deque significa “ fila dupla ” e é uma estrutura de dados que permite adicionar e remover elementos de ambas as extremidades da fila.

É semelhante a uma fila normal, mas com a flexibilidade adicional de poder adicionar e remover elementos da frente e do fim da fila. Isso é possível porque o deque do Python é implementado como uma lista duplamente encadeada.

Em Python, deques são implementados usando o módulo collections, que fornece uma classe deque. Essa classe fornece vários métodos para adicionar e remover elementos do deque.

Ele também fornece funções para outras operações úteis, como girar o deque ou limpá-lo totalmente.

Características de um Python Deque

Ao contrário de uma lista regular, que tem uma complexidade de tempo O(n) para operações append e pop, um deque fornece uma complexidade de tempo O(1). Isso o torna significativamente mais rápido e eficiente em termos de memória para essas operações de leitura e gravação.

Aqui estão mais alguns recursos de deque do Python que você deve conhecer:

• É uma estrutura de dados mutável.

• Ele pode armazenar vários tipos de dados, por exemplo, inteiros, tuplas, arrays, etc.

• Ele oferece suporte à indexação, mas não às operações de divisão.

• Ele não oferece suporte à classificação no local

• Ele suporta funções e operações iteráveis ​​integradas comuns, como in , sorted() , len() , reverse() , etc.

Aplicações de A Deque

Deques são úteis por uma variedade de razões. Por exemplo, eles podem ser usados ​​para implementar uma fila ou uma pilha, ambas estruturas de dados comuns na ciência da computação.

Eles também podem ser usados ​​para processar dados em tempo real com eficiência, como em aplicativos de streaming ou em sistemas que exigem acesso rápido aos dados.

Além de serem usados ​​para filas e pilhas, os deques também podem ser usados ​​para implementar algoritmos de busca em largura. Eles também são úteis para manter uma janela deslizante de itens em uma sequência maior.

Como criar e inicializar um Deque

Você pode criar um deque usando uma função interna do módulo de coleções. Vamos dar uma olhada em como você pode criar e preencher essa estrutura de dados.

Usando a função deque()

Para criar um deque em Python, você pode usar a função interna deque() do módulo collections. Essa função retorna um novo objeto deque vazio que você pode usar para implementar uma fila dupla.

Aqui está um exemplo de como criar um objeto deque vazio:

from collections import deque 

my_deque = deque() 

Você também pode criar um deque com elementos iniciais passando um iterável (lista, tupla, etc.) para a função deque() . O deque será inicializado com os elementos do iterável, da esquerda para a direita.

Aqui está um exemplo:

from collections import deque

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

Inicializando um Deque com Elementos

Você também pode inicializar um deque vazio com elementos usando vários métodos. Uma maneira de fazer isso é usar os métodos append() e appendleft() para adicionar elementos ao deque dos lados direito e esquerdo, respectivamente.

Aqui está um exemplo:

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)

Após executar este código, o deque conterá os elementos [3, 1, 2].

Outra forma de inicializar um deque com elementos é passar uma lista de elementos para a função deque() .

Aqui está um exemplo:

from collections import deque

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

A execução desse código criará um objeto deque contendo os elementos [1, 2, 3] .

No geral, criar e inicializar um deque em Python é simples e pode ser feito usando a função integrada deque() . Você também pode fazer isso adicionando elementos a um deque vazio usando os métodos append() e appendleft() .

Como realizar operações comuns de deque

Existem muitas operações que você pode executar em objetos deque em Python. Vamos verificar alguns dos mais populares.

Adicionando elementos a um Deque

Você pode adicionar elementos a um deque do Python usando os métodos append() e appendleft() . O método append() adiciona um elemento à extremidade direita do deque, enquanto o método appendleft() adiciona um elemento à extremidade esquerda do deque.

Aqui está um exemplo:

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

Adding Multiple Data Elements to A Deque

If you don’t want to add data elements to a deque one by one, you can speed up the process with the extend() or extendleft() functions. These functions take in an iterable and append the iterable’s content to the end or left end of the deque respectively.

Here’s an example:

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 the code above the extend() function appends the multiple values in the cont tuple to the end of the deque. Next, the extendleft() function appends the multiple data elements in the full list to the left end of the deque.

Removing Elements from a Deque

You can remove elements from a Python deque using the pop() and popleft() methods. The pop() method removes and returns the rightmost element of the deque while the popleft() method removes and returns the leftmost element of the deque.

Here’s an example:

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

You can also remove a specific value from a deque using the remove() function. The function removes the first occurrence of the specified value from the deque.

Here’s an example:

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

If the element is not found, Python will return a ValueError.

Removing All Elements From a Deque

To remove all the elements from a Deque and return it to an empty state, we can use the clear() function. Here’s how it works:

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

Para usar um deque como uma fila, você pode usar o método append() para adicionar elementos à extremidade direita do deque. Além disso, você pode usar o método popleft() para remover elementos da extremidade esquerda do deque.

Esta é uma maneira muito eficiente de implementar uma fila em Python. Aqui está um exemplo:

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

Como você pode ver, o método append() adiciona elementos à extremidade direita do deque e o método popleft() remove elementos da extremidade esquerda do deque.

Isso é exatamente o que precisamos em uma implementação de fila.

Verificando se uma Fila Deque está Vazia

Para verificar se um deque está vazio, você pode usar o operador not . Aqui está um exemplo:

from collections import deque 

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

Isso resultará em “ Queue is empty ” porque o deque está vazio. Se você adicionar elementos ao deque, ele não ficará mais vazio.

Concluindo, usar um deque como uma fila em Python é muito eficiente e fácil de implementar.

Trabalhando com Deque como uma pilha

Assim como as filas, as pilhas são outro exemplo de tipos de dados abstratos que você pode usar na organização de dados. Ao contrário das filas, as pilhas operam no estilo LIFO (last in first out).

Isso significa que o último elemento no deque será o primeiro elemento a sair. Veja como você pode implementar isso usando a estrutura de dados subjacente.

Usando métodos append() e pop()

Ao usar Deque como uma pilha, você pode adicionar elementos ao topo da pilha usando o método append() . Esse método adiciona o elemento à extremidade direita do deque.

Da mesma forma, você pode remover elementos do topo da pilha usando o método pop() . Este método remove e retorna o elemento mais à direita do deque.

Por exemplo, digamos que você tenha um deque chamado “ my_stack ” e queira adicionar um elemento ao topo da pilha. Você pode usar o seguinte código:

 my_stack.append(5) 

Isso adicionará o elemento 5 ao topo da pilha.

Se você deseja remover o elemento superior da pilha, pode usar o método pop(): `

bal = my_stack.pop() 

print(bal)
# Output: 5

Isso removerá e retornará o elemento mais à direita do deque, que neste caso é 5.

Verificando um Objeto Deque Vazio

Você pode verificar se uma pilha deque está vazia usando o operador booleano “ not ”. Se o deque estiver vazio, “ not my_deque ” retornará True . Caso contrário, retornará False .

Por exemplo, digamos que você tenha uma pilha de deque chamada “ my_deque ” e queira verificar se ela está vazia. Você pode usar o seguinte código:

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

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

Isso imprimirá “ O deque está vazio ” se o deque estiver vazio. Se não estiver vazio, a saída será “ O deque não está vazio ”.

Ao trabalhar com Deque como uma pilha, é importante acompanhar se a pilha está vazia ou não. Se você tentar retirar um elemento de uma pilha vazia, receberá um IndexError .

O que é um Deque Restrito?

Um deque restrito é uma fila de duas extremidades com algumas restrições colocadas em operações de acréscimo e pop de dados em cada extremidade do deque. Existem dois tipos principais de deques restritos; Deque restrito de entrada e deque restrito de saída

Vejamos eles:

Deque restrito de entrada

Um deque com restrição de entrada permite que você remova ou exclua elementos de dados de ambas as extremidades do deque. No entanto, você só pode inserir elementos de dados de uma extremidade do deque.

Isso é muito útil em aplicativos com restrições de memória. Você pode usá-lo para adicionar elementos de dados em ordem cronológica, mantendo a capacidade de descartar dados de qualquer extremidade do deque.

Saída Restrita Deque

Um deque com restrição de saída permite inserir dados de ambas as extremidades do deque. No entanto, você só pode excluir itens de uma extremidade do deque, chamada de front-end.

Um deque com restrição de saída é muito útil nos casos em que você precisa implementar uma estrutura de dados FIFO, mas ainda deseja a funcionalidade de anexar dados de ambas as extremidades.

Vamos Encerrar Isso

Até agora, você deve ter um bom entendimento do módulo deque em Python e como ele pode ser usado para implementar filas e pilhas eficientes.

Deques são estruturas de dados versáteis que oferecem muitas vantagens em relação às listas tradicionais. Essas vantagens são aparentes quando se trata de operações append e pop com eficiência de memória.

Eles também são uma ótima opção quando você precisa implementar uma pilha ou uma fila dupla. Alguns dos principais benefícios do uso de deques incluem:

• Eficiente O(1) append e pop de ambas as extremidades do deque

• Acesso rápido O(1) ao primeiro e último elementos do deque

• Suporte integrado para operações atômicas thread-safe

• Métodos flexíveis para inserir, remover e girar elementos no deque

No geral, o módulo deque é uma ferramenta poderosa que pode ajudá-lo a escrever um código Python mais eficiente e sustentável. Esteja você trabalhando em um pequeno script ou em um projeto de grande escala, definitivamente vale a pena considerar os deques como uma alternativa às listas tradicionais ou outras estruturas de dados!

Pronto para aprender mais sobre Python, confira nossa playlist abaixo