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 é:
(tras + 1) % tamanho == frente
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.

Exercícios relacionados