Implemente um algoritmo que teste se duas pilhas são ou não iguais. O algoritmo deve retornar o valor 1 se as duas pilhas forem iguais, e 0 caso contrário. Ao final da execução, as duas pilhas devem estar no mesmo estado em que estavam no início.
Passo 1
Beleza, vamos resumir o que a questão pede e o que vamos precisar para resolver. Precisamos criar um algoritmo que verifica se duas pilhas são iguais. Se forem iguais, o algoritmo retorna 1; se não, retorna 0. Além disso, no final, as duas pilhas devem continuar exatamente como estavam no início. Para resolver isso, vamos precisar entender como funcionam as operações básicas de pilha, como
push
(adicionar) e pop
(remover), e também como podemos comparar elementos de duas pilhas sem destruir seu estado original.Passo 2
Primeiro, vamos pensar em como comparar duas pilhas. A ideia é verificar se ambos têm o mesmo número de elementos e se cada par de elementos correspondentes é igual. Para fazer isso, vamos precisar desempilhar os elementos de ambas as pilhas simultaneamente e comparar cada par. Se encontrarmos algum par que não seja igual, sabemos que as pilhas não são iguais.
Passo 3
Mas tem um detalhe importante: no final, precisamos que as pilhas fiquem exatamente como estavam. Então, como fazemos isso sem perder os elementos? A solução é usar uma pilha temporária. Enquanto comparamos os elementos, vamos empurrando-os para uma terceira pilha. Depois de terminar a comparação, vamos devolver os elementos das pilhas temporárias para as pilhas originais usando outra pilha temporária. Isso garante que as pilhas iniciais fiquem inalteradas.
Passo 4
Vamos detalhar o passo a passo do algoritmo:
- Verificar o tamanho das pilhas: Se tiverem tamanhos diferentes, já sabemos que não são iguais, retorna 0.
- Comparar elemento por elemento:
- Enquanto nenhuma das pilhas estiver vazia:
- Desempilha o elemento do topo de cada pilha.
- Compara os dois elementos. Se forem diferentes, retorna 0.
- Empilha esses elementos em uma pilha temporária para restaurar depois.
- Enquanto nenhuma das pilhas estiver vazia:
- Restaurar as pilhas originais:
- Desempilha os elementos da pilha temporária e empilha de volta nas pilhas originais.
- Se todas as comparações forem iguais, retorna 1.
Passo 5
Vamos agora traduzir isso para um pseudocódigo para deixar mais claro:
função pilhasIguais(pilha1, pilha2):
se pilha1.tamanho() != pilha2.tamanho():
retorna 0
temporaria = nova Pilha
enquanto não pilha1.vazia():
elemento1 = pilha1.pop()
elemento2 = pilha2.pop()
se elemento1 != elemento2:
// Restaurar as pilhas antes de retornar
temporaria.empilha(elemento1)
temporaria.empilha(elemento2)
enquanto não temporaria.vazia():
pilha1.empilha(temporaria.pop())
pilha2.empilha(temporaria.pop())
retorna 0
temporaria.empilha(elemento1)
temporaria.empilha(elemento2)
// Restaurar as pilhas
enquanto não temporaria.vazia():
pilha1.empilha(temporaria.pop())
pilha2.empilha(temporaria.pop())
retorna 1
Resposta
O algoritmo retorna
1
se as duas pilhas forem iguais e 0
caso contrário, mantendo as pilhas no estado inicial após a execução.