Lección 10 · 10 de 20

Una pila y una cola · C

Use una pila en C para comprobar si los paréntesis de una expresión están equilibrados y una cola circular para los trabajos de una impresora.

C · Una pila y una cola en DMarlon Studio: el código del ejemplo y su salida en la terminal

Una pila (LIFO, *last in, first out*) solo deja meter y sacar por arriba, como una pila de platos. Aquí es un array stack con un índice top: apilar es stack[top++] = c y desapilar, stack[--top].

balanced comprueba los paréntesis de una expresión. Cada apertura ((, [ o {) se apila. Cada cierre tiene que coincidir con la última apertura que queda en la pila: "([{"[closer - ")]}"] da la apertura que corresponde al cierre encontrado, porque las dos cadenas tienen el mismo orden. Si la pila está vacía o no coincide, no está equilibrada; y si al final queda algo abierto, como en ((total), tampoco.

Una cola (FIFO, *first in, first out*) atiende por orden de llegada, como la de la impresora. Queue es un búfer circular: head es el primero que espera y count, cuántos hay. enqueue escribe en la posición (head + count) % CAP y dequeue lee en head y la adelanta.

El % CAP hace que los índices vuelvan a 0 al llegar al final del array, así que el hueco que deja cada trabajo impreso se aprovecha y nunca hay que mover elementos.

Las dos estructuras tienen aquí capacidad fija, CAP, y balanced devuelve 0 si se llenara la pila. Con lo visto en la lección de realloc se pueden convertir en estructuras que crecen.

Código · main.c

#include <stdio.h>#include <string.h>#define CAP 16  // room in the stack and in the queueint balanced(const char *text) {    char stack[CAP]; int top = 0;  // a stack (LIFO): last in, first out    for (; *text; text++) {        const char *closer = strchr(")]}", *text);        if (strchr("([{", *text)) {            if (top == CAP) return 0;  // too deep for our stack            stack[top++] = *text;      // push        } else if (closer && (top == 0 || stack[--top] != "([{"[closer - ")]}"]))            return 0;                  // pop: it must be the matching opener    }    return top == 0;  // nothing left open}typedef struct { const char *items[CAP]; int head, count; } Queue;  // FIFO ring buffervoid enqueue(Queue *q, const char *job) { q->items[(q->head + q->count++) % CAP] = job; }const char *dequeue(Queue *q) {  // head moves forward and wraps around    const char *job = q->items[q->head];    q->head = (q->head + 1) % CAP; q->count--;    return job;}int main(void) {    const char *exprs[] = {"(a[i] + b) * {c}", "f(x[0)]", "((total)"};    for (int i = 0; i < 3; i++)        printf("%-18s %s\n", exprs[i], balanced(exprs[i]) ? "balanced" : "NOT balanced");    Queue printer = {.head = 0, .count = 0};    enqueue(&printer, "invoice.pdf"); enqueue(&printer, "photo.png");    printf("Printing %s\n", dequeue(&printer)); enqueue(&printer, "report.docx");    while (printer.count > 0) printf("Printing %s\n", dequeue(&printer));    return 0;}

Salida · cc main.c -o main && ./main

(a[i] + b) * {c}   balanced
f(x[0)]            NOT balanced
((total)           NOT balanced
Printing invoice.pdf
Printing photo.png
Printing report.docx

Para recordar

Pila: el último que entra es el primero que sale.
Cola: el primero que entra es el primero que sale.
top++ apila y --top desapila.
Un búfer circular avanza con % CAP y no mueve datos.

Ejercicio

Añada a Queue una función int is_full(const Queue *q), haga que enqueue devuelva 0 si la cola está llena y pruébela con CAP a 3.