Um estudante de computação precisa resolver um problema bastante importante, que é executar as operações que estão descritas abaixo, cuja estrutura é uma pilha inicialmente vazia. Tão logo ele retire algum elemento desta pilha, estes deverão ser inseridos em uma fila também inicialmente vazia. A sequência de operações invocadas é: push P, push E, push R, push T, push O, pop, pop, push S, push S, push L, pop, pop, pop. Qual o estado final da fila após essa execução?

Passo 1

Temos uma pilha e uma fila, ambas inicialmente vazias. A sequência de operações é:
push \mathrm{P}, push \mathrm{E}, push \mathrm{R}, push \mathrm{T}, push \mathrm{O}, pop, pop, push \mathrm{S}, push \mathrm{S}, push \mathrm{L}, pop, pop, pop.
Sempre que fazemos pop na pilha, o elemento retirado é enfileirado na fila. Vamos simular em blocos: primeiro as operações iniciais de push, depois os primeiros pops, em seguida os pushes intermediários e, por fim, os pops finais.

Passo 2

Após as cinco primeiras operações de push, a pilha contém (do fundo para o topo):
[\mathrm{P}, \mathrm{E}, \mathrm{R}, \mathrm{T}, \mathrm{O}]
e a fila ainda está vazia.

Passo 3

Aplicando os dois primeiros pop:
  • pop remove \mathrm{O} da pilha e enfileira na fila.
  • pop remove \mathrm{T} da pilha e enfileira na fila.
    Agora
\text{pilha} = [\mathrm{P}, \mathrm{E}, \mathrm{R}], \quad \text{fila} = [\mathrm{O}, \mathrm{T}].

Passo 4

Em seguida, fazemos push \mathrm{S}, push \mathrm{S} e push \mathrm{L}. A pilha passa a ser
[\mathrm{P}, \mathrm{E}, \mathrm{R}, \mathrm{S}, \mathrm{S}, \mathrm{L}],
enquanto a fila permanece [\mathrm{O}, \mathrm{T}].

Passo 5

Fazemos então três pop finais:
  • pop remove \mathrm{L} e enfileira: fila vira [\mathrm{O}, \mathrm{T}, \mathrm{L}].
  • pop remove o primeiro \mathrm{S} e enfileira: fila vira [\mathrm{O}, \mathrm{T}, \mathrm{L}, \mathrm{S}].
  • pop remove o segundo \mathrm{S} e enfileira: fila vira [\mathrm{O}, \mathrm{T}, \mathrm{L}, \mathrm{S}, \mathrm{S}].

Resposta

O estado final da fila é:
[\mathrm{O}, \mathrm{T}, \mathrm{L}, \mathrm{S}, \mathrm{S}].

Exercícios relacionados