Pilas (Stacks)

¿Qué es una pila?

Imagina una pila de platos. Solo puedes:

• Poner un plato encima de la pila.
• Quitar el plato que está encima (el último que pusiste).

No puedes tomar un plato del medio sin quitar los de arriba primero. Esto se llama LIFO: Last In, First Out (el último en entrar es el primero en salir).

Pila:
┌─────┐
│  C  │  ← Tope (top): último en entrar, primero en salir
├─────┤
│  B  │
├─────┤
│  A  │  ← Fondo: primero en entrar, último en salir
└─────┘

Pila en C++ con stack

#include <stack>

stack<int> pila;

pila.push(10);    // Poner 10 encima
pila.push(20);    // Poner 20 encima
pila.push(30);    // Poner 30 encima

cout << pila.top() << endl;  // 30 (ver el de arriba)
pila.pop();                   // Quitar 30

cout << pila.top() << endl;  // 20
cout << pila.size() << endl; // 2
cout << pila.empty() << endl; // 0 (false)

Aplicaciones de pilas

1. Verificar paréntesis balanceados

Dado un string con (, ), [, ], {, }, verificar si están bien cerrados.

bool esBalanceado(string s) {
    stack<char> pila;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            pila.push(c);
        } else {
            if (pila.empty()) return false;

            char top = pila.top();
            pila.pop();

            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }

    return pila.empty();
}

2. Invertir un string/arreglo

string invertir(string s) {
    stack<char> pila;
    for (char c : s) pila.push(c);

    string resultado = "";
    while (!pila.empty()) {
        resultado += pila.top();
        pila.pop();
    }
    return resultado;
}

3. Historial (Deshacer/Rehacer)

Las pilas son perfectas para funcionalidades de "undo": cada acción se apila, y deshacer es simplemente quitar la última acción.

4. Evaluación de expresiones postfijas

Expresión postfija (notación polaca inversa): 3 4 + 2 * = (3 + 4) * 2 = 14

int evaluarPostfija(string expr) {
    stack<int> pila;
    stringstream ss(expr);
    string token;

    while (ss >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = pila.top(); pila.pop();
            int a = pila.top(); pila.pop();
            if (token == "+") pila.push(a + b);
            if (token == "-") pila.push(a - b);
            if (token == "*") pila.push(a * b);
            if (token == "/") pila.push(a / b);
        } else {
            pila.push(stoi(token));
        }
    }

    return pila.top();
}

5. La pila y la recursión

La recursión internamente usa una pila (la pila de llamadas del sistema). Por eso, cualquier algoritmo recursivo puede convertirse en iterativo usando una pila explícita.

Ejercicio de práctica

Dado un string con paréntesis, encuentra el par más profundo. Por ejemplo, en ((())) la profundidad máxima es 3. En (()()) es 2.

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;

    int profundidad = 0, maxProf = 0;
    for (char c : s) {
        if (c == '(') {
            profundidad++;
            maxProf = max(maxProf, profundidad);
        } else if (c == ')') {
            profundidad--;
        }
    }

    cout << maxProf << endl;

    return 0;
}

Siguiente paso

Aprende sobre Colas (Queues), la estructura de datos donde el primero en entrar es el primero en salir.