A queue of integer values, implemented as a linked-list.

queue.c

// A queue of integer values, implemented as a linked-list.
// Careful, don't pop the queue if it's empty!
// Copyright (c) James Davidson 2015.
// Publicly released under the terms of the MIT License.
// For educational purposes only, obviously; no warranty implied.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#define empty(Q) (q_length(Q) == 0)

typedef struct item {
    int value;
    struct item * next;
} item_t;
typedef item_t * queue_t;

void test();
queue_t q_create ();
queue_t q_pop (queue_t,int*);
queue_t q_prepend (queue_t,int);
queue_t q_append (queue_t,int);
queue_t q_reject (queue_t,int);
queue_t q_reject_all (queue_t);
queue_t q_deduplicate (queue_t);
void q_print (queue_t);
int q_length (queue_t);

int
main (int argc, char ** argv) {
  test();
  return EXIT_SUCCESS;
}

void
test () {
  int x;
  queue_t q;
  q = q_create(); q_print(q);
  q = q_prepend(q,1); q_print(q);
  q = q_prepend(q,2); q_print(q);
  q = q_reject(q,4); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_reject_all(q); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_reject(q,3); q_print(q);
  q = q_append(q,0); q_print(q);
  q = q_reject_all(q); q_print(q);
  q = q_deduplicate(q); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,3); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_prepend(q,8); q_print(q);
  q = q_deduplicate(q); q_print(q);
  if (!empty(q)) {
    q = q_pop(q,&x); printf("popped %d\n",x); q_print(q);
  }
  q = q_append(q,4); q_print(q);
  q = q_reject_all(q); q_print(q);
  return;
}

queue_t
q_create () {
  return NULL;
}

queue_t
q_pop (queue_t queue, int * v) {
  assert(queue != NULL);
  *v = queue->value;
  return queue->next;
}

queue_t
q_prepend (queue_t queue, int v) {
  item_t * new_head;
  new_head = malloc(sizeof(item_t));
  new_head->value = v;
  new_head->next = queue;
  return new_head;
}

queue_t
q_append (queue_t queue, int v) {
  item_t * current;
  item_t * new_tail;
  new_tail = malloc(sizeof(item_t));
  new_tail->value = v;
  new_tail->next = NULL;
  if (queue == NULL) {
    queue = new_tail;
  }
  else {
    for (current=queue; current->next != NULL; current=current->next);
    current->next = new_tail;
  }
  return queue;
}

queue_t
q_reject (queue_t queue, int v) {
  item_t * current;
  item_t * new_queue;
  new_queue = q_create();
  for (current = queue; current != NULL; current = current->next) {
    if (current->value != v) {
      new_queue = q_append(new_queue,current->value);
    }
  }
  q_reject_all(queue);
  return new_queue;
}

queue_t
q_reject_all (queue_t queue) {
  item_t * prev;
  while (queue != NULL) {
    prev = queue;
    queue = queue->next;
    free(prev);
  }
  return NULL;
}

queue_t
q_deduplicate (queue_t queue) {
  item_t * current;
  item_t * new_queue;
  new_queue = q_create();
  if (queue == NULL) {
  }
  else {
    for (current = queue; current != NULL; current = current->next) {
      new_queue = q_reject(new_queue,current->value);
      new_queue = q_append(new_queue,current->value);
    }
  }
  q_reject_all(queue);
  printf("dedupe!\n");
  return new_queue;
}

void
q_print (queue_t queue) {
  item_t * prev;
  int length;
  length = q_length(queue);
  if (queue == NULL) {
    printf("empty");
  }
  else {
    while (queue != NULL) {
      prev = queue;
      queue = queue->next;
      printf("%d ",prev->value);
    }
  }
  printf(" (length %d)\n", length);
  return;
}

int
q_length (queue_t queue) {
  int counter;
  item_t * current;
  for (counter = 0, current = queue;
       current != NULL;
       current = current->next) {
    counter++;
  }
  return counter;
}