Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

LIFO stack backed by a dynamic array in C

A LIFO stack removes the most recently pushed record first. Keep the element count separate from capacity and grow the buffer without losing data on allocation failure.

Version: ISO C23; implementation support may vary

Syntax

/* 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);

A LIFO stack follows last in, first out. push adds an element at the top, peek copies the top element without removing it, and pop copies and removes it. These are example functions, not C standard-library APIs. peek and pop require a valid pointer to a separate, writable Process object. On an empty stack they return false and leave that output unchanged.

The invariant is 0 <= size <= capacity: size counts stored records, and capacity counts reserved slots. The top is at index size - 1 only when size > 0. pop lowers size without freeing the buffer. The initial NULL means there is no buffer. NULL, available from <stdlib.h> among other headers, expands to an implementation-defined null pointer constant.

When full, push starts at one slot and then doubles capacity, capped at SIZE_MAX / sizeof *s->data. SIZE_MAX from <stdint.h> is the maximum size_t value, not the amount of available memory. The cap prevents overflow in the growth and byte-count calculations. Save the result of a nonzero-size realloc in a temporary pointer: NULL means failure and the stack stays unchanged. After successful reallocation, do not use old pointers into the buffer, including its base pointer, even if the address did not change.

If capacity cannot grow or allocation fails, push returns false. main reports the error on stderr, releases the buffer with free, and returns EXIT_FAILURE from <stdlib.h> to report unsuccessful termination to the host, without assuming a particular numeric status.

The compound literal (Process){ .id = 10 } creates an unnamed Process object; it is not a cast. This literal has automatic storage duration, and push stores the record by value, not its address. The example conforms to ISO C23; this form of the literal has existed since C99, but support for C23 mode varies by implementation.

Examples

#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;
}

Result

peek: 20
pop: 20
pop: 10
empty

Two pushes force capacity to grow from 1 to 2. After `peek` succeeds, the program prints the ID `20`. The first two calls to `pop` each return `true` and write a record through `out`: first the record with ID `20`, then the one with ID `10`. The next `pop` returns `false` because the stack is empty.

Related lessons

  • C · Lesson 87 · Advanced · Version: 3

Sources