Dado uma pilha que armazene números, escreva uma função que forneça o maior, o menor e a média aritmética dos elementos da pilha.
Passo 1
O enunciado pede uma função que, dada uma pilha (stack) de números, retorne seu valor máximo, mínimo e a média aritmética dos elementos. O conteúdo envolvido é estruturas de dados (pilha) e algoritmos de varredura sequencial, e vamos precisar usar operações básicas de pilha: push, pop, top e isEmpty.
Passo 2
Para não perder os elementos originais da pilha enquanto iteramos sobre eles, vamos usar uma pilha auxiliar. Assim, ao retirar cada elemento da pilha principal, guardamos esse valor na pilha auxiliar e atualizamos nossos indicadores (mínimo, máximo, soma e contador).
Começamos inicializando as variáveis de controle: o mínimo com +∞, o máximo com –∞, a soma acumulada com 0 e o contador de elementos com 0.
Começamos inicializando as variáveis de controle: o mínimo com +∞, o máximo com –∞, a soma acumulada com 0 e o contador de elementos com 0.
Passo 3
Enquanto a pilha principal não estiver vazia, fazemos:
- x ← pop(pilha_principal)
- atualizar mínimo: se x < min então min ← x
- atualizar máximo: se x > max então max ← x
- soma ← soma + x
- contador ← contador + 1
- push(auxiliar, x)
Passo 4
Depois de esvaziar a pilha principal, teremos todos os elementos na pilha auxiliar e os indicadores corretamente ajustados. Agora precisamos restaurar a pilha principal. Enquanto a pilha auxiliar não estiver vazia, fazemos pop(auxiliar) e push(pilha_principal, valor).
Passo 5
Com suma e contador em mãos, calculamos a média aritmética usando a fórmula:
onde
Por fim, retornamos os três valores (mínimo, máximo e média) em uma estrutura adequada (por exemplo, um registro ou tupla).
Resposta
Segue um pseudocódigo em estilo imperativo para a função getStats:
function getStats(pilha_principal):
pilha_aux ← new Stack()
min ← +∞
max ← -∞
soma ← 0
n ← 0
pilha_aux ← new Stack()
min ← +∞
max ← -∞
soma ← 0
n ← 0
while not isEmpty(pilha_principal):
x ← pop(pilha_principal)
if x < min:
min ← x
if x > max:
max ← x
soma ← soma + x
n ← n + 1
push(pilha_aux, x)
while not isEmpty(pilha_aux):
x ← pop(pilha_aux)
push(pilha_principal, x)
media ← soma / n
return (min, max, media)
Complexidade: O(n) de tempo e O(n) de espaço extra (para a pilha auxiliar).