Implemente a função reverso, que reposiciona os elementos na fila de tal forma que o início da fila torna-se o fim, e vice-versa
Passo 1
Estamos em uma situação de estruturas de dados, onde precisamos escrever uma função que receba uma fila e a inverta completamente: o primeiro vira o último e vice-versa.
Passo 2
Uma forma bem direta de fazer isso é usar uma pilha auxiliar. Como pilha é LIFO (último a entrar, primeiro a sair), se a gente empilhar todos os elementos da fila e depois desempilhar de volta na fila, a ordem fica invertida.
Primeiro, vamos esvaziar a fila original, removendo cada elemento com a operação de desenfileirar (dequeue), e empilhando-o na pilha (push). Ao fim desse loop, a fila estará vazia e a pilha terá todos os elementos na ordem que queremos para reinserir.
Primeiro, vamos esvaziar a fila original, removendo cada elemento com a operação de desenfileirar (dequeue), e empilhando-o na pilha (push). Ao fim desse loop, a fila estará vazia e a pilha terá todos os elementos na ordem que queremos para reinserir.
Passo 3
Em seguida, basta desempilhar (pop) cada elemento da pilha e enfileirar (enqueue) de volta na fila. Como a pilha devolve primeiro o último elemento inserido, a fila vai receber os itens em ordem reversa à original.
No final do segundo loop, a fila estará totalmente invertida em relação à sua ordem inicial. Essa solução usa apenas operações básicas de fila e pilha e roda em tempo O(n), onde n é o número de elementos.
No final do segundo loop, a fila estará totalmente invertida em relação à sua ordem inicial. Essa solução usa apenas operações básicas de fila e pilha e roda em tempo O(n), onde n é o número de elementos.
Passo 4
Vamos ver a implementação em pseudocódigo dividindo em duas fases: esvaziar na pilha e recarregar na fila.
Resposta
função reverso(fila):
pilha ← nova Pilha()
enquanto fila não estiver vazia:
elemento ← fila.desenfileirar()
pilha.empilhar(elemento)
enquanto pilha não estiver vazia:
elemento ← pilha.desempilhar()
fila.enfileirar(elemento)
retornar fila
pilha ← nova Pilha()
enquanto fila não estiver vazia:
elemento ← fila.desenfileirar()
pilha.empilhar(elemento)
enquanto pilha não estiver vazia:
elemento ← pilha.desempilhar()
fila.enfileirar(elemento)
retornar fila