Este artigo explora como podemos construir uma fila usando pilhas e, inversamente, uma pilha usando filas. Este exercício prático ajuda a solidificar o entendimento das propriedades fundamentais dessas estruturas de dados abstratas: First-In, First-Out (FIFO) para filas e Last-In, First-Out (LIFO) para pilhas.

Construindo uma Fila Usando Duas Pilhas

Uma fila é uma estrutura de dados FIFO, onde o primeiro elemento a ser inserido é o primeiro a ser removido. As pilhas, por outro lado, seguem o princípio LIFO. Para simular o comportamento de uma fila com pilhas, podemos utilizar duas pilhas:

1. Uma pilha de entrada (pilhaEntrada) para operações de inserção (enfileirar).
2. Uma pilha de saída (pilhaSaida) para operações de remoção e consulta do elemento da frente (desenfileirar e frente).

A lógica principal reside na operação de remoção. Quando um elemento precisa ser removido ou consultado da frente da fila, verificamos a pilha de saída. Se ela estiver vazia, todos os elementos da pilha de entrada são transferidos para a pilha de saída. Essa transferência inverte a ordem dos elementos, fazendo com que o elemento mais antigo (o "frente" da fila) fique no topo da pilha de saída. Se a pilha de saída já contiver elementos, eles são simplesmente desempilahdos ou consultados diretamente.

Exemplo de Implementação em Java: Fila com Pilhas

import java.util.Stack;

class FilaUsandoPilhas {
    private Stack<Integer> pilhaEntrada; // Usada para operações de inserção (enfileirar)
    private Stack<Integer> pilhaSaida;   // Usada para operações de remoção (desenfileirar)

    public FilaUsandoPilhas() {
        pilhaEntrada = new Stack<>();
        pilhaSaida = new Stack<>();
    }

    /**
     * Adiciona um elemento ao final da fila.
     * @param elemento O valor a ser adicionado.
     */
    public void enfileirar(int elemento) {
        pilhaEntrada.push(elemento);
    }

    /**
     * Remove e retorna o elemento da frente da fila.
     * @return O elemento removido da frente da fila.
     */
    public int desenfileirar() {
        // Garante que a pilha de saída esteja pronta para entregar o elemento mais antigo.
        transferirElementosSeNecessario();
        return pilhaSaida.pop();
    }

    /**
     * Retorna o elemento da frente da fila sem removê-lo.
     * @return O elemento na frente da fila.
     */
    public int frente() {
        // Garante que a pilha de saída esteja pronta para mostrar o elemento mais antigo.
        transferirElementosSeNecessario();
        return pilhaSaida.peek();
    }

    /**
     * Verifica se a fila está vazia.
     * @return true se a fila não contiver elementos, false caso contrário.
     */
    public boolean estaVazia() {
        return pilhaEntrada.isEmpty() && pilhaSaida.isEmpty();
    }

    // Método auxiliar para transferir elementos de pilhaEntrada para pilhaSaida.
    // Isso é feito apenas quando pilhaSaida está vazia para manter a ordem FIFO.
    private void transferirElementosSeNecessario() {
        if (pilhaSaida.isEmpty()) {
            while (!pilhaEntrada.isEmpty()) {
                pilhaSaida.push(pilhaEntrada.pop());
            }
        }
    }

    public static void main(String[] args) {
        FilaUsandoPilhas minhaFila = new FilaUsandoPilhas();
        minhaFila.enfileirar(10);
        minhaFila.enfileirar(20);
        System.out.println("Elemento na frente: " + minhaFila.frente()); // Saída: 10
        System.out.println("Removido: " + minhaFila.desenfileirar());   // Saída: 10
        System.out.println("A fila está vazia? " + minhaFila.estaVazia()); // Saída: false
        minhaFila.enfileirar(30);
        System.out.println("Elemento na frente: " + minhaFila.frente()); // Saída: 20
        System.out.println("Removido: " + minhaFila.desenfileirar());   // Saída: 20
        System.out.println("Removido: " + minhaFila.desenfileirar());   // Saída: 30
        System.out.println("A fila está vazia? " + minhaFila.estaVazia()); // Saída: true
    }
}

