Pilas (Stack) - Concepto y Uso

¿Qué es una pila?

Una pila (stack) es una estructura de datos lineal que sigue el principio LIFO (Last In, First Out): el último elemento en entrar es el primero en salir.

Analogía

Piensa en una pila de platos:

• Solo puedes agregar platos arriba
• Solo puedes quitar el plato de arriba
• No puedes acceder a platos del medio

    ┌───────┐
    │   4   │  ← top (último en entrar, primero en salir)
    ├───────┤
    │   3   │
    ├───────┤
    │   2   │
    ├───────┤
    │   1   │  ← fondo (primero en entrar, último en salir)
    └───────┘

Operaciones básicas

std::stack en C++

#include <stack>
using namespace std;

int main() {
    stack<int> pila;

    // Insertar elementos
    pila.push(10);
    pila.push(20);
    pila.push(30);

    // Ver el tope
    cout << pila.top() << endl;  // 30

    // Eliminar el tope
    pila.pop();
    cout << pila.top() << endl;  // 20

    // Tamaño
    cout << pila.size() << endl;  // 2

    // Verificar si está vacía
    cout << pila.empty() << endl;  // 0 (false)

    return 0;
}

Recorrer una pila

Como la pila solo permite acceso al tope, hay que ir sacando elementos:

stack<int> pila;
pila.push(1);
pila.push(2);
pila.push(3);

while (!pila.empty()) {
    cout << pila.top() << " ";  // 3 2 1
    pila.pop();
}

Nota: Esto destruye la pila. Si necesitas conservarla, haz una copia primero.

Implementación manual con arreglo

class MiPila {
private:
    int arr[10000];
    int tope = -1;

public:
    void push(int x) {
        arr[++tope] = x;
    }

    void pop() {
        if (!empty()) tope--;
    }

    int top() {
        return arr[tope];
    }

    bool empty() {
        return tope == -1;
    }

    int size() {
        return tope + 1;
    }
};

Aplicación: Paréntesis balanceados

Verificar si los paréntesis están correctamente balanceados:

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

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

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

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

    return pila.empty();
}

// Ejemplos:
// "(())" -> true
// "([{}])" -> true
// "([)]" -> false
// "(((" -> false

Aplicación: Invertir una cadena

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;
}

Aplicación: Historial (undo/redo)

stack<string> historial;
stack<string> redos;

void escribir(string texto) {
    historial.push(texto);
    // Limpiar redos al hacer nueva acción
    while (!redos.empty()) redos.pop();
}

string undo() {
    if (historial.empty()) return "";
    string ultimo = historial.top();
    historial.pop();
    redos.push(ultimo);
    return historial.empty() ? "" : historial.top();
}

string redo() {
    if (redos.empty()) return historial.top();
    string texto = redos.top();
    redos.pop();
    historial.push(texto);
    return texto;
}

Aplicación: Evaluación de expresiones postfijas

En notación postfija (polaca inversa), los operadores van después de los operandos: 3 4 + 5 * = (3+4)*5 = 35

int evaluarPostfija(string expresion) {
    stack<int> pila;
    stringstream ss(expresion);
    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);
            else if (token == "-") pila.push(a - b);
            else if (token == "*") pila.push(a * b);
            else if (token == "/") pila.push(a / b);
        } else {
            pila.push(stoi(token));
        }
    }

    return pila.top();
}

// "3 4 + 5 *" -> 35
// "2 3 4 * +" -> 14

Problema clásico: Stock Span

Para cada día, encontrar cuántos días consecutivos anteriores tienen precio menor o igual:

vector<int> stockSpan(vector<int>& precios) {
    int n = precios.size();
    vector<int> span(n);
    stack<int> pila;  // Índices

    for (int i = 0; i < n; i++) {
        // Sacar elementos menores
        while (!pila.empty() && precios[pila.top()] <= precios[i]) {
            pila.pop();
        }

        if (pila.empty()) {
            span[i] = i + 1;
        } else {
            span[i] = i - pila.top();
        }

        pila.push(i);
    }

    return span;
}

Ejercicios de práctica

Ejercicio 1

Implementa una función que convierta una expresión infija a postfija.

int prioridad(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infijaAPostfija(string infija) {
    string postfija = "";
    stack<char> pila;

    for (char c : infija) {
        if (isalnum(c)) {
            postfija += c;
        } else if (c == '(') {
            pila.push(c);
        } else if (c == ')') {
            while (!pila.empty() && pila.top() != '(') {
                postfija += pila.top();
                pila.pop();
            }
            pila.pop();  // Quitar '('
        } else {  // Operador
            while (!pila.empty() && prioridad(pila.top()) >= prioridad(c)) {
                postfija += pila.top();
                pila.pop();
            }
            pila.push(c);
        }
    }

    while (!pila.empty()) {
        postfija += pila.top();
        pila.pop();
    }

    return postfija;
}

Ejercicio 2

Dado un arreglo, para cada elemento encuentra el siguiente elemento mayor.

vector<int> siguienteMayor(vector<int>& arr) {
    int n = arr.size();
    vector<int> resultado(n, -1);
    stack<int> pila;  // Índices

    for (int i = 0; i < n; i++) {
        while (!pila.empty() && arr[pila.top()] < arr[i]) {
            resultado[pila.top()] = arr[i];
            pila.pop();
        }
        pila.push(i);
    }

    return resultado;
}
// [4, 5, 2, 10, 8] -> [5, 10, 10, -1, -1]

Siguiente paso

Aprende sobre Colas y cuándo usar cada estructura.