Para fechar esta unidade, vemos o TAD Deque (double-ended queue, fila de duas pontas): uma generalização de pilhas e filas, que permite inserir e remover em ambas as extremidades.

1. O TAD Deque

Um deque não impõe a restrição LIFO da pilha nem a restrição FIFO da fila — ele simplesmente permite operar nas duas pontas, deixando a cargo de quem usa o deque decidir que disciplina (LIFO, FIFO, ou uma mistura) faz sentido para o problema:

insere/remove aqui                    insere/remove aqui
        |                                     |
        v                                     v
     +-------+     +-------+     +-------+
     |   A   | --> |   B   | --> |   C   |
     +-------+     +-------+     +-------+

Operações

Repare que uma pilha nada mais é do que um deque em que só usamos insereInicio/removeInicio (ou só insereFim/removeFim); e uma fila é um deque em que usamos insereFim para inserir e removeInicio para remover. O deque é, portanto, mais geral que as duas estruturas anteriores.

2. Implementação: reaproveitando a lista duplamente encadeada

Para que todas as quatro operações de inserção/remoção sejam O(1), precisamos de acesso direto às duas pontas e capacidade de andar nos dois sentidos — exatamente o que a ListaDupla da Aula 6a já oferece. Não é por acaso: um deque é, na prática, uma lista duplamente encadeada usada através de uma interface mais restrita.

// Reaproveitando NodoD e ListaDupla da Aula 6a
typedef ListaDupla Deque;

void inicializa(Deque *d)                          { inicializa(d); }
int  estaVazio(Deque *d)                            { return d->ini == NULL; }
int  insereInicioDeque(Deque *d, Produto prod)      { return insereInicio(d, prod); }
int  insereFimDeque(Deque *d, Produto prod)         { return insereFim(d, prod); }

3. Aplicações

• Histórico de navegação com "voltar" e "avançar" nos dois sentidos (como já mencionado na Aula 6a) pode ser modelado como um deque;
• Algoritmos de janela deslizante (por exemplo, encontrar o máximo em cada sub-intervalo de tamanho fixo de um vetor) costumam usar um deque para inserir/remover elementos em ambas as pontas conforme a janela se move;
• Escalonadores com work stealing: cada processo/thread mantém uma fila de tarefas em formato de deque — insere e remove suas próprias tarefas de uma ponta, enquanto outros processos ociosos podem "roubar" tarefas da ponta oposta.

Resumo

Exercícios

1. Explique por que uma pilha e uma fila podem ser vistas como "casos particulares" de um deque.
2. Por que a lista duplamente encadeada da Aula 6a é uma base natural para implementar um deque, e não a lista simplesmente encadeada da Aula 4?
3. Se você tivesse que implementar um deque usando um vetor (em vez de lista encadeada), que problema da fila por vetor (Aula 9b) você esperaria enfrentar novamente, e como o resolveria?
4. Implemente uma função int removeInicio(Deque *d, Produto *prodRemovido) que remova o primeiro elemento de um deque (baseado em ListaDupla), devolvendo o produto removido via prodRemovido.
5. Implemente o deque por vetor circular. Defina a struct DequeVet, com um vetor de capacidade fixa (CAPACIDADE), um índice frente e uma quantidade qtd de elementos (no mesmo estilo da FilaVet da Aula 9b), e implemente inicializa, estaVazio, insereFim e removeInicio. Depois, implemente também insereInicio e removeFim — as duas novas operações que um deque tem e uma fila não tem. Dica: para "andar para trás" a partir de frente sem obter um índice negativo, use (frente - 1 + CAPACIDADE) % CAPACIDADE.

Sugestões de Respostas dos Exercícios

int removeInicio(Deque *d, Produto *prodRemovido) {
    NodoD *removido;

    if (d->ini == NULL) // deque vazio
        return 0;

    removido = d->ini;
    *prodRemovido = removido->dado;

    d->ini = removido->prox;
    if (d->ini != NULL)
        d->ini->ant = NULL;
    else
        d->fim = NULL; // deque ficou vazio

    free(removido);
    return 1;
}

#define CAPACIDADE 5

typedef struct {
    Produto dados[CAPACIDADE];
    int frente;
    int qtd;
} DequeVet;

void inicializa(DequeVet *d) {
    d->frente = 0;
    d->qtd = 0;
}

int estaVazio(DequeVet *d) {
    return d->qtd == 0;
}

int insereFim(DequeVet *d, Produto valor) {
    int posicaoFinal;

    if (d->qtd == CAPACIDADE)
        return 0;

    posicaoFinal = (d->frente + d->qtd) % CAPACIDADE;
    d->dados[posicaoFinal] = valor;
    d->qtd++;
    return 1;
}

int removeInicio(DequeVet *d, Produto *valorRemovido) {
    if (estaVazio(d))
        return 0;

    *valorRemovido = d->dados[d->frente];
    d->frente = (d->frente + 1) % CAPACIDADE;
    d->qtd--;
    return 1;
}

// As duas operações "novas" em relação à FilaVet da Aula 9b:

int insereInicio(DequeVet *d, Produto valor) {
    if (d->qtd == CAPACIDADE)
        return 0;

    d->frente = (d->frente - 1 + CAPACIDADE) % CAPACIDADE; // "anda para trás"
    d->dados[d->frente] = valor;
    d->qtd++;
    return 1;
}

int removeFim(DequeVet *d, Produto *valorRemovido) {
    int posicaoFinal;

    if (estaVazio(d))
        return 0;

    posicaoFinal = (d->frente + d->qtd - 1) % CAPACIDADE;
    *valorRemovido = d->dados[posicaoFinal];
    d->qtd--;
    return 1;
}