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