std::stackDocente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
std::stack)?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).
¡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()
20, primero es obligatorio hacer pop() del 30.
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()
}
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
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.
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).
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.
"Indicar si un texto de entrada compuesto por paréntesis está correctamente balanceado."
#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;
}
() [] {}
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
}
std::stack
Ya manejás pilas LIFO con std::stack. En el último módulo veremos colas FIFO (queue), colas de prioridad y colas dobles (deque).