Library for the Basic Data Structures, such as Queue, in C

This looks like a good candidate for the TAILQ_* ?

#include <sys/queue.h>

“man queue” will give more details – there are simple lists, tail queues and circular queues there. Those are the macros that you’d need to bolt on your own structures, not classes of course.

The code for your scenario will look something like this (I should have made the add_to_queue return some code to check for error, and avoid global vars too, but hopefully I would be forgiven in this example):

#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

TAILQ_HEAD(tailhead, entry) head;

struct entry {
  char c;
  TAILQ_ENTRY(entry) entries;
};

void add_to_queue(char ch) {
  struct entry *elem;
  elem = malloc(sizeof(struct entry));
  if (elem) {
    elem->c = ch;
  }
  TAILQ_INSERT_HEAD(&head, elem, entries);
}

int main(int argc, char *argv[]) {
  char ch = 'A';
  int i;
  struct entry *elem;

  TAILQ_INIT(&head);
  for (i=0; i<4; i++) {
    add_to_queue(ch);
    ch++;
    add_to_queue(ch);

    elem = head.tqh_first;
    TAILQ_REMOVE(&head, head.tqh_first, entries);
    free(elem);
  }