Construindo uma Pilha Usando Filas

Uma pilha é uma estrutura de dados LIFO, onde o último elemento a ser inserido é o primeiro a ser removido. As filas, por outro lado, seguem o princípio FIFO. Podemos simular uma pilha usando filas de duas maneiras principais: com duas filas ou com uma única fila.

Abordagem com Duas Filas

Utilizamos duas filas, uma principal (filaPrincipal) e uma auxiliar (filaAuxiliar). A ideia é que a operação de inserção (empilhar) seja simples, mas a de remoção (desempilhar) exija um reordenamento para garantir o comportamento LIFO.

1. Na operação de empilhar, simplesmente adicionamos o novo elemento à filaPrincipal e atualizamos uma variável ultimoAdicionado para manter o controle do topo da pilha.
2. Na operação de desempilhar, movemos todos os elementos da filaPrincipal para a filaAuxiliar, exceto o último. O último elemento da filaPrincipal é o topo da pilha, que então é removido. Após a remoção, as referências das filas são trocadas (filaAuxiliar se torna a nova filaPrincipal), e a variável ultimoAdicionado é atualizada para o último elemento movido.
3. A operação de consultarTopo simplesmente retorna o valor de ultimoAdicionado.
4. A operação estaVazia verifica se a filaPrincipal está vazia.

Exemplo de Implementação em Java: Pilha com Duas Filas

import java.util.LinkedList;
import java.util.Queue;

class PilhaComDuasFilas {
    private Queue<Integer> filaPrincipal; // Fila principal que armazena os elementos
    private Queue<Integer> filaAuxiliar;  // Fila auxiliar usada durante operações de desempilhar
    private int ultimoAdicionado;         // Mantém o valor do elemento mais recentemente adicionado (topo da pilha)

    public PilhaComDuasFilas() {
        filaPrincipal = new LinkedList<>();
        filaAuxiliar = new LinkedList<>();
    }
    
    /**
     * Adiciona um elemento ao topo da pilha.
     * @param x O valor a ser empilhado.
     */
    public void empilhar(int x) {
        filaPrincipal.offer(x); // Adiciona à fila principal
        ultimoAdicionado = x;   // Atualiza o último elemento adicionado
    }
    
    /**
     * Remove e retorna o elemento do topo da pilha.
     * @return O elemento desempilhado.
     */
    public int desempilhar() {
        // Move todos os elementos da filaPrincipal para filaAuxiliar, exceto o último.
        // O penúltimo elemento se tornará o novo 'ultimoAdicionado' (novo topo).
        while (filaPrincipal.size() > 1) {
            ultimoAdicionado = filaPrincipal.poll(); // Remove da principal e adiciona à auxiliar
            filaAuxiliar.offer(ultimoAdicionado);
        }
        
        int elementoRemovido = filaPrincipal.poll(); // Remove o último elemento (o topo original)
        
        // Troca as referências das filas: filaAuxiliar se torna a nova filaPrincipal
        // e filaPrincipal (agora vazia) se torna a nova filaAuxiliar.
        Queue<Integer> temp = filaPrincipal;
        filaPrincipal = filaAuxiliar;
        filaAuxiliar = temp;
        
        return elementoRemovido;
    }
    
    /**
     * Retorna o elemento do topo da pilha sem removê-lo.
     * @return O elemento no topo da pilha.
     */
    public int consultarTopo() {
        return ultimoAdicionado;
    }
    
    /**
     * Verifica se a pilha está vazia.
     * @return true se a pilha não contiver elementos, false caso contrário.
     */
    public boolean estaVazia() {
        return filaPrincipal.isEmpty();
    }

