Um deque é uma lista linear na qual os elementos podem ser inseridos ou removidos de qualquer extremo. Baseando-se na implementação circular de filas, implemente algoritmos para manipulação de deques. Os algoritmos devem ser de inicialização, teste de fila cheia ou vazia, inserir à esquerda, inserir à direita, remover à esquerda e remover à esquerda.
Passo 1
Beleza, vamos lá! O enunciado pede para a gente implementar um deque, que é tipo uma fila onde dá pra inserir e remover elementos tanto do começo quanto do fim. Isso é útil quando você precisa de mais flexibilidade na manipulação dos dados. A matéria aqui envolve estruturas de dados lineares, especificamente filas circulares. Vamos precisar entender como uma fila circular funciona e adaptar isso para permitir inserções e remoções dos dois lados.
Passo 2
Primeiro, vamos inicializar o deque. Para isso, vamos usar um array de tamanho fixo e dois ponteiros,
frente
e tras
, que vão indicar onde estão os elementos no início e no fim do deque. Inicialmente, esses ponteiros vão estar no mesmo lugar, indicando que o deque está vazio.def inicializar_deque(tamanho):
deque = [None] * tamanho
frente = tras = -1
return deque, frente, tras
Passo 3
Agora, precisamos de uma função para verificar se o deque está cheio. Em uma fila circular, a fila está cheia quando o próximo índice de
tras
é igual a frente
. Isso significa que não temos mais espaço para adicionar novos elementos.A fórmula para verificar isso é:
def esta_cheio(frente, tras, tamanho):
return (tras + 1) % tamanho == frente
Passo 4
Também precisamos verificar se o deque está vazio. Isso acontece quando
frente
e tras
apontam para o mesmo lugar e não há elementos. Inicialmente, ambos são -1
.def esta_vazio(frente, tras):
return frente == -1
Passo 5
Vamos criar a função para inserir um elemento à esquerda. Se o deque estiver cheio, a gente não consegue inserir. Se estiver vazio, ajustamos ambos os ponteiros para o primeiro elemento. Caso contrário, movemos o ponteiro
frente
para a posição anterior de forma circular.def inserir_esquerda(deque, frente, tras, tamanho, elemento):
if esta_cheio(frente, tras, tamanho):
print("Deque está cheio!")
return frente, tras
if esta_vazio(frente, tras):
frente = tras = 0
else:
frente = (frente - 1 + tamanho) % tamanho
deque[frente] = elemento
return frente, tras
Passo 6
Agora, vamos inserir à direita. A lógica é similar à inserção à esquerda, mas movemos o ponteiro
tras
para a próxima posição.def inserir_direita(deque, frente, tras, tamanho, elemento):
if esta_cheio(frente, tras, tamanho):
print("Deque está cheio!")
return frente, tras
if esta_vazio(frente, tras):
frente = tras = 0
else:
tras = (tras + 1) % tamanho
deque[tras] = elemento
return frente, tras
Passo 7
Para remover um elemento à esquerda, primeiro verificamos se o deque está vazio. Se não estiver, removemos o elemento na posição
frente
e movemos o ponteiro para a próxima posição. Se, após a remoção, frente
iguala tras
, isso significa que o deque ficou vazio, então ajustamos ambos para -1
.def remover_esquerda(deque, frente, tras, tamanho):
if esta_vazio(frente, tras):
print("Deque está vazio!")
return frente, tras, None
elemento = deque[frente]
if frente == tras:
frente = tras = -1
else:
frente = (frente + 1) % tamanho
return frente, tras, elemento
Passo 8
Finalmente, para remover à direita, verificamos se o deque está vazio. Se não estiver, removemos o elemento na posição
tras
e movemos o ponteiro tras
para a posição anterior de forma circular. Se frente
iguala tras
, ajustamos ambos para -1
.def remover_direita(deque, frente, tras, tamanho):
if esta_vazio(frente, tras):
print("Deque está vazio!")
return frente, tras, None
elemento = deque[tras]
if frente == tras:
frente = tras = -1
else:
tras = (tras - 1 + tamanho) % tamanho
return frente, tras, elemento
Resposta
Prontinho! Agora você tem todas as funções básicas para manipular um deque usando uma implementação circular de filas. Dessa forma, dá pra inserir e remover elementos tanto da esquerda quanto da direita de forma eficiente.