Como usar a deque do Python?

[

Python’s deque: Implementar filas e pilhas eficientes

Se você trabalha frequentemente com listas em Python, provavelmente sabe que elas não têm um desempenho rápido o suficiente quando você precisa retirar (pop) e adicionar (append) itens no início da lista. O módulo collections do Python fornece uma classe chamada deque que foi especialmente projetada para fornecer formas rápidas e eficientes de anexar e remover itens de ambos os extremos da estrutura de dados subjacente.

O deque do Python é uma fila de dois extremos otimizada e de baixo nível que é útil para implementar filas e pilhas elegantes, eficientes e com a sintaxe do Python, que são os tipos de dados de lista mais comuns na computação.

Neste tutorial, você aprenderá:

Como criar e usar o deque do Python em seu código
Como anexar e remover itens eficientemente de ambos os extremos de um deque
Como usar deque para construir filas e pilhas eficientes
Quando vale a pena usar o deque em vez da lista

Finalmente, você escreverá alguns exemplos que mostram alguns casos de uso comuns do deque, que é um dos tipos de dados mais poderosos do Python.

Começando com o `deque` do Python

Anexar itens ao final e removê-los é uma operação normalmente eficiente em uma lista do Python. Se usarmos a notação Big O para complexidade de tempo, podemos dizer que essas operações são O (1). No entanto, quando o Python precisa realocar memória para aumentar a lista subjacente para aceitar novos itens, essas operações ficam mais lentas e podem se tornar O (n).

Além disso, anexar e remover itens no início de uma lista do Python são conhecidos por serem operações ineficientes com velocidade O (n).

O deque é uma fila bidirecional e oferece desempenho próximo de O (1) tanto para anexar quanto para remover itens de ambos os extremos. Isso ocorre porque o deque é implementado como uma lista vinculada internamente. Em vez de realocar memória quando a lista subjacente está cheia, o deque aloca novos blocos de memória em vez disso, mantendo assim as operações de inserção e remoção rápidas.

O módulo collections é parte da biblioteca padrão do Python. Portanto, não é necessário instalar nada adicional para usar o deque em seus projetos.

Para começar a usar o deque, você precisa importar o módulo collections e, em seguida, criar uma instância do deque, como mostrado no exemplo a seguir:

from collections import deque

my_deque = deque()

Agora você está pronto para usar o deque em seu código. Vamos explorar suas características e funcionalidades mais a fundo.

Anexando e Removendo Itens Eficientemente

Os dois principais métodos que você usará com o deque são .append() e .pop(), que funcionam da mesma forma que os métodos correspondentes de uma lista do Python.

O método .append() é usado para anexar um item ao final do deque. Por exemplo:

my_deque.append('item')

Da mesma forma, o método .pop() é usado para remover o último item do deque e retorná-lo. Se você não passar nenhum índice como argumento, o .pop() remove o último item:

removed_item = my_deque.pop()

Você também pode passar um índice para o .pop() para remover um item específico do deque:

removed_item = my_deque.pop(0)

Lembre-se de que quando você remove um item do deque usando o .pop(), ele é removido da extremidade oposta à que você está anexando itens. Isso ocorre porque o deque é uma fila bidirecional, ou seja, você pode anexar e remover itens de ambos os extremos da fila.

O deque também permite anexar e remover itens no início da fila de maneira eficiente, usando os métodos .appendleft() e .popleft(), respectivamente. Por exemplo:

my_deque.appendleft('item')

removed_item = my_deque.popleft()

Esses métodos funcionam da mesma forma que o .append() e o .pop(), mas utilizam a extremidade oposta do deque.

Vamos ver um exemplo completo para entender melhor como usar o deque:

from collections import deque

# Cria um deque vazio
my_deque = deque()

# Anexa itens ao final do deque
my_deque.append('item1')
my_deque.append('item2')
my_deque.append('item3')

# Remove o último item do deque
removed_item = my_deque.pop()

# Anexa um item no início do deque
my_deque.appendleft('item4')

# Remove o primeiro item do deque
removed_item = my_deque.popleft()

# Imprime o deque final
print(my_deque)

A saída será:

deque(['item4', 'item2'])

Como você pode ver, o deque mantém a ordem dos itens corretamente e os métodos .append(), .pop(), .appendleft() e .popleft() funcionaram corretamente.

Acessando Itens Aleatórios em um `deque`

Além de anexar e remover itens de ambos os sentidos do deque, você também pode acessar itens específicos de maneira eficiente, da mesma forma que faria com uma lista do Python.

Como o deque é implementado como uma lista vinculada internamente, o acesso aos itens no deque é uma operação de tempo constante O (1), independentemente do índice do item que você está acessando.

Para acessar um item em um deque, você pode usar a mesma sintaxe que usaria para acessar um item em uma lista:

my_item = my_deque[index]

Onde index é a posição do item que você deseja acessar. Lembre-se de que a primeira posição é 0.

Se você tentar acessar um item fora dos limites do deque, ou seja, usando um índice maior ou igual ao tamanho do deque, uma exceção IndexError será levantada.

Se você quiser acessar o primeiro item sem removê-lo do deque, pode usar o atributo .peek():

first_item = my_deque[0]

Esse método é útil quando você deseja apenas verificar um item no início da fila sem removê-lo do deque.

Vamos ver um exemplo completo para entender melhor como acessar itens em um deque:

from collections import deque

# Cria um deque com alguns itens
my_deque = deque(['item1', 'item2', 'item3', 'item4'])

# Acessa o primeiro item
first_item = my_deque[0]

# Acessa o segundo item
second_item = my_deque[1]

# Acessa o último item
last_item = my_deque[-1]

# Acessa um item fora dos limites do deque
out_of_range_item = my_deque[10]

A execução desse código elevará uma exceção IndexError, porque estamos tentando acessar um item fora dos limites do deque.

Construindo Filas e Pilhas Eficientes com o `deque`

Uma das principais razões para usar o deque em vez de uma lista do Python é a eficiência ao construir filas e pilhas. O deque permite anexar e remover itens rapidamente de ambos os extremos da fila, sem realocar memória.

Para construir uma fila eficiente com o deque, você usaria os métodos .append() e .popleft(). Por exemplo:

from collections import deque

# Cria uma fila (ou fila FIFO) vazia
my_queue = deque()

# Adiciona itens à fila
my_queue.append('item1')
my_queue.append('item2')
my_queue.append('item3')

# Remove itens da fila
removed_item = my_queue.popleft()

Aqui, você está usando o .append() para adicionar itens no final da fila e o .popleft() para remover itens do início da fila. Esses métodos são muito rápidos e eficientes porque o deque é implementado como uma lista vinculada internamente.

Da mesma forma, para construir uma pilha eficiente com o deque, você usaria os métodos .append() e .pop(). Por exemplo:

from collections import deque

# Cria uma pilha (ou pilha LIFO) vazia
my_stack = deque()

# Adiciona itens à pilha
my_stack.append('item1')
my_stack.append('item2')
my_stack.append('item3')

# Remove itens da pilha
removed_item = my_stack.pop()

Aqui, você está usando o .append() para adicionar itens no final da pilha e o .pop() para remover itens do final da pilha. Mais uma vez, esses métodos são muito rápidos e eficientes graças à implementação do deque como uma lista vinculada.

Explorando Outras Funcionalidades do `deque`

Além das funcionalidades básicas de adicionar e remover itens, o deque também oferece outras funcionalidades importantes que podem ser úteis em diferentes situações. Vamos dar uma olhada em algumas delas:

Limitando o Número Máximo de Itens: `.maxlen`

Ao criar um deque, você pode especificar um número máximo de itens que ele pode conter usando o argumento maxlen. Se você definir um valor para maxlen, o deque rejeitará automaticamente os itens mais antigos quando atingir o limite especificado. Por exemplo:

from collections import deque

# Cria um deque com uma capacidade máxima de 3 itens
limited_deque = deque(maxlen=3)

# Adiciona itens ao deque
limited_deque.append('item1')
limited_deque.append('item2')
limited_deque.append('item3')

# Adiciona mais um item
limited_deque.append('item4')

# Adeque logará os itens mais antigos automaticamente, mantendo apenas os últimos 3 itens
print(limited_deque)

A saída será:

deque(['item2', 'item3', 'item4'], maxlen=3)

Neste exemplo, o deque foi definido com uma capacidade máxima de 3 itens usando o argumento maxlen. Quando o quarto item é adicionado, o deque automaticamente descarta o item mais antigo e mantém apenas os últimos 3 itens.

Essa funcionalidade é útil quando você precisa manter um histórico limitado de itens ou quando deseja definir um tamanho máximo fixo para uma fila ou pilha.

Girando os Itens: `.rotate()`

Outra funcionalidade interessante oferecida pelo deque é a capacidade de girar os itens em torno do deque em uma determinada quantidade de posições. Isso pode ser útil em situações em que você precisa deslocar os itens em uma fila ou uma pilha.

O método .rotate() aceita um argumento opcional que especifica o número de posições para girar os itens. Se o argumento for positivo, os itens serão girados para a direita, enquanto se for negativo, os itens serão girados para a esquerda. Por exemplo:

from collections import deque

# Cria um deque com alguns itens
my_deque = deque(['item1', 'item2', 'item3'])

# Gira os itens em uma posição para a direita
my_deque.rotate(1)

# Gira os itens em duas posições para a esquerda
my_deque.rotate(-2)

# Gira os itens em três posições para a direita
my_deque.rotate(3)

# Imprime o deque final
print(my_deque)

A saída será:

deque(['item2', 'item3', 'item1'])

Neste exemplo, você cria um deque com alguns itens e, em seguida, usa o método .rotate() para girar os itens. Note que se você usar um argumento maior do que o tamanho do deque, ele irá ajustá-lo automaticamente para evitar erros.

Adicionando Vários Itens de Uma Vez: `.extendleft()`

Além de adicionar um item por vez usando o método .append() ou .appendleft(), você também pode adicionar vários itens de uma vez ao deque usando o método .extendleft(). Esse método aceita um iterável como argumento e adiciona cada item no iterável ao início do deque na ordem em que estão. Por exemplo:

from collections import deque

# Cria um deque vazio
my_deque = deque()

# Adiciona vários itens ao início do deque
my_deque.extendleft(['item1', 'item2', 'item3'])

# Imprime o deque final
print(my_deque)

A saída será:

deque(['item3', 'item2', 'item1'])

Ao usar o .extendleft(), é importante observar que a ordem dos itens no iterável é preservada ao serem adicionados ao deque. Isso significa que o último item do iterável será o primeiro item no deque.

Usando as Funcionalidades de Lista do Python no `deque`

Embora o deque seja uma fila bidirecional e ofereça funcionalidades especiais para adicionar e remover itens de seus dois extremos, ele também pode ser usado como uma lista normal do Python quando necessário.

O deque herda todas as funcionalidades de lista do Python, como len(), in e slicing. Isso permite que você use o deque como uma lista completa quando necessário.

Por exemplo, você pode verificar o tamanho de um deque usando a função len():

my_deque = deque(['item1', 'item2', 'item3'])

# Verifica o tamanho do deque
deque_size = len(my_deque)

Da mesma forma, você também pode verificar se um item está presente em um deque usando o operador in:

my_deque = deque(['item1', 'item2', 'item3'])

# Verifica se 'item2' está no deque
item_present = 'item2' in my_deque

Você também pode usar a sintaxe de fatiamento (slicing) para acessar uma parte específica do deque:

my_deque = deque(['item1', 'item2', 'item3'])

# Acessa apenas os dois primeiros itens do deque
two_items = my_deque[:2]

Essas funcionalidades permitem que você use o deque como uma lista completa quando necessário, aproveitando suas vantagens de desempenho ao mesmo tempo que se beneficia das funcionalidades da lista.

Colocando o `deque` do Python em Ação

Agora que você entende os conceitos fundamentais do deque e como usá-lo, vamos explorar algumas situações comuns em que o deque pode ser útil.

Mantendo um Histórico de Páginas

Suponha que você esteja desenvolvendo um navegador web e precisa manter um histórico das páginas visitadas pelo usuário. O deque é perfeito para essa situação, pois permite adicionar as páginas visitadas ao final do deque e remover as páginas mais antigas quando o limite especificado for atingido.

from collections import deque

# Cria um deque com uma capacidade máxima de 10 itens
page_history = deque(maxlen=10)

# Simula a navegação do usuário
page_history.append('https://google.com')
page_history.append('https://github.com')
page_history.append('https://facebook.com')

# Imprime o histórico de páginas
print(page_history)

A saída será:

Neste exemplo, você cria um deque com uma capacidade máxima de 10 itens, simulando o histórico de páginas visitadas pelo usuário. À medida que o usuário visita novas páginas, elas são adicionadas ao final do deque. Quando o deque atinge o limite de 10 itens, as páginas mais antigas são automaticamente removidas.

Compartilhando Dados Entre Threads

Se você estiver trabalhando com programação multithread em Python e precisar compartilhar dados entre diferentes threads, o deque é uma ótima opção, pois é seguro para uso simultâneo por várias threads.

O deque fornece operações atômicas para adicionar e remover itens sem a preocupação de conflitos de acesso simultâneo entre as threads. Isso o torna uma escolha adequada para implementar buffers entre threads produtoras e consumidores.

Vejamos um exemplo simples em que duas threads compartilham um deque para adicionar e remover itens:

import threading
from collections import deque

# Cria um deque como buffer compartilhado entre as duas threads
shared_buffer = deque()

# Função para adicionar itens ao buffer
def producer():
    for i in range(100):
        shared_buffer.append(i)
    print("Producer finished")

# Função para remover itens do buffer
def consumer():
    while True:
        try:
            item = shared_buffer.popleft()
            print("Consumed:", item)
        except IndexError:
            break
    print("Consumer finished")

# Cria as duas threads
producer_thread = threading.Thread(target=producer)
consumer_thread = threading.Thread(target=consumer)

# Inicia as threads
producer_thread.start()
consumer_thread.start()

# Espera as threads terminarem
producer_thread.join()
consumer_thread.join()

Neste exemplo, você cria um deque como um buffer compartilhado entre duas threads. A função producer() adiciona itens ao buffer usando o .append(), enquanto a função consumer() remove itens do buffer usando o .popleft().

O uso do deque garante que as operações de adição e remoção sejam atomicamente seguras entre as threads e evita possíveis conflitos de acesso simultâneo.

Emulando o Comando `tail`

Suponha que você precise implementar a funcionalidade do comando tail do Linux, que permite visualizar as últimas linhas de um arquivo em tempo real. O deque pode ser útil para essa tarefa, pois permite manter uma “janela deslizante” de tamanho fixo das linhas lidas.

from collections import deque

# Tamanho da "janela deslizante" em número de linhas
window_size = 10

# Cria um deque vazio para armazenar as linhas
lines_buffer = deque(maxlen=window_size)

# Itera sobre as linhas do arquivo
with open('filename.txt') as file:
    for line in file:
        lines_buffer.append(line)

# Imprime as linhas armazenadas no buffer
for line in lines_buffer:
    print(line)

Neste exemplo, você cria um deque vazio com uma capacidade máxima igual ao tamanho da “janela deslizante”. Em seguida, lê as linhas de um arquivo e as adiciona ao final do deque.

Ao final, você itera sobre as linhas armazenadas no deque e as imprime.

O deque garante que apenas as últimas linhas lidas sejam armazenadas no buffer. Quando um novo item é adicionado, o item mais antigo é automaticamente descartado, mantendo assim uma janela deslizante das últimas linhas.

Conclusão

Neste tutorial, você aprendeu a usar o deque do Python para implementar filas e pilhas eficientes. O deque oferece vantagens de desempenho ao anexar e remover itens de seus dois extremos, tornando-o ideal para construir pipelines de dados eficientes em Python.

Você aprendeu como anexar e remover itens do deque eficientemente, tanto no início quanto no final da fila. Também exploramos outras funcionalidades importantes, como limitar o número máximo de itens, girar os itens e adicionar vários itens de uma vez.

Além disso, você aprendeu como usar o deque para manter um histórico de páginas visitadas, compartilhar dados entre threads e emular a funcionalidade do comando tail do Linux.

Lembre-se de que, embora o deque possa ser usado como uma lista completa e ofereça funcionalidades semelhantes às listas do Python, é projetado principalmente para otimizar operações de anexar e remover itens de ambos os extremos.

Agora você pode aproveitar ao máximo o deque do Python e implementar filas e pilhas eficientes em seus projetos!

Como usar a deque do Python?

Python’s deque: Implementar filas e pilhas eficientes

Começando com o deque do Python

Anexando e Removendo Itens Eficientemente

Acessando Itens Aleatórios em um deque

Construindo Filas e Pilhas Eficientes com o deque

Explorando Outras Funcionalidades do deque

Limitando o Número Máximo de Itens: .maxlen

Girando os Itens: .rotate()

Adicionando Vários Itens de Uma Vez: .extendleft()

Usando as Funcionalidades de Lista do Python no deque

Colocando o deque do Python em Ação

Mantendo um Histórico de Páginas

Compartilhando Dados Entre Threads

Emulando o Comando tail

Conclusão

Começando com o `deque` do Python

Acessando Itens Aleatórios em um `deque`

Construindo Filas e Pilhas Eficientes com o `deque`

Explorando Outras Funcionalidades do `deque`

Limitando o Número Máximo de Itens: `.maxlen`

Girando os Itens: `.rotate()`

Adicionando Vários Itens de Uma Vez: `.extendleft()`

Usando as Funcionalidades de Lista do Python no `deque`

Colocando o `deque` do Python em Ação

Emulando o Comando `tail`