1. Ordenação por Recursão (sem pilha extra)

A abordagem recursiva consiste em remover o topo da pilha, ordenar o restante e então inserir o elemento removido na posição correta dentro da pilha já ordenada.

void ordenarPilha(Pilha& p) {
    if (p.topo != p.base) {
        int valor = 0;
        pop(p, valor);
        ordenarPilha(p);
        inserirOrdenado(p, valor);
    }
}

void inserirOrdenado(Pilha& p, int x) {
    if (p.topo == p.base || getTop(p) <= x) {
        push(p, x);
    } else {
        int temp = 0;
        pop(p, temp);
        inserirOrdenado(p, x);
        push(p, temp);
    }
}

Princípio: A recursão reduz o problema a subproblemas menores. Cada elemento é removido e depois reintroduzdio na posição correta, garantindo que a pilha cresça ordenada durante o retorno das chamadas recursivas.

• Complexidade Temporal: O(n²), pois cada elemento pode ser movido múltiplas vezes.
• Complexidade Espacial: O(n) devido ao uso da pilha de chamadas recursivas.

2. Ordenação com Pilha Auxiliar

Esta solução utiliza uma segunda pilha para armazenar os elementos em ordem crescente. Os elementos são retirados da pilha original e colocados na pilha auxiliar na posição correta, movendo elementos maiores de volta para a pilha original quando necessário.

void ordenarComAuxiliar(Pilha& p) {
    Pilha aux;
    init(aux);

    while (p.topo > p.base) {
        int item = 0;
        pop(p, item);

        if (aux.topo == aux.base || getTop(aux) >= item) {
            push(aux, item);
        } else {
            while (aux.topo != aux.base && getTop(aux) < item) {
                int temp = 0;
                pop(aux, temp);
                push(p, temp);
            }
            push(aux, item);
        }
    }

    // Transferir todos os elementos da pilha auxiliar de volta
    while (aux.topo != aux.base) {
        int val = 0;
        pop(aux, val);
        push(p, val);
    }
}

Princípio: A pilha auxiliar mantém os elementos em ordem decrescente (do topo para baixo). Ao processar cada elemento da pilha original, elementos maiores são temporariamente devolvidos à pilha principal até encontrar um local adequado.

• Complexidade Temporal: O(n²) no pior caso (elementos em ordem decrescente).
• Complexidade Espacial: O(n) pela pilha auxiliar.

3. Uso de Fila como Estrutura Auxiliar

É possível implementar a ordenação usando uma fila como estrutura auxiliar. A ideia é extrair elementos da pilha e inserir na fila em ordem crescente, aproveitando a propriedade FIFO da fila. Após todos os elementos estarem na fila, eles são transferidos de volta para a pilha, resultando em uma pilha ordenada.

Apesar de não haver implementação detalhada aqui, a viabilidade é confirmada por modelos teóricos: como a fila permite acesso sequencial e controle de ordem, é possível simular uma inserção ordenada com operações limitadas. No entanto, a eficiência será afetada pelo número de operações necessárias para manter a ordem.

Este método é menos direto do que usar pilhas auxiliares, mas demonstra a flexibilidade dos tipos de estruturas de dados na resolução de problemas de ordenação com restrições.