Problema: Implementar uma fila FIFO utilizando apenas duas pilhas. A fila deve suportar as operações push, pop, peek e empty.

A seguir, apresentam-se duas soluções em Java.

Abordagem 1: Uso de duas pilhas com inversão completa durante o push

Nesta abordagem, uma pilha principal armazena os elementos na ordem FIFO após cada inserção. Ao adicionar um novo elemento, todos os elementos existentes são transferidos temporariamente para uma pilha auxiliar, o novo elemento é colocado na pilha principal, e os elementos são devolvidos. As operações de remoção e consulta são realizadas diretamente na pilha principal.

class FilaComPilhas {
    private Deque<Integer> pilhaPrincipal;
    private Deque<Integer> pilhaAuxiliar;

    public FilaComPilhas() {
        pilhaPrincipal = new LinkedList<>();
        pilhaAuxiliar = new LinkedList<>();
    }

    public void push(int valor) {
        while (!pilhaPrincipal.isEmpty()) {
            pilhaAuxiliar.push(pilhaPrincipal.pop());
        }
        pilhaPrincipal.push(valor);
        while (!pilhaAuxiliar.isEmpty()) {
            pilhaPrincipal.push(pilhaAuxiliar.pop());
        }
    }

    public int pop() {
        if (empty()) {
            return -1; // Indica estado inválido
        }
        return pilhaPrincipal.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        return pilhaPrincipal.peek();
    }

    public boolean empty() {
        return pilhaPrincipal.isEmpty();
    }
}

Abordagem 2: Uso de duas pilhas com transferência sob demanda

Nesta versão otimizada, uma pilha é dedicada a inserções e outra a remoções. Os elementos são transferidos da pilha de inserção para a pilha de remoção apenas quando necessário, o que reduz a complexidade amortizada das operações.

class FilaComPilhasOtimizada {
    private Deque<Integer> pilhaInsercao;
    private Deque<Integer> pilhaRemocao;
    private int elementoFrente;

    public FilaComPilhasOtimizada() {
        pilhaInsercao = new LinkedList<>();
        pilhaRemocao = new LinkedList<>();
    }

    public void push(int valor) {
        if (pilhaInsercao.isEmpty()) {
            elementoFrente = valor;
        }
        pilhaInsercao.push(valor);
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (pilhaRemocao.isEmpty()) {
            while (!pilhaInsercao.isEmpty()) {
                pilhaRemocao.push(pilhaInsercao.pop());
            }
        }
        return pilhaRemocao.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (pilhaRemocao.isEmpty()) {
            return elementoFrente;
        }
        return pilhaRemocao.peek();
    }

    public boolean empty() {
        return pilhaInsercao.isEmpty() && pilhaRemocao.isEmpty();
    }
}