Suponha que uma pilha possua 4 valores na seguinte ordem: 1, 2, 3 e 4. Qual seria a sequência correta de operações de inserção (I) e eliminação (E) para se obter os registros na ordem 243 1?

Passo 1

Temos como entrada a sequência de registros 1, 2, 3 e 4 e queremos gerar a saída 2, 4, 3, 1 usando uma pilha (LIFO) com operações de inserção (I) e eliminação (E).

Passo 2

Lembrando que numa pilha (Last In, First Out) só podemos remover (E) o elemento que está no topo, e para colocar um novo elemento no topo usamos inserção (I).

Passo 3

Para gerar o primeiro número 2 na saída, fazemos I para empilhar o 1, I para empilhar o 2, e em seguida E desfaz o topo, produzindo 2.

Passo 4

Depois de remover o 2, a pilha tem apenas o 1. Para gerar o 4 precisamos levar 3 e 4 ao topo: fazemos I (empilha 3) e I (empilha 4), então E retira o topo entregando 4. Agora a pilha contém 1 e 3, e dois E sucessivos removem primeiro o 3 e depois o 1, fechando a sequência.

Resposta

I I E I I E E E

Exercícios relacionados