Uso Básico

Os containers stack, queue e priority_queue na STL de C++ são adaptadores que fornecem interfaces específicas para estruturas de dados. Eles são fáceis de usar após familiarização com os métodos principais como push, pop, top, front, back, entre outros.

Exercícios Práticos

1. MinStack - LeetCode 155

A abordagem utiliza duas pilhas: uma para armazenar dados normais e outra para rastrear o mínimo atual. Ao inserir um elemento, se ele for menor ou igual ao topo da pilha de mínimos, ele também é adicionado lá. Isso garante eficiência na recuperação do mínimo.

class MinStack {
public:
    MinStack() {}

    void push(int valor) {
        principal.push(valor);
        if (minima.empty() || valor <= minima.top()) {
            minima.push(valor);
        }
    }

    void pop() {
        if (principal.top() == minima.top()) {
            minima.pop();
        }
        principal.pop();
    }

    int top() {
        return principal.top();
    }

    int getMin() {
        return minima.top();
    }

private:
    stack<int> principal;
    stack<int> minima;
};
</int></int>

2. Sequência de Push e Pop em Pilha

O problema verifica se uma sequência de pop é válida dada uma sequência de push. A solução simula o processo usando uma pilha auxiliar, empilhando elementos da sequência de push e desempilhando quando houver correspondência com a sequência de pop.

#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    bool isValidPopOrder(vector<int>& pushSeq, vector<int>& popSeq) {
        stack<int> aux;
        int idx = 0;
        for (int elem : pushSeq) {
            aux.push(elem);
            while (!aux.empty() && aux.top() == popSeq[idx]) {
                aux.pop();
                idx++;
            }
        }
        return aux.empty();
    }
};

3. Travessia por Nível em Árvore Binária - LeetCode 102

Para percorrer uma árvore binária nível por nível, utiliza-se uma fila. A variável levelSize controla quantos nós há no nível atual, atualizada após processar todos os nós do nível.

struct TreeNode {
    int val;
    TreeNode* esquerda;
    TreeNode* direita;
    TreeNode(int x) : val(x), esquerda(nullptr), direita(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* raiz) {
        vector<vector<int>> resultado;
        queue<TreeNode*> fila;
        if (raiz) {
            fila.push(raiz);
        }
        while (!fila.empty()) {
            int tamNivel = fila.size();
            vector<int> nivel;
            for (int i = 0; i < tamNivel; i++) {
                TreeNode* no = fila.front();
                fila.pop();
                nivel.push_back(no->val);
                if (no->esquerda) fila.push(no->esquerda);
                if (no->direita) fila.push(no->direita);
            }
            resultado.push_back(nivel);
        }
        return resultado;
    }
};

Implementação Subjacente

Adaptadores de Container

Adaptadores de container na STL permitem reutilizar containers subjacentes como vector ou list para construir estruturas como stack e queue. Por exemplo, stack pode ser implementada sobre vector, e queue sobre list, abstraindo operações específicas.

Implementação de stack e queue

A implementação usa templates para generalizar o container subjacente. O código abaixo ilustra uma stack simples usando vector como container padrão.

template<typename T, typename Container = vector<T>>
class Stack {
public:
    void push(const T& valor) { dados.push_back(valor); }
    void pop() { dados.pop_back(); }
    T& top() { return dados.back(); }
    bool empty() const { return dados.empty(); }
    size_t size() const { return dados.size(); }
private:
    Container dados;
};

Estrutura deque

O deque combina características de vector e list, oferecendo acesso eficiente por índice e inserção/remoção em ambas as extremidades. Internamente, utiliza um array de ponteiros para blocos de memória.

O deque, embora não substitua vector ou list, é eficiente para operações em ambas as extremidades, sendo útil para implementar stack e queue.

priority_queue (Estrutura de Heap)

A priority_queue é baseada em um heap, permitindo acesso ao elemento de maior prioridade. Por padrão, é um max-heap, mas pode ser configurada como min-heap usando functors.

template<typename T, typename Container = vector<T>, typename Comparador = less<T>>
class PriorityQueue {
public:
    void inserir(const T& valor) {
        dados.push_back(valor);
        siftUp(dados.size() - 1);
    }

    void remover() {
        swap(dados[0], dados.back());
        dados.pop_back();
        siftDown(0);
    }

    const T& topo() const { return dados[0]; }
    bool vazio() const { return dados.empty(); }

private:
    void siftUp(int filho) {
        int pai = (filho - 1) / 2;
        while (filho > 0 && comparador(dados[filho], dados[pai])) {
            swap(dados[filho], dados[pai]);
            filho = pai;
            pai = (filho - 1) / 2;
        }
    }

    void siftDown(int pai) {
        int filho = pai * 2 + 1;
        while (filho < dados.size()) {
            if (filho + 1 < dados.size() && comparador(dados[filho + 1], dados[filho])) {
                filho++;
            }
            if (comparador(dados[pai], dados[filho])) break;
            swap(dados[pai], dados[filho]);
            pai = filho;
            filho = pai * 2 + 1;
        }
    }

    Container dados;
    Comparador comparador;
};

Functors

Functors são objetos que sobrecarregam o operador (), permitindo comportamento semelhante a funções. Em priority_queue, functors definem a ordem de prioridade, como less para max-heap e greater para min-heap.

Algoritmos de Heap na STL

A biblioteca <algorithm> oferece funções para manipulação de heaps: is_heap verifica se um intervalo é um heap, make_heap constrói um heap, e sort_heap ordena um heap.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> dados = {3, 1, 4, 1, 5};
    make_heap(dados.begin(), dados.end());
    // Agora dados é um max-heap
    sort_heap(dados.begin(), dados.end());
    // Dados ordenados em ordem crescente
}