    public static void main(String[] args) {
        PilhaComDuasFilas minhaPilha = new PilhaComDuasFilas();
        minhaPilha.empilhar(100);
        minhaPilha.empilhar(200);
        System.out.println("Topo da pilha: " + minhaPilha.consultarTopo()); // Saída: 200
        System.out.println("Desempilhado: " + minhaPilha.desempilhar()); // Saída: 200
        System.out.println("A pilha está vazia? " + minhaPilha.estaVazia()); // Saída: false
        System.out.println("Topo da pilha: " + minhaPilha.consultarTopo()); // Saída: 100
        System.out.println("Desempilhado: " + minhaPilha.desempilhar()); // Saída: 100
        System.out.println("A pilha está vazia? " + minhaPilha.estaVazia()); // Saída: true
    }
}

Abordagem com Uma Única Fila

Com uma única fila, a complexidade é transferida para a operação de inserção (empilhar). O objetivo é garantir que o elemento recém-adicionado esteja sempre na frente da fila, simulando o topo da pilha.

1. Na operação de empilhar, o novo elemento é adicionado ao final da fila. Em seguida, para manter a propriedade LIFO, todos os elementos que estavam anteriormente na fila são removidos de sua posição atual (frente) e adicionados de volta ao final da fila. Isso efetivamente "rotaciona" a fila, colocando o elemento recém-adicionado na frente.
2. A operação de desempilhar é simples, pois o elemento na frente da fila já é o topo da pilha (o último a ser adicionado).
3. A operação de consultarTopo retorna o elemento da frente da fila sem removê-lo.
4. A operação estaVazia verifica se a fila está vazia.

Exemplo de Implementação em Java: Pilha com Uma Única Fila

import java.util.LinkedList;
import java.util.Queue;

class PilhaComUmaFila {
    private Queue<Integer> filaUnica; // A única fila usada para simular a pilha

    public PilhaComUmaFila() {
        filaUnica = new LinkedList<>();
    }
    
    /**
     * Adiciona um elemento ao topo da pilha.
     * @param valor O valor a ser empilhado.
     */
    public void empilhar(int valor) {
        int tamanhoAtual = filaUnica.size();
        filaUnica.offer(valor); // Adiciona o novo elemento ao final da fila
        
        // Gira a fila: remove os 'tamanhoAtual' elementos anteriores e os adiciona de volta.
        // Isso faz com que o novo elemento (o 'valor' recém-adicionado) seja o primeiro da fila,
        // simulando o topo da pilha (LIFO).
        for (int i = 0; i < tamanhoAtual; i++) {
            filaUnica.offer(filaUnica.poll());
        }
    }
    
    /**
     * Remove e retorna o elemento do topo da pilha.
     * @return O elemento desempilhado.
     */
    public int desempilhar() {
        // Como o elemento do topo da pilha é sempre o primeiro da fila (devido à lógica de empilhar),
        // basta removê-lo.
        return filaUnica.poll();
    }
    
    /**
     * Retorna o elemento do topo da pilha sem removê-lo.
     * @return O elemento no topo da pilha.
     */
    public int consultarTopo() {
        // O topo da pilha é o primeiro elemento da fila.
        return filaUnica.peek();
    }
    
    /**
     * Verifica se a pilha está vazia.
     * @return true se a pilha não contiver elementos, false caso contrário.
     */
    public boolean estaVazia() {
        return filaUnica.isEmpty();
    }

    public static void main(String[] args) {
        PilhaComUmaFila minhaPilha = new PilhaComUmaFila();
        minhaPilha.empilhar(5);
        minhaPilha.empilhar(10);
        System.out.println("Topo da pilha: " + minhaPilha.consultarTopo()); // Saída: 10
        System.out.println("Desempilhado: " + minhaPilha.desempilhar()); // Saída: 10
        System.out.println("A pilha está vazia? " + minhaPilha.estaVazia()); // Saída: false
        System.out.println("Topo da pilha: " + minhaPilha.consultarTopo()); // Saída: 5
        System.out.println("Desempilhado: " + minhaPilha.desempilhar()); // Saída: 5
        System.out.println("A pilha está vazia? " + minhaPilha.estaVazia()); // Saída: true
    }
}