Mi implementación de cola (en C)

Question

Esta es mi implementación de cola en C. No dude en hacerme cualquier pregunta relacionada con mi código. Cualquier consejo o sugerencia es bienvenido, incluidos los consejos sobre nombres / espacios / convenciones comunes.

Queue_node, Queue, create_queue, destroye_queue, queue_push, queue_pop están destinados a funcionar con cualquier estructura de nodo que tenga un miembro struct Queue_node *nexty funciones para crear el nodo y destruirlo.

#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;
}

Reescribí el código siguiendo la sugerencia de @ vnp. Aquí está la nueva versión: Mi implementación de cola (en C) [V.2]

Answer 1

• SECO . queue_pushasigna queue_backal input_nodepase lo que pase. Considerar

    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 están ahí solo para aclarar la lógica).

  Lo mismo ocurre con queue_pop.

• Por lo general, no queremos que el código del cliente esté al tanto de los contenedores, ni dependa de ellos. Si por casualidad eventualmente decide mantener las coordenadas ponderadas en un árbol en lugar de una lista, necesitaría rediseñar struct Weighted_coord_nodey el código circundante. Recomiendo encarecidamente struct Queue_nodemantener el puntero en los datos reales

    struct Queue_node {
        struct Queue_node * next;
        void * client_data;
    };