I like your diagrams in the comments - a picture really can express much more than words sometimes!  It's a shame the text lines are so long - I recommend keeping line lengths less than a standard terminal width of 80 columns (even in these days of large monitors, most readers prefer to have more files visible side-by-side than to have longer lines in each).

---
>     struct Queue {
>       size_t capacity, size;
>       void** data;
>       size_t head, tail;
>     };

Good choice of type for `capacity` and `size`.  I'd probably have `head` and `tail` be pointers to `void*` rather than indexes.  Instead of maintaining `size` as a member, we could compute it when needed from `head` and `tail`, provided we don't ever completely fill the queue (i.e. expand it just before `head==tail`, rather than just after).

---
>       Queue* queue = calloc(1, sizeof *queue);
>       assert(queue);

That's plain wrong.  We know that `calloc()` can return zero, so claiming `queue` is non-zero is mistaken.

It seems that you think `assert()` is a tool for run-time checks, but that is not the case.  **`assert()` exists to document things we know to be true** (and, in debug builds, let us know when our claims are wrong).

The correct code is

      Queue* queue = calloc(1, sizeof *queue);
      if (!queue) { return queue; }

Not only does this perform the check in non-debug builds, it reports the failure to the caller, who can handle it appropriately.

Such misuse of `assert()` exists throughout the program.

It's not clear why we're using `calloc()` here rather than `malloc()` - we write all the storage we allocate, so the zero-initialising done by `calloc()` is just a waste of cycles.

---
>     void queue_free(Queue* queue) {
>       assert(queue);  
>       free(queue->data);

Why not just handle a null `queue`, to give an interface consistent with `free()`?  I'd write

    void queue_free(Queue* queue)
    {
        if (!queue) { return; }
        free(queue->data);
        free(queue);
    }

That makes life much easier for callers, who can now pass their `Queue*` to `queue_free()` without needing a separate path for null pointers.

---
>     if (queue->head > queue->tail) {
>       for (size_t i = queue->head; i < queue->capacity; ++i) {
>         tmp[i + queue->capacity] = tmp[i];
>         tmp[i] = NULL;
>       }
>       queue->head += queue->capacity;
>     }

I think the loop there can be replaced by a simple `memmove()`.  There should be no need to assign `NULL` to the positions between `tail` and `head`, as we'll not access those entries before they are next written.

---
`queue_iterate` has:

>       if (queue->size == 0) {
>         return;
>       }

That's unnecessary, since the rest of the function is a `for` loop that will do nothing when size is zero.  We can just omit this test.