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.

Passo 3

Enquanto a pilha principal não estiver vazia, fazemos:
  1. x ← pop(pilha_principal)
  2. atualizar mínimo: se x < min então min ← x
  3. atualizar máximo: se x > max então max ← x
  4. soma ← soma + x
  5. contador ← contador + 1
  6. 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:
x = sum xin
onde n é o contador de elementos.
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
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).

Exercícios relacionados