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

Pila (Stack) — Diagrama del principio LIFO
Parte superior (Top) — Solo se puede operar desde aquí
Plato 1 (fondo de la pila)
Plato 2
Plato 3
Plato 4 (parte superior de la pila)
Fondo (Bottom) — Solo se puede retirar al final
▲ push (apilar) ▼ pop (desapilar)

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 <stdio.h>
#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 <stdio.h>
#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ónDescripciónPor qué usar una pila
Pila de llamadas a funcionesGuarda la dirección de retorno y las variables locales de la funciónLas llamadas a funciones son anidadas, naturalmente LIFO
Coincidencia de paréntesisVerifica si los paréntesis en el código están correctamente emparejadosAl encontrar un paréntesis izquierdo se apila, al encontrar uno derecho se compara con el tope y se desapila
Operación de deshacerFunción de deshacer en editores de texto y navegadoresCada operación se apila, al deshacer se desapila
Evaluación de expresionesCalcula el valor de expresiones infijas/posfijasLos operandos se apilan, después de calcular el operador, el resultado se apila
Búsqueda en profundidadAlgoritmo de recorrido DFS de grafosUsa una pila explícitamente o recursión (uso implícito de la pila de llamadas)
Otras extensiones