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:
- Fila com dois ponteiros:
A invariante de representação é que, se a fila estiver vazia,
; caso contrário,
aponta para o primeiro nó e
para o último.
Passo 3
Agora definimos as operações do TAD, cada uma com pré e pós-condição.
- criarFila(): inicializa uma fila vazia.
Pré-condição: nenhuma.
Pós-condição: retorna fila com. - estaVazia(f): checa se a fila
está vazia.
Pré-condição: fila válida.
Pós-condição: retorna verdadeiro se, senão falso. - enfileirar(f, x): insere elemento
no final de .
Pré-condição: fila válida.
Pós-condição: novo nó contendofoi anexado após ; se estiver vazia, e passam a apontar para esse nó. - desenfileirar(f): remove o elemento do início de
.
Pré-condição: fila não vazia.
Pós-condição: nó originalmente emé removido e liberado; passa a apontar para o próximo; se ficar vazia, . - frente(f): retorna o elemento no início de
sem removê-lo.
Pré-condição: fila não vazia.
Pós-condição: retorna, fila inalterada. - 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;.
Resposta
TAD Fila usando lista duplamente encadeada:
Tipos:
Operações:
-
criarFila(): Queue
- Pré: –
- Pós: retorna fila com head = tail = NULL
-
estaVazia(f: Queue): Bool
- Pré: f válida
- Pós: verdadeiro se f.head = NULL, senão falso
-
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)
-
desenfileirar(f: Queue): Queue
- Pré: f não vazia
- Pós: remove nó em head; atualiza head (e tail se ficar vazia)
-
frente(f: Queue): Tipo
- Pré: f não vazia
- Pós: retorna f.head.info sem alterar f
-
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).