Tema 3
Listas, pilas y colas
Patrón de examen
Pila para problemas con 'deshacer' o DFS. Cola para BFS. Priority queue para Dijkstra o seleccionar el mínimo/máximo repetidamente.
Explicación
Pila (Stack) — LIFO
Último en entrar, primero en salir.
stack<int> s;
s.push(x); // agregar arriba
s.pop(); // eliminar arriba
s.top(); // ver el tope
s.empty(); // ¿está vacía?
Usos: DFS iterativo, evaluar expresiones, paréntesis balanceados, historial de deshacer.
Cola (Queue) — FIFO
Primero en entrar, primero en salir.
queue<int> q;
q.push(x); // agregar al final
q.pop(); // eliminar al frente
q.front(); // ver el frente
q.empty(); // ¿está vacía?
Usos: BFS, procesamiento en orden de llegada.
Deque (doble cola)
Permite insertar/eliminar por ambos extremos en O(1).
deque<int> dq;
dq.push_front(x); dq.push_back(x);
dq.pop_front(); dq.pop_back();
Priority Queue (cola de prioridad / heap)
El elemento de mayor prioridad siempre está al frente.
priority_queue<int> pq; // max-heap
priority_queue<int, vector<int>, greater<int>> pq; // min-heap
pq.push(x); pq.top(); pq.pop();