Implementação de Fila com Pilhas (LeetCode 232)

Para simular o comportamento FIFO (First-In-First-Out) de uma fila utilizando estruturas LIFO (Last-In-First-Out), a abordagem mais eficiente requer o uso de duas pilhas. Uma pilha é dedicada exclusivamente para receber novos elementos (inStack), enquanto a outra é responsável por fornecer os elementos na ordem de saída (outStack).

A lógica central reside na transferência de elementos: sempre que for necessário remover ou visualizar o elemento da frente e a outStack estiver vazia, todos os elementos da inStack são transferidos para a outStack. Isso inverte a ordem dos elementos, alinhando-os perfeitamente com a semântica de uma fila.

#include <stack>

class CustomQueue {
private:
    std::stack<int> inStack;
    std::stack<int> outStack;

    void transferElements() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
    }

public:
    CustomQueue() {}
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        transferElements();
        int frontElement = outStack.top();
        outStack.pop();
        return frontElement;
    }
    
    int peek() {
        transferElements();
        return outStack.top();
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

Implementação de Pilha com Filas (LeetCode 225)

Emular o comportamento LIFO de uma pilha utilizando uma única fila FIFO é perfeitamente viável. A estratégia mais direta consiste em manter a ordem de inserção normal durante a operação de push, mas reorganizar os elementos internamente durante a operação de pop.

Ao remover um elemento, o objetivo é acessar o último ittem inserido. Para isso, calculamos o tamanho atual da fila e movemos os primeiros N - 1 elementos para o final da própria fila. O elemento que restar na frente será o último que entrou, caracterizando o comportamento de uma pilha.

#include <queue>

class CustomStack {
private:
    std::queue<int> dataQueue;

public:
    CustomStack() {}
    
    void push(int x) {
        dataQueue.push(x);
    }
    
    int pop() {
        int currentSize = dataQueue.size();
        for (int i = 0; i < currentSize - 1; ++i) {
            dataQueue.push(dataQueue.front());
            dataQueue.pop();
        }
        int topElement = dataQueue.front();
        dataQueue.pop();
        return topElement;
    }
    
    int top() {
        return dataQueue.back();
    }
    
    bool empty() {
        return dataQueue.empty();
    }
};

Validação de Parênteses Ballanceados (LeetCode 20)

A verificação de parênteses balanceados é um caso clássico de aplicação de pilhas. A solução percorre a string caractere por caractere. Ao encontrar um parêntese de abertura, o respectivo parêntese de fechamento correspondente é empilhado. Ao encontrar um caractere de fechamento, verifica-se se a pilha está vazia ou se o topo da pilha não corresponde ao caractere atual.

É crucial realizar uma poda inicial: se o comprimento da string for ímpar, ela nunca poderá ser válida. Além disso, a ordem das verificações condicionais é fundamental; verificar se a pilha está vazia antes de acessar o elemento do topo evita exceções de execução em casos como ) no início da string.

#include <string>
#include <stack>

class ParenthesesValidator {
public:
    bool isValid(const std::string& s) {
        if (s.length() % 2 != 0) return false;
        
        std::stack<char> bracketStack;
        
        for (char c : s) {
            if (c == '(') bracketStack.push(')');
            else if (c == '{') bracketStack.push('}');
            else if (c == '[') bracketStack.push(']');
            else {
                if (bracketStack.empty() || bracketStack.top() != c) {
                    return false;
                }
                bracketStack.pop();
            }
        }
        
        return bracketStack.empty();
    }
};

Remoção de Duplicatas Adjacentes (LeetCode 1047)

Para eliminar caarcteres duplicados e adjacentes em uma string, podemos utilizar a própria string de resultado como uma estrutura de pilha. A ideia é iterar sobre a string original e comparar cada caractere com o último caractere adicionado à string de resultado.

Se houver correspondência, o caractere duplicado é removido (operação de pop). Caso contrário, o novo caractere é anexado (operação de push). Essa abordagem elimina a necessidade de uma pilha separada e evita a etapa de inversão da string no final, resultando em um código mais limpo e performático.

#include <string>

class DuplicateRemover {
public:
    std::string removeDuplicates(const std::string& s) {
        std::string processed;
        
        for (char c : s) {
            if (!processed.empty() && processed.back() == c) {
                processed.pop_back();
            } else {
                processed.push_back(c);
            }
        }
        
        return processed;
    }
};