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.

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

Exercícios relacionados