How do I implement a queue in C without front, rear or count variables?

Question

I'm given an assignment to implement a queue in C yet all the tutorials and videos use front, rear and count variables while our assignment is asking us to do it without. How would I go about completing this program? What should I have in the back of my mind when implementing this data structure?

For context, here are the structs we're allowed to use:

// The type for a node in the list.
struct node
{
    struct node *next;
    struct node *prev;
    char *value;
};

// The type for a list.
typedef struct list
{
    struct node head;
} List;

typedef struct queue
{
    List *list;
} Queue;

Answer 1

I hope this can works fine for you. I haven't tested too much the reliability of this code, but it passed the standard valgrind memory test, so it should be fine. Please let me know if you find some bugs.

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

#define IS_NULL(ptr) ((ptr) == NULL)

#define READY 1

struct node
{
    struct node *next;
    struct node *prev;
    char *value;
};

// The type for a list.
typedef struct list
{
    struct node head;
} List;

typedef struct queue
{
    List *list;
} Queue;


int enqueue (Queue queue, char *key);
char *dequeue (Queue queue);
int queue_init (Queue * queue);
void dispose(Queue queue);

static struct node * new_node(char *key, struct node *next, struct node *prev);

int enqueue (Queue queue, char *key){
    char *new_string;
    struct node *head, *new;
    if (IS_NULL(queue.list) || IS_NULL(key) || IS_NULL((new_string = strdup(key)))){
        return !READY;
    }
    head = &queue.list->head;
    new = new_node(new_string, NULL, head->prev);
    if (IS_NULL(new)){
        free(new_string);
        return !READY;
    }
    if (IS_NULL(head->next)){
        head->next = new;
    } else {
        head->prev->next = new;
    }
    head->prev = new;
    return READY;
}

char *dequeue (Queue queue){
    char *result;
    struct node *head, *selected;
    if (IS_NULL(queue.list)){
        return NULL;
    }
    head = &queue.list->head;
    selected = head->next;
    if (IS_NULL(selected)){
        return NULL;
    }
    head->next = selected->next;
    result = selected->value;
    free(selected);
    return result;
}

int queue_init (Queue * queue){
    if (IS_NULL(queue) || IS_NULL(queue->list = calloc(1, sizeof(List)))){
        return !READY;
    }
    return READY;
}

void dispose(Queue queue){
    if (IS_NULL(queue.list)){
        return;
    }
    struct node *ptr = queue.list->head.next, *ptr_1;
    while (ptr != NULL){
        free(ptr->value);
        ptr_1 = ptr;
        ptr = ptr->next;
        free(ptr_1);
    }
    free(queue.list);
}

static struct node * new_node(char *key, struct node *next, struct node *prev){
    struct node *new;
    if (IS_NULL((new = malloc(sizeof(struct node))))){
        return NULL;
    }
    new->value = key;
    new->next = next;
    new->prev = prev;
    return new;
}

void queue_print(Queue queue){
    char *string = dequeue(queue);
    if (IS_NULL(string)) return;
    fprintf(stdout, "\n%s", string);
    free(string);
}

int main(){
    Queue my_queue;
    if (queue_init(&my_queue) != READY){
        exit(EXIT_FAILURE);
    }
    enqueue(my_queue, "test1");
    enqueue(my_queue, "test2");
    queue_print(my_queue);
    enqueue(my_queue, "test3");
    enqueue(my_queue, "test4");
    queue_print(my_queue);
    queue_print(my_queue);
    dispose(my_queue);
}