Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 4

Pilas: std::stack
Estructuras LIFO y Acceso por Tope

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

¿Qué es una Pila (std::stack)?

Estructura LIFO (Last In, First Out)

Los elementos se agregan en el tope y se remueven exactamente del mismo lugar. El último elemento en entrar es el primero en salir (como una pila de platos).

Restricción Estricta

¡SOLO ES POSIBLE ACCEDER AL ELEMENTO EN EL TOPE TANTO PARA AÑADIRLO COMO PARA ELIMINARLO!

No tiene operador [] ni iteradores para recorrer el medio de la pila sin desapilar.

push(x)  |  top()  |  pop()
30 ← tope (visible)
20 (oculto)
10 (base oculta)
Para ver el 20, primero es obligatorio hacer pop() del 30.

Operaciones de std::stack

Cabecera necesaria: #include <stack> — Todas las operaciones cuestan O(1).


// 1. DEFINICION
stack<int> pila;

// 2. INSERTAR UN ELEMENTO EN EL TOPE
pila.push(10);
pila.push(25); // Ahora 25 esta en el tope

// 3. CONSULTAR EL ELEMENTO DEL TOPE (sin sacarlo)
cout << pila.top() << endl; // Imprime 25

// 4. ELIMINAR EL ELEMENTO DEL TOPE
pila.pop(); // Saca el 25 (no devuelve el valor, solo lo remueve)

// 5. REVISAR SI LA PILA ESTA VACIA
if (pila.empty()) {
    // Esta vacia
} else {
    // No esta vacia: es seguro llamar a pila.top() o pila.pop()
}
                    

¿Cómo Procesamos Todos los Elementos?


stack<char> letras;
for (char c : string("UTN")) {
    letras.push(c);
}

// Patron tipico de procesamiento LIFO:
while (!letras.empty()) {
    cout << letras.top() << " ";
    letras.pop();
}
// Salida en orden inverso: N T U
                            

Inversión Natural

Como el último carácter en entrar es el primero en salir, vaciar una pila con while (!pila.empty()) recorre los elementos en sentido exactamente inverso al que ingresaron.

Cuidado con top() en vacío

Llamar a pila.top() o pila.pop() cuando pila.empty() es verdadero produce un error en tiempo de ejecución (Segmentation Fault).

Ejemplo de Aplicación: Fórmulas de Ayelén

Práctica Stack

Ayelén es una gran matemática reconocida en todo el mundo que trabaja constantemente con fórmulas muy extensas llenas de paréntesis, llaves y corchetes. Como no trabaja sola, le pidió a sus ayudantes que realicen manipulaciones sobre las fórmulas, pero algunos no trabajaron bien con los paréntesis y varias fórmulas terminaron mal formadas.

Ayelén eliminó todo lo que estaba adentro y te envió las secuencias para que indiques si están bien formadas: aquellas donde todos los símbolos que abren se cierran en el orden correspondiente y nunca cierran antes de abrir. Por ejemplo, "(([[{}]]))" está bien formada, pero ")(())(" no.

Simplificamos el problema antes de resolver:

"Indicar si un texto de entrada compuesto por paréntesis está correctamente balanceado."

Resolución Paso a Paso: Paréntesis Balanceados


#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<char> pila;
    string formula;
    int contadorParentesis = 0;

    cin >> formula;
    for (auto thisSymbol : formula)
        pila.push(thisSymbol);

    while (!pila.empty() and contadorParentesis >= 0) {
        if (pila.top() == ')') contadorParentesis++;
        else if (pila.top() == '(') contadorParentesis--;
        pila.pop();
    }

    bool respuesta = (contadorParentesis == 0);
    cout << boolalpha << respuesta << endl;
    return 0;
}
                        

Variante General: Múltiples Símbolos () [] {}

Cuando además de () tenemos [] y {}, apilamos los símbolos que abren y verificamos que cada cierre coincida con el tope actual:


bool bienFormada(const string &formula) {
    stack<char> abiertos;
    for (char c : formula) {
        if (c == '(' || c == '[' || c == '{') {
            abiertos.push(c);
        } else {
            if (abiertos.empty()) return false; // Cierra sin abrir
            char tope = abiertos.top();
            abiertos.pop();
            if (c == ')' && tope != '(') return false;
            if (c == ']' && tope != '[') return false;
            if (c == '}' && tope != '{') return false;
        }
    }
    return abiertos.empty(); // Debe quedar vacia al terminar
}
                        

Laboratorio en Vivo: Validador de Fórmulas con std::stack

OneCompiler - C++ Sandbox (Probá distintas fórmulas)

¡Fin del Módulo 4!

Ya manejás pilas LIFO con std::stack. En el último módulo veremos colas FIFO (queue), colas de prioridad y colas dobles (deque).

Módulo 3: std::set Volver al Hub Ir al Módulo 5: queue y deque