Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Pila LIFO sobre un arreglo dinámico en C

Una pila LIFO extrae primero el último registro insertado. Distingue el número de elementos de la capacidad y amplía el búfer sin perder datos si falla la asignación.

Versión: ISO C23; implementation support may vary

Sintaxis

/* Application-defined operations in ISO C23; not standard-library APIs. */
/* Inside main, after the application types and functions are defined. */
Stack s = { .data = NULL, .size = 0, .capacity = 0 };
Process p;
if (!push(&s, (Process){ .id = 42 }) ||
    !peek(&s, &p) ||
    !pop(&s, &p)) {
    free(s.data);
    return EXIT_FAILURE;
}
/* All three calls succeeded; p holds the record copied by pop. */
free(s.data);

Una pila LIFO sigue el principio «último en entrar, primero en salir». push añade un elemento en la cima, peek copia el de la cima sin retirarlo y pop lo copia y lo retira. Son funciones del ejemplo, no de la biblioteca estándar de C. peek y pop requieren un puntero válido a un objeto Process separado y modificable. Si la pila está vacía, devuelven false y dejan intacto el objeto de salida.

El invariante es 0 <= size <= capacity: size cuenta los registros almacenados y capacity, las posiciones reservadas. La cima está en el índice size - 1 solo si size > 0. pop reduce size sin liberar el búfer. El valor inicial NULL indica que no hay búfer. La macro NULL, disponible entre otros encabezados en <stdlib.h>, se expande a una constante de puntero nulo definida por la implementación.

Cuando la pila está llena, push empieza con una posición y luego duplica la capacidad sin superar SIZE_MAX / sizeof *s->data. SIZE_MAX, de <stdint.h>, es el valor máximo de size_t, no la cantidad de memoria disponible. El límite evita desbordamientos al calcular la capacidad y el número de bytes. Guarda el resultado de realloc con tamaño no nulo en un puntero temporal: NULL indica un fallo y la pila no cambia. Tras una reasignación exitosa, no uses los punteros antiguos al búfer ni a sus elementos, aunque la dirección no haya cambiado.

Si no se puede aumentar la capacidad o falla la asignación, push devuelve false. main notifica el error en stderr, libera el búfer con free y devuelve EXIT_FAILURE, de <stdlib.h>, para comunicar al entorno anfitrión que el programa terminó con un fallo, sin suponer un valor numérico concreto.

El literal compuesto (Process){ .id = 10 } crea un objeto Process sin nombre; no es una conversión de tipo. Este literal tiene duración de almacenamiento automática y push guarda el registro por valor, no su dirección. El ejemplo es conforme a ISO C23; esta forma del literal existe desde C99, pero la compatibilidad con el modo C23 depende de la implementación.

Ejemplos

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct { int id; } Process;

typedef struct {
    Process *data;
    size_t size;
    size_t capacity;
} Stack;

static bool push(Stack *s, Process value)
{
    if (s->size == s->capacity) {
        const size_t limit = SIZE_MAX / sizeof *s->data;
        if (s->capacity == limit)
            return false;

        size_t next = s->capacity == 0 ? 1
                    : s->capacity > limit / 2 ? limit
                    : s->capacity * 2;
        Process *new_data = realloc(s->data, next * sizeof *s->data);
        if (new_data == NULL)
            return false;
        s->data = new_data;
        s->capacity = next;
    }
    s->data[s->size] = value;
    ++s->size;
    return true;
}

static bool peek(const Stack *s, Process *out)
{
    if (s->size == 0)
        return false;
    *out = s->data[s->size - 1];
    return true;
}

static bool pop(Stack *s, Process *out)
{
    if (!peek(s, out))
        return false;
    --s->size;
    return true;
}

int main(void)
{
    Stack s = { .data = NULL, .size = 0, .capacity = 0 };
    if (!push(&s, (Process){ .id = 10 }) ||
        !push(&s, (Process){ .id = 20 })) {
        fputs("Cannot grow stack\n", stderr);
        free(s.data);
        return EXIT_FAILURE;
    }

    Process p;
    if (peek(&s, &p))
        printf("peek: %d\n", p.id);
    while (pop(&s, &p))
        printf("pop: %d\n", p.id);
    puts("empty");

    free(s.data);
    return EXIT_SUCCESS;
}

Resultado

peek: 20
pop: 20
pop: 10
empty

Dos inserciones hacen que la capacidad pase de 1 a 2. Tras una llamada correcta a `peek`, el programa muestra el identificador `20`. Las dos primeras llamadas a `pop` devuelven `true` y escriben a través de `out` primero el registro con identificador `20` y luego el de identificador `10`. La siguiente llamada a `pop` devuelve `false` porque la pila está vacía.

Lecciones relacionadas

  • C · Lección 87 · Avanzado · Versión: 3

Fuentes