A simple queue implementation in C.

queue.c

#include <stdlib.h>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Header
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#define IN    /* IN */
#define OUT   /* OUT */
#define INOUT /* INOUT */

struct Value { };

struct Value *ValueNew();
void ValueDelete(INOUT struct Value **value);

struct QueueNode {
  struct Value *value;
  struct QueueNode *next;
};

struct QueueNode *QueueNodeNew(IN struct Value *value, IN struct QueueNode *next);
void QueueNodeDelete(INOUT struct QueueNode **node);

struct Queue {
  struct QueueNode *first;
  struct QueueNode *last;
};

struct Queue *QueueNew();
inline bool QueueIsEmpty(IN const struct Queue *queue);
void QueuePush(INOUT struct Queue *queue, IN struct Value *value);
struct Value *QueuePop(INOUT struct Queue *queue);
void QueueDelete(INOUT struct Queue **queue);

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Value
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct Value *ValueNew() {
  struct Value *value;
  
  value = malloc(sizeof(struct Value));
  
  return value;
}

void ValueDelete(INOUT struct Value **value) {
  free(*value);
  *value = NULL;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Queue Node
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct QueueNode *QueueNodeNew(IN struct Value *value, IN struct QueueNode *next) {
  struct QueueNode *node;
  
  node = malloc(sizeof(struct QueueNode));
  node->value = value;
  node->next = next;
  
  return node;
}

void QueueNodeDelete(INOUT struct **node) {
  if ((*node)->next) {
    QueueNodeDelete(&(*node)->next);
  }
  if ((*node)->value) {
    ValueDelete(&(*node)->value);
  }
  free(*node);
  *node = NULL;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Queue
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct Queue *QueueNew() {
  struct Queue *queue;

  queue = malloc(sizeof(struct Queue));
  queue->first = NULL;
  queue->last = NULL;

  return queue;
}

inline bool QueueIsEmpty(IN const struct Queue *queue) {
  return !queue->first;
}

void QueuePush(INOUT struct Queue *queue, IN struct Value *value) {
  struct QueueNode *node;

  node = QueueNodeNew(value, NULL);

  if (QueueIsEmpty(queue)) {
    queue->first = node;
    queue->last = node;
  } else {
    queue->last->next = node;
    queue->last = node;
  }
}

struct Value *QueuePop(INOUT struct Queue *queue) {
  struct QueueNode *node;
  struct Value *value;

  node = queue->first;
  if (node->next) {
    queue->first = node->next;
  } else {
    queue->first = NULL;
    queue->last = NULL;
  }

  value = node->value;

  node->value = NULL;
  node->next = NULL;
  QueueNodeDelete(&node);

  return value;
}

void QueueDelete(INOUT struct Queue **queue) {
  if (!QueueIsEmpty(*queue)) {
    QueueNodeDelete(&(*node)->first);
  }
  (*queue)->last = NULL;
  free(*queue);
  *queue = NULL;
}