Desenvolva uma função para inverter a posição dos elementos de uma pilha
.
Passo 1
A questão pede para criar uma função que receba uma pilha P e inverta completamente a ordem dos seus elementos. O conteúdo aqui envolve estruturas de dados (pilha) e operações básicas de LIFO (Last In, First Out): push, pop e isEmpty. Vamos usar recursão para resolver sem usar estruturas auxiliares explícitas.
Passo 2
Antes de codificar, vale entender o que significa inverter uma pilha: se P tiver, de cima para baixo, [a₁, a₂, …, aₙ], queremos que ela fique [aₙ, …, a₂, a₁]. Como só podemos acessar o topo, a ideia é “desempilhar” um a um, inverter o restante e depois inserir cada elemento no fundo da pilha.
Passo 3
A estratégia recursiva funciona assim: 1) Se P estiver vazia, nada a fazer. 2) Caso contrário, removemos o elemento do topo (x = pop). 3) Chamamos recursivamente invert§ para inverter o que restou. 4) Por fim, colocamos x no fundo da pilha invertida.
Passo 4
Para colocar x no fundo, usamos uma função auxiliar insertAtBottom(P, x): 1) Se P estiver vazia, fazemos push(x). 2) Caso contrário, retiramos o topo (y = pop), chamamos recursivamente insertAtBottom(P, x) e depois empilhamos y de volta.
Com essa lógica, todos os elementos acima de x serão retirados, x será inserido no fundo e então os elementos retirados voltam na mesma ordem, garantindo a inversão completa.
Com essa lógica, todos os elementos acima de x serão retirados, x será inserido no fundo e então os elementos retirados voltam na mesma ordem, garantindo a inversão completa.
Resposta
// Pseudocódigo em estilo imperativo
função insertAtBottom(Pilha P, elemento x)
se P.isEmpty() então
P.push(x)
senão
y ← P.pop()
insertAtBottom(P, x)
P.push(y)
se P.isEmpty() então
P.push(x)
senão
y ← P.pop()
insertAtBottom(P, x)
P.push(y)
função invert(Pilha P)
se P.isEmpty() então
retorne
senão
x ← P.pop()
invert§
insertAtBottom(P, x)
se P.isEmpty() então
retorne
senão
x ← P.pop()
invert§
insertAtBottom(P, x)