Estructuras de datos - Pila
Una pila (Stack) es una estructura de datos lineal que sigue el principio de último en entrar, primero en salir (Last In First Out, LIFO). Se puede imaginar como una pila de platos: solo se puede colocar encima y retirar desde arriba.
Concepto y principio de la pila
Verificación LIFO: apilar 10→20→30, desapilar 30→20→10 (último en entrar, primero en salir) | La pila solo se preocupa por la parte superior, no por el medio
Implementación con arreglo (pila secuencial)
Almacenamiento: arreglo de tamaño fijo + puntero top
push:items[++top] = value
pop:return items[top--]
Ventajas: acceso rápido, amigable con caché, implementación simple
Desventajas: capacidad fija, posible desbordamiento
Implementación con lista enlazada (pila encadenada)
Almacenamiento: nodos dinámicos + puntero al tope (cabeza de la lista)
push: inserción por cabeza newNode->next = top
pop: top = top->next; free(cabeza anterior)
Ventajas: sin límite de capacidad, expansión dinámica flexible
Desventajas: gasto adicional de punteros, no amigable con caché
Implementación de pila con arreglos
Ejemplo
#include <stdbool.h> /* tipo bool */
#define MAX_SIZE 100 /* capacidad máxima de la pila */
/* Estructura de la pila: contiene arreglo de datos y puntero al tope */
struct Stack {
int items[MAX_SIZE]; /* Arreglo que almacena los elementos de la pila */
int top; /* Puntero al tope, -1 indica pila vacía */
};
/* Inicializar la pila: establecer top en -1 */
void initStack(struct Stack* s) {
s->top = -1;
}
/* Verificar vacía: la pila está vacía cuando top es -1 */
bool isEmpty(struct Stack* s) {
return s->top == -1;
}
/* Verificar llena: la pila está llena cuando top alcanza el límite de capacidad menos 1 */
bool isFull(struct Stack* s) {
return s->top == MAX_SIZE - 1;
}
/* Apilar (push): colocar un elemento en el tope
Primero mover top, luego escribir los datos */
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("¡La pila está llena, no se puede apilar!\n");
return;
}
s->items[++s->top] = value; /* Primero incrementar top en 1, luego asignar */
printf("Apilando: %d\n", value);
}
/* Desapilar (pop): elimina y devuelve el elemento superior
Primero extraer los datos, luego mover top */
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("¡La pila está vacía, no se puede desapilar!\n");
return -1; /* Devuelve un valor especial para indicar error */
}
return s->items[s->top--]; /* Primero devolver el valor, luego decrementar top en 1 */
}
/* Ver el tope (peek): no desapila, solo observa */
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("¡La pila está vacía!\n");
return -1;
}
return s->items[s->top];
}
int main() {
struct Stack s;
initStack(&s);
push(&s, 10); /* Apilar: 10 */
push(&s, 20); /* Apilar: 20 */
push(&s, 30); /* Apilar: 30 */
printf("Elemento superior: %d\n", peek(&s)); /* Salida: Elemento superior: 30 */
printf("Desapilando: %d\n", pop(&s)); /* Salida: Desapilando: 30 (último en entrar, primero en salir) */
printf("Desapilando: %d\n", pop(&s)); /* Salida: Desapilando: 20 */
printf("Desapilando: %d\n", pop(&s)); /* Salida: Desapilando: 10 */
if (isEmpty(&s)) {
printf("La pila ya está vacía\n"); /* Salida: La pila ya está vacía */
}
return 0;
}
Implementación de pila con lista enlazada
Ejemplo
#include <stdlib.h>
#include <stdbool.h>
/* Nodo de la lista enlazada */
struct Node {
int data;
struct Node* next;
};
/* Apilar (push): usa la cabeza de la lista como tope, inserción por cabeza
Complejidad de tiempo: O(1) */
struct Node* push(struct Node* top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top; /* El nuevo nodo apunta al tope original */
printf("Apilando: %d\n", value);
return newNode; /* El nuevo nodo se convierte en el nuevo tope */
}
/* Desapilar (pop): elimina el nodo cabeza de la lista
Complejidad de tiempo: O(1) */
struct Node* pop(struct Node* top) {
if (top == NULL) {
printf("¡La pila está vacía!\n");
return NULL;
}
struct Node* temp = top;
printf("Desapilando: %d\n", top->data);
top = top->next; /* El tope se mueve al siguiente */
free(temp); /* Liberar el tope anterior */
return top;
}
/* Verificar si está vacía */
bool isEmpty(struct Node* top) {
return top == NULL;
}
int main() {
struct Node* stackTop = NULL; /* Inicialmente la pila está vacía */
stackTop = push(stackTop, 100); /* Apilar: 100 */
stackTop = push(stackTop, 200); /* Apilar: 200 */
stackTop = push(stackTop, 300); /* Apilar: 300 */
printf("Tope: %d\n", stackTop->data); /* Salida: Tope: 300 */
stackTop = pop(stackTop); /* Desapilar: 300 */
stackTop = pop(stackTop); /* Desapilar: 200 */
stackTop = pop(stackTop); /* Desapilar: 100 */
if (isEmpty(stackTop)) {
printf("La pila ya está vacía\n"); /* Salida: La pila ya está vacía */
}
return 0;
}
La ventaja de la pila implementada con lista enlazada es que teóricamente no tiene límite de capacidad fijo, solo está limitada por la memoria disponible del sistema. Pero cada nodo requiere espacio adicional para el puntero.
Escenarios de aplicación de la pila
| Escenario de aplicación | Descripción | Por qué usar una pila |
|---|---|---|
| Pila de llamadas a funciones | Guarda la dirección de retorno y las variables locales de la función | Las llamadas a funciones son anidadas, naturalmente LIFO |
| Coincidencia de paréntesis | Verifica si los paréntesis en el código están correctamente emparejados | Al encontrar un paréntesis izquierdo se apila, al encontrar uno derecho se compara con el tope y se desapila |
| Operación de deshacer | Función de deshacer en editores de texto y navegadores | Cada operación se apila, al deshacer se desapila |
| Evaluación de expresiones | Calcula el valor de expresiones infijas/posfijas | Los operandos se apilan, después de calcular el operador, el resultado se apila |
| Búsqueda en profundidad | Algoritmo de recorrido DFS de grafos | Usa una pila explícitamente o recursión (uso implícito de la pila de llamadas) |