c - 为什么我要覆盖我的结构？实现队列，但是行不通

Question

我需要在C语言中编程队列结构来分配任务。节点有一个指向下一个节点和值的指针（到目前为止，是正常的）。但是，由于我需要在线程中使用它，我将malloc堆中的所有容量。
但是，节点和队列的定义如下：

//Element of a queue
struct queue_node {
    // Pointer to next element in the queue
    struct queue_node* next;
    // Value/Data of the queue element
    int value;
};

// Queue data structure
    struct queue {
    // Head of the linked list
    struct queue_node* head;
    // Max capacity of the queue
    int capacity;
    // Current size of the queue. size <= capacity, always
    int size;
};

我遇到的问题是推送元素，因为我没有任何关于分配内存的开始或结束的信息。所以我决定让头部节点始终是空间中的第一个节点，这样我就可以使用容量
我把基本功能编程如下：

struct queue* queue_new(int capacity){

    struct queue_node* head1 = malloc(sizeof(struct queue_node)*capacity);

    struct queue* ret = malloc(sizeof(struct queue));

    /*
    struct queue_node head2;
    head2.next = NULL;

    (*head1) = head2;
    */
    (*head1).next = NULL;

    (*ret).head = head1;
    (*ret).size = 0;
    (*ret).capacity = capacity;

    return ret;

    }



void queue_delete(struct queue* queue){
    free((*queue).head);
    free(queue);
    }

所以。但是，当我想把东西推到队列里的时候，我就麻烦了。显然，首先要做的，就是填满脑袋。这似乎奏效了。但是将元素附加到头节点并不：

int queue_push_back(struct queue* queue, int value){

    if((*queue).size >= (*queue).capacity){
        return -1;
    }else if((*queue).size == 0){
        (*(*queue).head).value = value;
        (*queue).size++;
        return (*queue).size;
    } else{



        if((*(*queue).head).next == NULL){          ////((*queue).head + sizeof(struct queue_node))

            printf("Intern queue size 1: %d\n", (*queue).size);

            (*(*queue).head).next = ((*queue).head + sizeof(struct queue_node));
            printf("Error here?\n");
            (*(*(*queue).head).next).value = value;
            printf("Error here 2?\n");
            (*(*(*queue).head).next).next = NULL;
            printf("Error here 3?\n");


            printf("Intern queue size 2: %d\n", (*queue).size);
            printf("Intern queue capacity: %d\n", (*queue).capacity);

            (*queue).size++;
            return (*queue).size;

        }
}

我跳过了普通情况下的代码，因为这根本不起作用。出于某种原因，如果我想推送第二个元素，它将重写我的队列结构。我也不知道为什么。
有人能帮我告诉我，我做错什么了吗？

Answer 1

你似乎在尝试混合两种不同的方法来解决这个问题：
将队列维护为数组，并且
将队列维护为链接列表。
为一个块中的全部节点分配空间，将队列头保持在块的开头，实际上首先具有固定的队列容量，这些都是类数组使用的特征。另一方面，具有带有“next”指针的元素节点结构是链表的形式。
如果您将队列作为一个数组来管理，那么next指针是多余的，如果您实际使用它们的话，它们确实在收缩。相反，您始终可以通过指向节点块开头的指针和节点索引来标识和导航到节点：my_queue_ptr->head[node_num]。您还可以根据队列的当前大小标识下一个可用节点：my_queue_ptr->head[my_queue_ptr->size]。
但是，每当您将一个节点出列时，您必须将所有其他节点（或者至少是它们的数据）向前移动一个位置。如果你移动整个节点，那么你就把它们的next指针搞砸了，因为每个指向位置的东西都不同，而且与以前的不同，有着不同的意义。
另一方面，如果将队列作为链表管理，则在一个块中分配所有节点是没有意义的。相反，传统的做法是为每个入队列的值分配一个新节点，并取消分配每个出队列的值的节点。在这种情况下，您将在第一个元素排队和任何元素出列时修改队列的head指针。如果您没有维护指向当前尾部的指针（目前您没有），那么每次将元素排队时，您都需要遍历列表以找到尾部节点，并在那里追加新节点。
更新：
如果您仍然继续您所描述的内容，那么对我来说唯一有意义的方法就是采用基于数组的方法，并且完全忽略数据结构的链表方面。您提供的queue_new()和queue_delete()函数对此是合理的。另一方面，您的queue_push_back()甚至在内部都不一致，更不适合使用类似数组的方法。
不过，在开始之前，我要详细说明一下，我想指出的是，您的代码不必要地难以阅读。当然，这里已经介绍了->操作符；它是专门为方便使用指向结构的指针而设计的，特别是方便使用指向结构的指针链。这里是queue_push_back()函数的第一部分，重写为使用->；显示的部分完全等同于原始函数的相应部分：

int queue_push_back(struct queue* queue, int value){

    if (queue->size >= queue->capacity) {
        return -1;
    } else if (queue->size == 0) {
        queue->head->value = value;
        queue->size++;
        return queue->size;
    } else {

    // ...

}

至少对我来说，读起来容易多了。现在，在更少的干扰下，更容易看到您设置的头节点的唯一属性是它的 value。您没有设置它的 next指针。如果您理解我的建议，那么您将认识到这实际上很好——您将使用数组中的索引来访问元素，而不是链接，这最多是多余的。
但是现在考虑一下当你推下一个元素时你想做什么。第一件事是测试头节点的 next指针的值，这是您从未设置过的。未定义的行为结果。现在您可以管理这些链接并使用它们（尽管如果您希望支持容量大于2的队列，您需要比现在更复杂的东西），但是正如我所说，我的建议是完全忽略这些链接。
已经验证队列有空间容纳另一个元素，您可以直接访问该元素作为 queue->head[queue->size]：

    queue->head[queue->size].value = value;
    queue->size++;

瞧，就这些了。但是等等，情况会好起来的！如果仔细观察，就会发现第一个节点的情况与其他节点的情况几乎没有区别。事实上，区别纯粹是语法上的；第一个节点（当 queue->size == 0时）也会被我刚才介绍的代码很好地服务；它根本不需要特殊情况：

int queue_push_back(struct queue* queue, int value){
    if (queue->size >= queue->capacity) {
        return -1;
    } else {
        queue->head[queue->size].value = value;
        return ++queue->size;
    }
    // That's all, folks!
}