Configuraciones predeterminadas en SGI STL

En la implementación estándar de SGI STL, si no se especifica otra estructura subyacente, se utiliza deque como base por defecto para las pilas y colas. Esto se aplica tanto a stack como a queue.

Simulación de una cola FIFO con dos pilas

Para emular una cola con operaciones de inserción (push) y extracción (pop) en orden FIFO, se pueden emplear dos pilas: una para entrada y otra para salida. Al insertar un elemento, se apila en la pila de entrada. Al extraer, si la pila de salida está vacía, se transfieren todos los elementos de la pila de entrada a la de salida (manteniendo el orden) antes de desapilar. La cola se considera vacía cuando ambas pilas están vacías.

template<typename T>
class ColaConPilas {
private:
    stack<T> pila_entrada;
    stack<T> pila_salida;
public:
    void enqueue(T valor) {
        pila_entrada.push(valor);
    }
    T dequeue() {
        if (pila_salida.empty()) {
            while (!pila_entrada.empty()) {
                pila_salida.push(pila_entrada.top());
                pila_entrada.pop();
            }
        }
        if (pila_salida.empty()) throw runtime_error("Cola vacía");
        T valor = pila_salida.top();
        pila_salida.pop();
        return valor;
    }
    bool esta_vacia() const {
        return pila_entrada.empty() && pila_salida.empty();
    }
};

Vaildación de secuencias de paréntesis

Para verificar si una cadena de paréntesis, llaves y corchetes está correctamente balanceada, se utiliza una pila. Se recorre la cadena: si se encuentra un delimitador de apertura, se apila su correspondiente cierre; si se encuentra uno de cierre, se compara con el tope de la pila. Si la pila está vacía o los delimitadores no coinciden, la secuencia es inválida. Al finalizar, la pila debe estar vacía para que sea válida.

bool es_secuencia_valida(const string& s) {
    stack<char> pila;
    for (char c : s) {
        if (c == '(') pila.push(')');
        else if (c == '{') pila.push('}');
        else if (c == '[') pila.push(']');
        else if (pila.empty() || pila.top() != c) return false;
        else pila.pop();
    }
    return pila.empty();
}

Eliminación de duplicados adyacentes

Para suprimri caracteres repetidos consecutivos en una cadena, se puede usar una pila. Se itera sobre la cadena: si el carácter actual es diferente al tope de la pila (o la pila está vacía), se apila; si es igual, se desapila. Luego, se reconstruye la cadena en orden inverso a partir de la pila. Alternativamente, se puede emplear un string como pila, aprovechando sus métodos push_back y pop_back.

string eliminar_duplicados(const string& s) {
    stack<char> pila;
    for (char c : s) {
        if (pila.empty() || c != pila.top()) {
            pila.push(c);
        } else {
            pila.pop();
        }
    }
    string resultado;
    while (!pila.empty()) {
        resultado += pila.top();
        pila.pop();
    }
    reverse(resultado.begin(), resultado.end());
    return resultado;
}

// Implementación alternativa usando string como pila
string eliminar_duplicados_v2(const string& s) {
    string pila;
    for (char c : s) {
        if (pila.empty() || pila.back() != c) {
            pila.push_back(c);
        } else {
            pila.pop_back();
        }
    }
    return pila;
}

Evaluación de notación polaca inversa

En la notación polaca inversa (RPN), los operadores siguen a sus operandos. Para evaluar una expresión en RPN, se utiliza una pila. Se procesan los tokens: si es un número, se apila; si es un operador, se desapilan dos operandos, se aplica el operador y se apila el resultado. Se debe tener en cuenta el orden de los operandos al realizar la operación.

int evaluar_rpn(const vector<string>& tokens) {
    stack<int> pila;
    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = pila.top(); pila.pop();
            int a = pila.top(); pila.pop();
            if (token == "+") pila.push(a + b);
            else if (token == "-") pila.push(a - b);
            else if (token == "*") pila.push(a * b);
            else pila.push(a / b);
        } else {
            pila.push(stoi(token));
        }
    }
    return pila.top();
}

Cola monótona para máximo en ventana deslizante

Una cola monótona es una estructura que mantiene sus elementos en orden ascendente o descendente. Se usa para encontrar el máximo (o mínimo) en una ventana deslizante de tamaño fijo. La cola se implementa con un deque: al insertar un nuevo elemento, se eliminan todos los elementos menores desde el final para mantener el orden descendenet. Al remover un elemento de la ventana, se compara con el frente de la cola y, si coincide, se extrae. Así, el frente de la cola siempre es el máximo actual de la ventana.

class ColaMonotonaDecreciente {
private:
    deque<int> dq;
public:
    void insertar(int valor) {
        while (!dq.empty() && valor > dq.back()) {
            dq.pop_back();
        }
        dq.push_back(valor);
    }
    void eliminar(int valor) {
        if (!dq.empty() && valor == dq.front()) {
            dq.pop_front();
        }
    }
    int obtener_maximo() const {
        return dq.front();
    }
};

vector<int> maximo_ventana_deslizante(const vector<int>& nums, int k) {
    ColaMonotonaDecreciente cola;
    vector<int> resultado;
    for (int i = 0; i < k; ++i) {
        cola.insertar(nums[i]);
    }
    resultado.push_back(cola.obtener_maximo());
    for (int i = k; i < nums.size(); ++i) {
        cola.eliminar(nums[i - k]);
        cola.insertar(nums[i]);
        resultado.push_back(cola.obtener_maximo());
    }
    return resultado;
}

Elementos más frecuentes usando un heap mínimo

Para obtener los k elementos más frecuentes en una lista, se puede combinar un mapa de frecuencias con una cola de prioridad (heap mínimo) de tamaño k. Primero, se cuentan las frecuencias con un unordered_map. Luego, se itera sobre el mapa, insertando pares (elemento, frecuencia) en el heap. Si el heap excede el tamaño k, se extrae el elemento con menor frecuencia. Finalmente, los elementos restantes en el heap son los más frecuentes, pero se deben extraer en orden inverso para obtener el resultado correcto.

vector<int> elementos_mas_frecuentes(const vector<int>& nums, int k) {
    unordered_map<int, int> frecuencia;
    for (int num : nums) {
        frecuencia[num]++;
    }
    // Comparador para heap mínimo basado en frecuencia
    auto comparador = [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comparador)> heap_minimo(comparador);
    for (const auto& par : frecuencia) {
        heap_minimo.push(par);
        if (heap_minimo.size() > k) {
            heap_minimo.pop();
        }
    }
    vector<int> resultado(k);
    for (int i = k - 1; i >= 0; --i) {
        resultado[i] = heap_minimo.top().first;
        heap_minimo.pop();
    }
    return resultado;
}