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
, push
, push
, push
, push
, pop, pop, push
, push
, push
, 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 , push
, push
, push
, push
, pop, pop, push
, push
, push
, 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.
push
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):
e a fila ainda está vazia.
Passo 3
Aplicando os dois primeiros pop:
- pop remove
da pilha e enfileira na fila. - pop remove
da pilha e enfileira na fila.
Agora
Passo 4
Em seguida, fazemos push
, push
e push
. A pilha passa a ser
enquanto a fila permanece
.
Passo 5
Fazemos então três pop finais:
- pop remove
e enfileira: fila vira . - pop remove o primeiro
e enfileira: fila vira . - pop remove o segundo
e enfileira: fila vira .
Resposta
O estado final da fila é: