6
\$\begingroup\$

This is my queue implementtion in C. Feel free to ask me any questions relating to my code. Any tips or suggestions are welcome, including tips on naming/spacing/common conventions.

Queue_node, Queue, create_queue, destroye_queue, queue_push, queue_pop are meant to work with any node struct which has a member struct Queue_node *next and functions to create the node and destroy the node.

#include <stdlib.h>
/* malloc(), EXIT_SUCCESS */
#include <stdio.h>
/* fprintf */
#include <stddef.h>
/* size_t */

struct Coordinate {
    int x;
    int y;
};

struct Queue_node {
    struct Queue_node *next;
};

struct Queue {
    struct Queue_node *front;
    struct Queue_node *back;

    size_t size;
};

struct Queue* create_queue(void) {

    struct Queue *created_queue = malloc(sizeof(*created_queue));

    if (created_queue == NULL) {
        return NULL;
    }

    created_queue->back = NULL;
    created_queue->front = NULL;
    created_queue->size = 0;

    return created_queue;
}

void destroy_queue(struct Queue *input_queue, void (*delete_node)(void*)) {

    while (input_queue->front != NULL) {

        struct Queue_node *deleted_node = input_queue->front;
        input_queue->front = input_queue->front->next;
        if (delete_node != NULL) {
            delete_node(deleted_node);
        }
    }
    free(input_queue);
}

void queue_push(struct Queue *input_queue, void *input_node) {

    ++input_queue->size;

    if (input_queue->front == NULL) { // first insert

        input_queue->front = (struct Queue_node*) input_node;
        input_queue->back = (struct Queue_node*) input_node;

        return;
    }

    input_queue->back->next = (struct Queue_node*) input_node;
    input_queue->back = input_queue->back->next;
}

void* queue_pop(struct Queue* input_queue) {

    if (input_queue->front == NULL) { // empty queue
        return NULL;
    }

    --input_queue->size;

    struct Queue_node *deleted_node = input_queue->front;
    input_queue->front = input_queue->front->next;

    return deleted_node;
}

/*
nodes that are queue_pop()'d must be free()'d by caller
*/

static struct Weighted_coord_node {
    struct Queue_node *next;
    // parent property

    int weight;
    struct Coordinate coord;
    // child properties
};

static struct Weighted_coord_node* create_node(struct Coordinate coord, int weight) {

    struct Weighted_coord_node *node = malloc(sizeof(*node));

    if (node == NULL) {
        return NULL;
    }
    node->next = NULL;
    node->coord = coord;
    node->weight = weight;

    return node;
}

int main() {

    struct Queue *my_queue = create_queue();
    if (!my_queue) {
        return EXIT_FAILURE;
    }

    struct Weighted_coord_node *my_node;
    
    my_node = create_node((struct Coordinate){5,5}, 0);
    if (!my_node) {
        return EXIT_FAILURE;
    }
    queue_push(my_queue, my_node);

    my_node = create_node((struct Coordinate){7,7}, 2);
    if (!my_node) {
        return EXIT_FAILURE;
    }
    queue_push(my_queue, my_node);

    my_node = create_node((struct Coordinate){11,11}, 5);
    if (!my_node) {
        return EXIT_FAILURE;
    }
    queue_push(my_queue, my_node);

    while (my_node = queue_pop(my_queue)) {
        fprintf(stderr, "POP->  X: %i, Y:%i   weight: %i\n", my_node->coord.x, my_node->coord.y, my_node->weight);
        free(my_node);
    }

    destroy_queue(my_queue, free);

    return EXIT_SUCCESS;
}

I rewrote the code following @vnp's suggestion. Here is the new version: My queue implementation (in C) [V.2]

\$\endgroup\$
2

1 Answer 1

2
\$\begingroup\$
  • DRY. queue_push assigns queue_back to the input_node no matter what. Consider

      if (input_queue->front == NULL) {
          assert(input_queue->back == NULL);
          input_queue->front = input_node;
      } else {
          assert(input_queue->back != NULL);
          input_queue->back->next = input_node;
      }
      input_queue->back = input_node;
    

    (asserts are there only to clarify the logic).

    Ditto for queue_pop.

  • Usually we don't want the client code to be aware of the containers, neither depend of them. If perchance you'd eventually decide to keep the weighted coordinates in a tree rather than a list, you'd need to redesign struct Weighted_coord_node, and the surrounding code. I strongly recommend to have struct Queue_node keeping the pointer to the actual data

      struct Queue_node {
          struct Queue_node * next;
          void * client_data;
      };
    
\$\endgroup\$
1
  • \$\begingroup\$ Thanks a lot @vnp! I have modified my code according to your suggestions and added it into my post. Is it as you had suggested? \$\endgroup\$ Oct 12, 2020 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.