Projete um TAD (defina as operações) que use uma lista duplamente encadeada que possa funcionar como uma fila.

Passo 1

O enunciado pede para projetar um TAD de fila usando lista duplamente encadeada. O conteúdo envolve conceitos de fila (FIFO) e lista duplamente encadeada. Vamos precisar definir a estrutura interna (nó com ponteiros para anterior e próximo) e as operações típicas de uma fila (criar, enfileirar, desenfileirar, frente, vazio e liberar).

Passo 2

Uma fila é uma coleção FIFO (First In, First Out). Numa lista duplamente encadeada cada nó guarda um elemento e dois ponteiros: um para o nó anterior e outro para o próximo. Essa estrutura permite inserção no fim e remoção no início em tempo constante.
Definimos dois tipos básicos:
  • Nó com campos:
Node: info: Tipo, prev: Nodeast, next: Nodeast
  • Fila com dois ponteiros:
Queue: head: Nodeast, tail: Nodeast
A invariante de representação é que, se a fila estiver vazia, head = tail = NULL; caso contrário, head aponta para o primeiro nó e tail para o último.

Passo 3

Agora definimos as operações do TAD, cada uma com pré e pós-condição.
  1. criarFila(): inicializa uma fila vazia.
    Pré-condição: nenhuma.
    Pós-condição: retorna fila com head = tail = NULL.
  2. estaVazia(f): checa se a fila f está vazia.
    Pré-condição: fila válida.
    Pós-condição: retorna verdadeiro se fhead = NULL, senão falso.
  3. enfileirar(f, x): insere elemento x no final de f.
    Pré-condição: fila válida.
    Pós-condição: novo nó contendo x foi anexado após tail; se estiver vazia, head e tail passam a apontar para esse nó.
  4. desenfileirar(f): remove o elemento do início de f.
    Pré-condição: fila não vazia.
    Pós-condição: nó originalmente em head é removido e liberado; head passa a apontar para o próximo; se ficar vazia, tail = NULL.
  5. frente(f): retorna o elemento no início de f sem removê-lo.
    Pré-condição: fila não vazia.
    Pós-condição: retorna headinfo, fila inalterada.
  6. liberarFila(f): esvazia completamente e libera memória.
    Pré-condição: fila válida.
    Pós-condição: todos os nós são liberados; head = tail = NULL.

Resposta

TAD Fila usando lista duplamente encadeada:
Tipos:
Node = info: Tipo; prev: Nodeast; next: Nodeast
Queue = head: Nodeast; tail: Nodeast
Operações:
  1. criarFila(): Queue
    • Pré: –
    • Pós: retorna fila com head = tail = NULL
  2. estaVazia(f: Queue): Bool
    • Pré: f válida
    • Pós: verdadeiro se f.head = NULL, senão falso
  3. enfileirar(f: Queue, x: Tipo): Queue
    • Pré: f válida
    • Pós: insere nó com info = x no fim; atualiza tail (e head se estava vazia)
  4. desenfileirar(f: Queue): Queue
    • Pré: f não vazia
    • Pós: remove nó em head; atualiza head (e tail se ficar vazia)
  5. frente(f: Queue): Tipo
    • Pré: f não vazia
    • Pós: retorna f.head.info sem alterar f
  6. liberarFila(f: Queue): –
    • Pré: f válida
    • Pós: libera todos os nós; head = tail = NULL
Complexidade de todas as operações principais (enfileirar, desenfileirar, frente, vazio) é O(1).

Exercícios relacionados