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

Question

Problem: to find the right data structure for the queue:

 #include <stdio.h>                                                                                                                                                             
 #include <stdlib.h>
 #include <stdarg.h>
 #include <time.h>

 int main(int argc, const char *argv[])
 {
     Queue q;
     ch ='A';
     for (int k = 0; int k < 4; int k++) {
         q.addQ(ch);
         ch++;
         q.addQ(ch);
         ch=q.front();
         q.removeQ();
     }
     return 0;
 }

I tried to compile it, but the Queue is undeclared:

$ gcc -o Qu_1 -g q_queue.c
q_queue.c: In function 'main':
q_queue.c:8: error: 'Queue' undeclared (first use in this function)

Question: What is the library for the basic data structures such as the queue in the example?

Solution 1

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);
  }
  exit(0);
}

Solution 2

A great option is to use the C Generic Library. This is a C library modeled (loosely) on the C++ STL. It provides a queue struct, lists, etc.

Solution 3

There isn't one in the standard C library; tracing back through the related posts, it looks like the Queue data structure was meant to be written by the student.

Unlike C++, the standard C library does not provide a standard set of containers.

Comments

[Aiden Bell]

To be fair, it could have been implemented using function-pointers in the struct.

[Aiden Bell]

Actually I retract that, the state isn't passed.

[Reed Copsey]

There are options for doing this in C instead of C++ - C can be object-oriented, but it isn't required. (See Gtk for examples of at least somewhat OO C code).

[Michal aka Miki]

Interestingly, I really overlooked the complexity. I did not wait for so long code. Perhaps, Ruby's simplicity has deteriorated my mind.

[Michal aka Miki]

Thank you! It takes some time to go step-by-step through it.

[Dmytro]

As stated above, you do not need OOP to have generics. There are two kinds of generics, being free and nonfree(I made this dichotomy up just now), referring to the amount of extra work the computer needs to do to figure out the data type of the generic structure. First being free generics, which uses preprocessing, as discussed here stackoverflow.com/questions/10950828/…. Second being nonfree generics, through having void pointers/unions paired with data type identifier to help the program deduce the type being accessed at runtime.

[Mihir Luthra]

Is the queue atomic?