Stack (pila)
Última actualización
Una pila es una colección con exactamente un extremo abierto. Añades un valor apilándolo en la cima, y quitas uno desapilando esa misma cima, así que el último valor que entra es siempre el primero en salir. Eso es lo que significa LIFO, y es toda la regla: no hay forma de llegar al medio sin quitar antes lo que está encima. Pulsa reproducir arriba y observa cómo la columna crece con cada push y se reduce por ese mismo extremo con cada pop.
La restricción es justo el punto. Como las dos operaciones tocan solo la cima, cada una es O(1) por muy alta que se ponga la pila, y esa previsibilidad es la razón de que las pilas estén debajo de gran parte de la informática: la pila de llamadas que ejecuta la recursión, el historial de deshacer de un editor, el emparejamiento de paréntesis en un analizador sintáctico, y la pila explícita que convierte una búsqueda en profundidad recursiva en un bucle. Cambia el extremo por el que quitas y lo que obtienes es una Queue (cola).
Complejidad temporal y espacial
Para la pila estándar respaldada por un arreglo o por una lista enlazada:
| Operación | Complejidad | Notas |
|---|---|---|
| Push | O(1) | O(1) amortizado en un arreglo dinámico, que de vez en cuando se redimensiona. |
| Pop | O(1) | Siempre el elemento de la cima, así que no hace falta desplazar nada. |
| Peek (cima) | O(1) | Lee la cima sin quitarla. |
| Buscar | O(n) | No es para lo que sirve una pila: tienes que ir desapilando hacia abajo. |
| Espacio | O(n) | Un hueco por cada valor almacenado. |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | La pila empieza vacía, con la cima sin apuntar a nada. |
| 2 | Push escribe el valor en la posición de la cima y sube la cima una posición. |
| 3 | Cada push posterior cae justo encima del valor anterior. |
| 4 | Pop lee el valor de la cima y luego baja la cima una posición. |
| 5 | El valor que devuelve es siempre el que se apiló más recientemente. |
| 6 | Desapilar una pila vacía es un error, llamado subdesbordamiento de pila, así que el código real comprueba antes is_empty(). |
Ejemplo resuelto
Apilando 3, 7, 5 y luego vaciando la pila:
| Operación | Pila (de abajo arriba) | Devuelve |
|---|---|---|
push(3) | [3] | nada |
push(7) | [3, 7] | nada |
push(5) | [3, 7, 5] | nada |
pop() | [3, 7] | 5, el valor más nuevo |
pop() | [3] | 7 |
pop() | [] | 3, el valor más antiguo, el último |
Cuándo usar una pila
| Úsala cuando | Evítala cuando |
|---|---|
| Necesitas recuperar primero el elemento más reciente: deshacer, botones de atrás, emparejamiento de paréntesis | Necesitas primero el elemento más antiguo, que es una Queue (cola) |
| Estás convirtiendo un algoritmo recursivo en uno iterativo | Necesitas buscar o indexar en medio de los datos |
| Estás analizando estructuras anidadas como expresiones, JSON o HTML | Muchos lectores necesitan acceso arbitrario, donde encaja mejor un arreglo o un mapa |
Quieres inserción y eliminación O(1) garantizadas sin reequilibrados | Necesitas mantener los datos ordenados, que es lo que te da un heap o un árbol |
Código de Stack
Una implementación limpia y ejecutable de Stack en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Stack en Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Código de Stack en JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Código de Stack en Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Código de Stack en C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Código de Stack en C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Preguntas frecuentes sobre las pilas
¿Qué significa LIFO?
Último en entrar, primero en salir: el valor apilado más recientemente es el primero en desapilarse. Una pila de platos es la imagen habitual: coges el plato que acabas de dejar, no el del fondo. Una Queue (cola) sigue la disciplina contraria, FIFO.
¿Cuál es la diferencia entre una pila y una cola?
Solo el extremo por el que quitas. Las dos añaden por un extremo en
O(1); una pila quita por ese mismo extremo (LIFO) y una cola quita por el otro (FIFO). Todo lo demás, incluida la tabla de complejidad de arriba, es idéntico.¿Cuáles son las operaciones principales de una pila?
push añade un valor en la cima, pop quita y devuelve el valor de la cima, peek (a veces top) lee la cima sin quitarla, y is_empty indica si queda algo. Las cuatro son O(1).¿Qué es un desbordamiento de pila (stack overflow)?
Apilar en una pila que ya no tiene espacio. El caso famoso es la pila de llamadas: cada llamada a una función apila un marco, así que una recursión que nunca llega a su caso base sigue apilando hasta alcanzar el límite de pila del entorno de ejecución y el programa se cae. El error espejo, desapilar una pila vacía, es un subdesbordamiento de pila.
¿Cómo se implementa una pila?
Dos formas comunes. Un arreglo dinámico apila y desapila por el final, lo cual es
O(1) amortizado y amigable con la caché: así funcionan list de Python y ArrayDeque de Java. Una lista enlazada apila y desapila por la cabeza, O(1) en el peor caso y sin redimensionar, pero cuesta un puntero por elemento. std::stack de C++ es un adaptador que usa std::deque por defecto, un arreglo segmentado, y acepta otro contenedor si se lo pasas.¿Dónde se usan las pilas en programas reales?
La pila de llamadas para las llamadas a funciones y la recursión, el historial de deshacer y rehacer, la navegación hacia atrás del navegador, la evaluación de expresiones y el emparejamiento de paréntesis en los analizadores sintácticos, y la pila explícita que convierte una búsqueda en profundidad recursiva en un bucle iterativo.
Recursos relacionados
Más visualizaciones
