Dado uma pilha que armazene números, escreva uma função para ordenar os valores da pilha em ordem crescente.
Passo 1
A questão pede ordenar em ordem crescente os valores armazenados em uma pilha usando só operações de pilha (push, pop, peek, isEmpty). O conteúdo é estrutura de dados (pilha) e vamos precisar de uma pilha auxiliar.
Passo 2
A ideia é parecida com insertion sort: a cada iteração, retiramos o topo da pilha original e o inserimos na pilha auxiliar de modo que ela permaneça sempre ordenada.
Para isso, criamos uma pilha auxiliar vazia. Enquanto a pilha original não estiver vazia, fazemos: retiramos o elemento tmp da original; então, movemos para a pilha original todos os elementos da auxiliar que sejam maiores que tmp; por fim, empilhamos tmp na auxiliar.
Para isso, criamos uma pilha auxiliar vazia. Enquanto a pilha original não estiver vazia, fazemos: retiramos o elemento tmp da original; então, movemos para a pilha original todos os elementos da auxiliar que sejam maiores que tmp; por fim, empilhamos tmp na auxiliar.
Passo 3
Assim garantimos que, a cada inserção, a pilha auxiliar fica com seus elementos em ordem crescente do topo para a base. No fim, basta retornar (ou substituir) a pilha original pela auxiliar.
Passo 4
O custo desse algoritmo é O(n²) no pior caso, pois para cada um dos n elementos podemos fazer até O(n) movimentos entre as pilhas.
Resposta
def sort_stack(stack):
"""
Recebe uma pilha 'stack' (por exemplo, uma lista em que o fim é o topo)
e retorna uma nova pilha com os mesmos elementos em ordem crescente,
sendo o menor elemento no topo.
"""
auxiliary = []
# Enquanto houver elementos na pilha original
while stack:
tmp = stack.pop()
# Move da auxiliar para a original tudo que for maior que tmp
while auxiliary and auxiliary[-1] > tmp:
stack.append(auxiliary.pop())
# Agora tmp pode ser empilhado na auxiliar na posição correta
auxiliary.append(tmp)
# 'auxiliary' está ordenada de forma crescente (topo é o menor)
return auxiliary