Fundamentos de Pilhas e Filas
O Princípio LIFO nas Pilhas
Uma pilha é uma coleção linear que segue o princípio Last-In, First-Out (último a entrar, primeiro a sair). Os elementos são inseridos e removidos exclusivamente pelo topo da estrutura. As operações fundamentais — inserção, remoção e consulta ao topo — possuem complexidade O(1).
Pilhas são amplamente utilizadas como estrutura auxiliar na implementação de algoritmos de busca em profundidade (DFS) e na conversão de algoritmos recursivos para versões iterativas. A recursão, por natureza, utiliza a pilha de chamadas do sistema operacional; cada chamada recursiva equivale a um empilhamento, e cada retorno equivale a um desempilhamento.
API da Pilha em C++
// Métodos disponíveis na classe std::stack
// Verifica se a estrutura está vazia
bool empty() const;
// Adiciona elemento ao topo - complexidade O(1)
void push(const value_type& elemento);
// Remove o elemento do topo - complexidade O(1)
void pop();
// Acessa o elemento do topo por referência
value_type& top();
Exemplo Básico de Uso
#include <stack>
#include <queue>
#include <iostream>
int main() {
// Demonstração com pilha
std::stack<int> pilhaExemplo;
pilhaExemplo.push(15);
pilhaExemplo.push(30);
int topoAtual = pilhaExemplo.top(); // retorna 30
// Demonstração com fila
std::queue<int> filaExemplo;
filaExemplo.push(15);
filaExemplo.push(30); // fila contém [15, 30]
int frenteAtual = filaExemplo.front(); // retorna 15
filaExemplo.pop(); // fila contém [30]
return 0;
}
O Princípio FIFO nas Filas
Uma fila segue o princípio First-In, First-Out (primeiro a entrar, primeiro a sair). Os elementos são inseridos na cauda e removidos pela cabeça. Todas as operações possuem complexidade O(1).
Filas são a estrutura fundamental para algoritmos de busca em largura (BFS). Além disso, servem como buffer em modelos produter-consumidor, onde um componente adiciona elementos ao final e outro consome pelo início. Em ambientes com múltiplas threads acessando a mesma fila, é necessário implementar mecanismos de sincronização.
Tanto pilhas quanto filas podem ser entendidas como listas ligadas com restrições de acesso. Quando as limitações dessas estruturas são muito rígidas para o problema em questão, pode-se recorrer a listas mais flexíveis.
Reconhecimento de Padrões
Leitura em ordem específica com duas pilhas: Quando se precisa de uma ordem de leitura diferente da LIFO padrão, é possível usar duas pilhas, transferindo elementos entre elas para reorganizar a sequência desejada.
Implementação de Pilha com Consulta de Máximo em O(1)
Construir uma pilha que suporte as operações padrão e também retorne o elemento máximo em tempo constante.
Estratégia: Utilizar duas pilhas simultaneamente. A primeira armazena todos os elementos normalmente. A segunda mantém apenas os valores máximos encontrados, atualizando-se conforme novos elementos maiores são inseridos.
Análise de complexidade: Todas as operações mantêm O(1) no tempo. No pior caso, a pilha auxiliar armazena todos os elementos, resultando em O(n) de espaço adicional.
#include <stack>
#include <iostream>
template<typename Tipo>
class PilhaComMaximo {
public:
Tipo consultarTopo() const {
return dadosPrincipal.top();
}
void desempilhar() {
if (!dadosMaximo.empty() && dadosMaximo.top() == dadosPrincipal.top()) {
dadosMaximo.pop();
}
dadosPrincipal.pop();
}
void empilhar(const Tipo& valor) {
if (dadosMaximo.empty() || dadosMaximo.top() < valor) {
dadosMaximo.push(valor);
}
dadosPrincipal.push(valor);
}
Tipo obterMaximo() const {
if (!dadosMaximo.empty()) {
return dadosMaximo.top();
}
return dadosPrincipal.top();
}
private:
std::stack<Tipo> dadosPrincipal;
std::stack<Tipo> dadosMaximo;
};
int main() {
PilhaComMaximo<int> pilha;
int elementos[] = {5, 42, 18, 42, 27, 10, -3, 55, 48, 20, 26, 31, 35};
for (int elem : elementos)
pilha.empilhar(elem);
std::cout << "Máximo: " << pilha.obterMaximo() << std::endl;
while (true) {
try {
std::cout << pilha.consultarTopo() << " | Max: "
<< pilha.obterMaximo() << std::endl;
pilha.desempilhar();
} catch (...) {
break;
}
}
return 0;
}
Fila Implementada com Duas Pilhas
Construir uma fila utilizando exclusivamente estruturas de pilha.
#include <stack>
#include <iostream>
template<typename Tipo>
class FilaViaPilhas {
public:
void enfileirar(const Tipo& valor) {
pilhaEntrada.push(valor);
}
Tipo desenfileirar() {
if (pilhaEntrada.empty()) {
throw std::runtime_error("Fila vazia");
}
// Transfere tudo para a pilha de saída, invertendo a ordem
while (!pilhaEntrada.empty()) {
pilhaSaida.push(pilhaEntrada.top());
pilhaEntrada.pop();
}
Tipo resultado = pilhaSaida.top();
pilhaSaida.pop();
// Devolve os elementos restantes à pilha de entrada
while (!pilhaSaida.empty()) {
pilhaEntrada.push(pilhaSaida.top());
pilhaSaida.pop();
}
return resultado;
}
bool estaVazia() const {
return pilhaEntrada.empty();
}
private:
std::stack<Tipo> pilhaEntrada;
std::stack<Tipo> pilhaSaida;
};
int main() {
FilaViaPilhas<int> fila;
int valores[] = {10, 20, 30, 40};
for (int v : valores)
fila.enfileirar(v);
while (!fila.estaVazia())
std::cout << fila.desenfileirar() << " ";
return 0;
}
Ordenação de Pilha com Pilha Auxiliar
Ordenar os elementos de uma pilha em ordem crescente (menor no topo), utilizando apenas uma pilha auxiliar como estrutura adicional.
Análise de complexidade: Para cada elemento, pode ser necessário transferir até n elementos entre as pilhas, resultando em complexidade O(n²).
#include <stack>
#include <iostream>
template<typename Tipo>
std::stack<Tipo> ordenarPilha(std::stack<Tipo>& entrada) {
std::stack<Tipo> organizada;
while (!entrada.empty()) {
Tipo elementoAtual = entrada.top();
entrada.pop();
// Move elementos menores de volta para a entrada
while (!organizada.empty() && organizada.top() < elementoAtual) {
entrada.push(organizada.top());
organizada.pop();
}
organizada.push(elementoAtual);
}
return organizada;
}
int main() {
std::stack<int> pilhaOriginal;
int dados[] = {8, 3, 7, 1, 9, 5};
for (int d : dados)
pilhaOriginal.push(d);
std::stack<int> resultado = ordenarPilha(pilhaOriginal);
while (!resultado.empty()) {
std::cout << resultado.top() << " ";
resultado.pop();
}
return 0;
}
Padrão "Salvar para Depois"
Existe uma categoria de problemas onde a solução de um nó depende dos nós seguintes. Se não se conhece o estado dos sucessores, não é possível obter uma resposta significativa para o nó atual. A pilha resolve naturalmente esse padrão: o nó atual é empilhado enquanto seus dependentes são processados. Quando todas as dependências estão satisfeitas, o nó é desempilhado para cálculo final. Em certos casos, o reslutado intermediário precisa ser reempilhado até que dependências adicionais sejam resolvidas.
Validação de Parênteses
Dada uma string contendo apenas os caracteres (, ), {, }, [ e ], determinar se a sequência de parênteses é válida.
#include <iostream>
#include <string>
#include <stack>
bool saoCorrespondentes(char abertura, char fechamento) {
return (abertura == '(' && fechamento == ')') ||
(abertura == '[' && fechamento == ']') ||
(abertura == '{' && fechamento == '}');
}
bool validarParenteses(const std::string& texto) {
std::stack<char> pilhaAux;
for (char simbolo : texto) {
// Caracteres de abertura vão para a pilha
if (simbolo == '(' || simbolo == '[' || simbolo == '{') {
pilhaAux.push(simbolo);
}
// Caracteres de fechamento precisam combinar com o topo
else if (simbolo == ')' || simbolo == ']' || simbolo == '}') {
if (pilhaAux.empty())
return false;
if (!saoCorrespondentes(pilhaAux.top(), simbolo))
return false;
pilhaAux.pop();
}
}
return pilhaAux.empty();
}
int main() {
std::cout << validarParenteses("((()))") << " "; // 1 (válido)
std::cout << validarParenteses("([)]") << " "; // 0 (inválido)
std::cout << validarParenteses("{[()]}") << " "; // 1 (válido)
std::cout << validarParenteses("(((") << " "; // 0 (inválido)
std::cout << std::endl;
return 0;
}
Eliminando Recursão com Pilhas: Estruturas Top-Down
Estruturas hierárquicas, como árvores, apresentam uma natureza top-down: a solução do nó depende das soluções dos filhos. A recursão é a abordagem natural, mas cada chamada recursiva consome espaço na pilha do sistema. Usar uma pilha explícita elimina esse overhead e oferece controle total sobre o fluxo de execução.
Percurso In-Order com Pilha
Realizar o percurso em-ordem (esquerda, raiz, direita) de uma árvore binária usando uma pilha auxiliar.
#include <iostream>
#include <stack>
struct NoArvore {
char valor;
NoArvore* esq;
NoArvore* dir;
NoArvore(char v) : valor(v), esq(nullptr), dir(nullptr) {}
};
void percorrerEmOrdem(NoArvore* raiz) {
std::stack<NoArvore*> pilhaNos;
NoArvore* corrente = raiz;
while (corrente != nullptr || !pilhaNos.empty()) {
// Desce o máximo possível à esquerda
while (corrente != nullptr) {
pilhaNos.push(corrente);
corrente = corrente->esq;
}
// Processa o nó e vai para a direita
corrente = pilhaNos.top();
pilhaNos.pop();
std::cout << corrente->valor << " ";
corrente = corrente->dir;
}
}
int main() {
NoArvore* raiz = new NoArvore('M');
raiz->esq = new NoArvore('B');
raiz->esq->esq = new NoArvore('A');
raiz->esq->dir = new NoArvore('F');
raiz->dir = new NoArvore('Z');
percorrerEmOrdem(raiz); // Saída: A B F M Z
std::cout << std::endl;
return 0;
}
Avaliação de Expressões Aritméticas
Converter expressões na notação infixa (como (4+5)*(7-2)) para a notação pós-fixa (como 4 5 + 7 2 - *) e em seguida avaliar o resultado.
Conversão Infixa para Pós-fixa
#include <iostream>
#include <string>
#include <stack>
#include <queue>
int precedencia(char operador) {
switch (operador) {
case '+': case '-': return 1;
case '*': case '/': return 2;
default: return 0;
}
}
bool ehOperador(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
std::queue<char> converterParaPosfixa(const std::string& expressao) {
std::stack<char> operadores;
std::queue<char> saida;
for (char caractere : expressao) {
if (std::isdigit(caractere)) {
saida.push(caractere);
}
else if (caractere == '(') {
operadores.push(caractere);
}
else if (caractere == ')') {
while (!operadores.empty() && operadores.top() != '(') {
saida.push(operadores.top());
operadores.pop();
}
if (!operadores.empty()) operadores.pop(); // remove '('
}
else if (ehOperador(caractere)) {
while (!operadores.empty() && operadores.top() != '(' &&
precedencia(operadores.top()) >= precedencia(caractere)) {
saida.push(operadores.top());
operadores.pop();
}
operadores.push(caractere);
}
}
while (!operadores.empty()) {
saida.push(operadores.top());
operadores.pop();
}
return saida;
}
double avaliarPosfixa(const std::string& expressao) {
std::queue<char> posfixa = converterParaPosfixa(expressao);
std::stack<double> operandos;
while (!posfixa.empty()) {
char c = posfixa.front();
posfixa.pop();
if (ehOperador(c)) {
double opDir = operandos.top(); operandos.pop();
double opEsq = operandos.top(); operandos.pop();
switch (c) {
case '+': operandos.push(opEsq + opDir); break;
case '-': operandos.push(opEsq - opDir); break;
case '*': operandos.push(opEsq * opDir); break;
case '/': operandos.push(opEsq / opDir); break;
}
} else {
operandos.push(c - '0');
}
}
return operandos.top();
}
int main() {
std::cout << avaliarPosfixa("(4+5)*(7-2)") << std::endl; // 45
std::cout << avaliarPosfixa("4*5/7") << std::endl; // ~2.857
return 0;
}
Extensão: Suporte a Múltiplos Dígitos e Exponenciação
O programa a seguir processa expressões com números de vários dígitos, ponto decimal e o operador de potência (^):
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <cmath>
#include <map>
enum class TipoToken { Operando, Operador };
struct Token {
std::string texto;
TipoToken tipo;
static const std::map<std::string, int> prioridades;
Token(const std::string& t) : texto(t) {
static const std::string ops = "+-*/^()";
tipo = (ops.find(t) != std::string::npos) ? TipoToken::Operador : TipoToken::Operando;
}
};
const std::map<std::string, int> Token::prioridades = {
{"(", 1}, {"+", 2}, {"-", 2}, {"*", 3}, {"/", 3}, {"^", 4}
};
bool operator>(const Token& a, const Token& b) {
if (a.tipo == TipoToken::Operador && b.tipo == TipoToken::Operador) {
return Token::prioridades.at(a.texto) >= Token::prioridades.at(b.texto);
}
return false;
}
bool ehAbertura(const Token& t) { return t.texto == "("; }
bool ehFechamento(const Token& t) { return t.texto == ")"; }
std::vector<Token> tokenizar(const std::string& expr) {
std::string buffer;
for (char c : expr) {
if (std::string("+-*/^()").find(c) != std::string::npos) {
if (!buffer.empty()) { buffer += ' '; }
buffer += c;
buffer += ' ';
} else {
buffer += c;
}
}
std::vector<Token> tokens;
std::istringstream iss(buffer);
std::string palavra;
while (iss >> palavra)
tokens.emplace_back(palavra);
return tokens;
}
std::vector<Token> infixaParaPosfixa(const std::vector<Token>& entrada) {
std::stack<Token> operadores;
std::vector<Token> saida;
for (const auto& tok : entrada) {
if (tok.tipo == TipoToken::Operando) {
saida.push_back(tok);
} else if (ehAbertura(tok)) {
operadores.push(tok);
} else if (ehFechamento(tok)) {
while (!operadores.empty() && !ehAbertura(operadores.top())) {
saida.push_back(operadores.top());
operadores.pop();
}
operadores.pop();
} else {
while (!operadores.empty() && !ehAbertura(operadores.top()) &&
operadores.top() > tok) {
saida.push_back(operadores.top());
operadores.pop();
}
operadores.push(tok);
}
}
while (!operadores.empty()) {
saida.push_back(operadores.top());
operadores.pop();
}
return saida;
}
double computarPosfixa(const std::vector<Token>& tokens) {
std::stack<double> pilha;
for (const auto& tok : tokens) {
if (tok.tipo == TipoToken::Operador) {
double dir = pilha.top(); pilha.pop();
double esq = pilha.top(); pilha.pop();
if (tok.texto == "+") pilha.push(esq + dir);
else if (tok.texto == "-") pilha.push(esq - dir);
else if (tok.texto == "*") pilha.push(esq * dir);
else if (tok.texto == "/") pilha.push(esq / dir);
else if (tok.texto == "^") pilha.push(std::pow(esq, dir));
} else {
pilha.push(tok.texto.find('.') != std::string::npos ?
std::stod(tok.texto) : std::stol(tok.texto));
}
}
return pilha.top();
}
int main() {
std::string expr = "(3+2)^2*(12+3)";
auto tokens = tokenizar(expr);
auto posfixa = infixaParaPosfixa(tokens);
std::cout << computarPosfixa(posfixa) << std::endl; // 375
return 0;
}
Extensões e Variações
Fila Circular
Implementação que reutiliza posições de memória em um vetor, usando aritmética modular para avançar os ponteiros de cabeça e cauda.
Fila com Máximo em O(1)
Similar à pilha com máximo, mas adaptada para o comportamento FIFO, mantendo uma fila auxiliar de máximos.
#include <iostream>
#include <deque>
template<typename Tipo>
class FilaComMaximo {
public:
void enfileirar(const Tipo& valor) {
dados.push_back(valor);
while (!auxMax.empty() && auxMax.back() < valor)
auxMax.pop_back();
auxMax.push_back(valor);
}
void desenfileirar() {
if (dados.front() == auxMax.front())
auxMax.pop_front();
dados.pop_front();
}
Tipo getMaximo() const {
return auxMax.front();
}
Tipo frente() const {
return dados.front();
}
bool estaVazia() const {
return dados.empty();
}
private:
std::deque<Tipo> dados;
std::deque<Tipo> auxMax;
};
int main() {
FilaComMaximo<int> fila;
int vals[] = {3, 1, 5, 2, 4};
for (int v : vals) fila.enfileirar(v);
std::cout << "Frente: " << fila.frente() << std::endl; // 3
std::cout << "Maximo: " << fila.getMaximo() << std::endl; // 5
fila.desenfileirar(); // remove 3
fila.desenfileirar(); // remove 1
std::cout << "Maximo: " << fila.getMaximo() << std::endl; // 5
return 0;
}
Fila de Prioridade
A fila de prioridade é, em essência, um heap. Existem diversas implementações possíveis: lista simples, árvore binária de busca, heap binário completo (a mais comum, geralmente implementada sobre vetor).
Fila Bloqueante (Multi-thread)
Em sistemas concorrentes, uma fila bloqueante suspende a thread consumidora quando a fila está vazia e a thread produtora quando a fila está cheia. Threads são despertadas assim que as condições necessárias são atendidas (espaço disponível ou elemento disponível).
Exercício: Avaliação de Expressão com Parênteses
Avaliar a expressão (3+4)*14 usando o algoritmo de conversão e avaliação pós-fixa descrito anteriormente.
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <cmath>
#include <map>
enum Categoria { Operacao, Numero };
struct Simbolo {
std::string lexema;
Categoria cat;
static const std::map<std::string, int> precedencia;
Simbolo(const std::string& l) : lexema(l) {
static const std::string sinais = "+-*/()^";
cat = (sinais.find(l) != std::string::npos) ? Operacao : Numero;
}
};
const std::map<std::string, int> Simbolo::precedencia = {
{"(", 0}, {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"^", 3}
};
bool operator>=(const Simbolo& a, const Simbolo& b) {
if (a.cat == Operacao && b.cat == Operacao)
return Simbolo::precedencia.at(a.lexema) >= Simbolo::precedencia.at(b.lexema);
return false;
}
std::vector<Simbolo> separarSimbolos(const std::string& expr) {
std::string reformulado;
for (char ch : expr) {
if (std::string("+-*/()^").find(ch) != std::string::npos) {
reformulado += ' ';
reformulado += ch;
reformulado += ' ';
} else {
reformulado += ch;
}
}
std::vector<Simbolo> lista;
std::istringstream iss(reformulado);
std::string pedaco;
while (iss >> pedaco)
lista.emplace_back(pedaco);
return lista;
}
std::vector<Simbolo> transformarEmPosfixa(const std::vector<Simbolo>& infixa) {
std::stack<Simbolo> pilhaOp;
std::vector<Simbolo> resultado;
for (const auto& simb : infixa) {
if (simb.cat == Numero) {
resultado.push_back(simb);
} else if (simb.lexema == "(") {
pilhaOp.push(simb);
} else if (simb.lexema == ")") {
while (pilhaOp.top().lexema != "(") {
resultado.push_back(pilhaOp.top());
pilhaOp.pop();
}
pilhaOp.pop();
} else {
while (!pilhaOp.empty() && pilhaOp.top().lexema != "(" &&
pilhaOp.top() >= simb) {
resultado.push_back(pilhaOp.top());
pilhaOp.pop();
}
pilhaOp.push(simb);
}
}
while (!pilhaOp.empty()) {
resultado.push_back(pilhaOp.top());
pilhaOp.pop();
}
return resultado;
}
double resolverPosfixa(const std::vector<Simbolo>& posfixa) {
std::stack<double> acumulador;
for (const auto& simb : posfixa) {
if (simb.cat == Operacao) {
double op2 = acumulador.top(); acumulador.pop();
double op1 = acumulador.top(); acumulador.pop();
if (simb.lexema == "+") acumulador.push(op1 + op2);
else if (simb.lexema == "-") acumulador.push(op1 - op2);
else if (simb.lexema == "*") acumulador.push(op1 * op2);
else if (simb.lexema == "/") acumulador.push(op1 / op2);
else if (simb.lexema == "^") acumulador.push(std::pow(op1, op2));
} else {
acumulador.push(std::stod(simb.lexema));
}
}
return acumulador.top();
}
int main() {
std::string entrada = "(3+4)*14";
auto simbolos = separarSimbolos(entrada);
auto posfixa = transformarEmPosfixa(simbolos);
std::cout << resolverPosfixa(posfixa) << std::endl; // 98
return 0;
}