Pila y cola en C sobre un array, con un búfer circular

Una pila y una cola en C implementadas sobre un array, sin reservar memoria por cada elemento y sin salirse nunca de los límites: la pila resuelve un problema clásico, comprobar que los paréntesis están equilibrados, y la cola usa un búfer circular, la estructura de los controladores y los registros.

Una pila (stack) saca primero lo último que entró, como una pila de platos; una cola (queue) saca primero lo primero que entró, como la fila de una tienda. Las dos se implementan bien sobre un array, sin un malloc por elemento.

Una pila sobre un array

#include <stdio.h>

#define CAPACIDAD 8

typedef struct {
    char datos[CAPACIDAD];
    size_t tope;
} Pila;

bool apilar(Pila *p, char c)
{
    if (p->tope == CAPACIDAD) return false;
    p->datos[p->tope++] = c;
    return true;
}

bool desapilar(Pila *p, char *c)
{
    if (p->tope == 0) return false;
    *c = p->datos[--p->tope];
    return true;
}

/* Comprueba que los paréntesis, corchetes y llaves estén bien emparejados. */
bool equilibrado(const char *s)
{
    Pila p = {};
    for (; *s != '\0'; s++) {
        char abre;
        switch (*s) {
        case '(': case '[': case '{':
            if (!apilar(&p, *s)) return false;
            break;
        case ')': case ']': case '}':
            if (!desapilar(&p, &abre)) return false;
            if ((*s == ')' && abre != '(') || (*s == ']' && abre != '[') || (*s == '}' && abre != '{')) return false;
            break;
        }
    }
    return p.tope == 0;
}

int main(void)
{
    const char *pruebas[] = {"f(a[1], {2, 3})", "f(a[1)]", "((x)", "x)", "{[()()]}"};
    for (int i = 0; i < 5; i++) {
        printf("%-16s %s\n", pruebas[i], equilibrado(pruebas[i]) ? "bien" : "mal");
    }
    return 0;
}

salidaf(a[1], {2, 3})  bien
f(a[1)]          mal
((x)             mal
x)               mal
{[()()]}         bien

La pila es un array y un índice, tope, que dice cuántos elementos hay. apilar escribe en datos[tope] y lo incrementa; desapilar lo decrementa y lee. Las dos comprueban los límites: una pila llena o vacía devuelve false en lugar de escribir fuera del array. El uso clásico es el del ejemplo: cada símbolo que abre se apila, y cada uno que cierra tiene que coincidir con el último abierto. Así comprueban los compiladores y los editores que los paréntesis cuadran.

Una cola circular

Una cola sobre un array normal tiene un problema: al sacar del principio, o se mueven todos los elementos o se desperdicia el hueco. La solución es el búfer circular: dos índices, uno para leer y otro para escribir, que al llegar al final del array vuelven al principio:

#include <stdio.h>

#define CAPACIDAD 4

typedef struct {
    int datos[CAPACIDAD];
    size_t inicio;
    size_t cuantos;
} Cola;

bool encolar(Cola *c, int v)
{
    if (c->cuantos == CAPACIDAD) return false;
    c->datos[(c->inicio + c->cuantos) % CAPACIDAD] = v;
    c->cuantos++;
    return true;
}

bool desencolar(Cola *c, int *v)
{
    if (c->cuantos == 0) return false;
    *v = c->datos[c->inicio];
    c->inicio = (c->inicio + 1) % CAPACIDAD;
    c->cuantos--;
    return true;
}

int main(void)
{
    Cola c = {};
    for (int i = 1; i <= 5; i++) {
        if (!encolar(&c, i * 10)) printf("Cola llena: %d se queda fuera\n", i * 10);
    }

    int v;
    desencolar(&c, &v);
    printf("Sale %d\n", v);
    desencolar(&c, &v);
    printf("Sale %d\n", v);

    encolar(&c, 60);
    encolar(&c, 70);
    printf("Inicio en la posición %zu; quedan:", c.inicio);
    while (desencolar(&c, &v)) printf(" %d", v);
    printf("\n");
    return 0;
}

salidaCola llena: 50 se queda fuera
Sale 10
Sale 20
Inicio en la posición 2; quedan: 30 40 60 70

Después de sacar dos elementos, el 60 y el 70 se escriben en las posiciones 0 y 1, que habían quedado libres, y la cola sigue saliendo en orden. Guardar cuantos en lugar de un segundo índice evita la ambigüedad clásica de los búferes circulares: con dos índices iguales, ¿la cola está llena o vacía? Los búferes circulares están en todas partes: los controladores de red y de sonido, los registros de eventos que guardan solo lo último o la comunicación entre un hilo que produce datos y otro que los consume.

• PilaCola
• Sale primerolo último que entró (LIFO)lo primero que entró (FIFO)
• Operacionesapilar, desapilarencolar, desencolar
• Sobre un arrayun índice: el topedos posiciones que dan la vuelta
• Usosdeshacer, paréntesis, recorrer árbolestareas pendientes, búferes, recorrer por niveles

Todo el código de esta página se compiló con GCC 15.3 (C23, -Wall -Wextra, sin avisos) y se ejecutó en Linux, en un contenedor limpio sin acceso a la red, antes de publicarla; las salidas están copiadas de esa ejecución.