Stack

An array-based stack that stores elements of any type using a fixed-capacity buffer.

Interface

typedef struct Stack stack_t;

/**
 * Create a new stack that stores elements of @p element_size bytes
 * with the given @p capacity.
 *
 * @param element_size Size in bytes of each element.
 * @param capacity     Maximum number of elements the stack can hold.
 * @return Pointer to the newly created stack, or NULL on allocation failure.
 *         The caller must free the returned stack with stack_destroy().
 */
stack_t *stack_create(size_t element_size, int capacity);

/**
 * Destroy the stack and free all associated memory.
 */
void stack_destroy(stack_t *s);

/**
 * Check whether the stack is empty.
 * @return Non-zero if empty, 0 otherwise.
 */
int stack_is_empty(const stack_t *s);

/**
 * Check whether the stack is full.
 * @return Non-zero if full, 0 otherwise.
 */
int stack_is_full(stack_t *s);

/**
 * Push a copy of @p element onto the stack.
 * @return 0 on success, non-zero on failure.
 */
int stack_push(stack_t *s, const void *element);

/**
 * Remove the top element from the stack.
 * @return 0 on success, non-zero on failure.
 */
int stack_pop(stack_t *s);

/**
 * Copy the top element into the buffer pointed to by @p element
 * without removing it from the stack.
 * @return 0 on success, non-zero on failure.
 */
int stack_peek(const stack_t *s, void *element);

Implementation

#include "data_structures.h"

#include <stdlib.h>
#include <string.h>

struct Stack {
    void *data;
    int top;
    int capacity;
    size_t element_size;
};

stack_t *stack_create(const size_t element_size, const int capacity)
{
    stack_t *s = malloc(sizeof(stack_t));
    s->data = malloc(capacity * element_size);
    s->top = -1;
    s->capacity = capacity;
    s->element_size = element_size;
    return s;
}

void stack_destroy(stack_t *s)
{
    if (s) {
        free(s->data);
        free(s);
    }
}

int stack_is_empty(const stack_t *s)
{
    return s->top == -1;
}

int stack_is_full(stack_t *s)
{
    return s->top == s->capacity - 1;
}

int stack_push(stack_t *s, const void *element)
{
    if (stack_is_full(s)) {
        return 0;
    }
    memcpy((char *)s->data + (++s->top * s->element_size), element, s->element_size);
    return 1;
}

int stack_pop(stack_t *s)
{
    if (stack_is_empty(s)) {
        return 0;
    }
    s->top--;
    return 1;
}

int stack_peek(const stack_t *s, void *element)
{
    if (stack_is_empty(s)) {
        return 0;
    }
    memcpy(element, (char *)s->data + (s->top * s->element_size), s->element_size);
    return 1;
}

Complexity