使用动态数组调整循环队列的大小

Question

我分析了下面的代码很长时间，但是，我仍然没有得到这个函数的一行，如下所示：

void ResizeQueue(struct DynArrayQueue* q) {
    int size = q->capacity;
    q->capactiy = q->capacity * 2;
    q->array = realloc(q->array, q->capacity);
    if (!q->array) {
        printf("Memory error");
        return;
    }

    // The doubt lines:
    if (q->front > q->rear) {
        for (int i = 0; i < q->front; i++) {
            q->array[i + size] = q->array[i];
        }
        q->rear = q->rear + size;
    }
}

我对上述代码的疑问是，在循环队列的动态数组实现中，在什么时候前面变得比后面更大？

Answer 1

原因是因为它是一个循环缓冲区。假设一个缓冲区的长度为8，这里有两个场景A和B，缓冲区中有4个数据项，使用-表示无关数据，d表示缓冲数据：

index   0   1   2   3   4   5   6   7

A data  -   d   d   d   d   -   -   -
          begin        end

B data  d   d   -   -   -   -   d   d
           end                begin

因为 - 根据循环缓冲区的定义 - 数据回绕，头部可能低于尾部，或者尾部可能低于头部。

看看缓冲区 B 的长度加倍后会发生什么

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   d   d   -   -   -   -   -   -   -   -
           end                begin

现在应该很清楚为什么要移动数据了，所以是这样的：

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  d   d   -   -   -   -   -   -   -   -   -   -   -   -   d   d
           end                                                begin

相应调整指针或索引。

或者可以将数据调整为如下所示：

index   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
B data  -   -   -   -   -   -   d   d   d   d   -   -   -   -   -   -
                              begin        end

Answer 2

所以"front"是读指针，接下来要读的东西。 "rear" 是写指针，最后插入的东西。

任何时候循环队列插入的元素超过 capacity 个，rear 环绕到开头，front > rear 变为真。该机制使它成为一个循环缓冲区。

如果在此之后调用此调整大小代码，它会将 front 读取指针之前的所有内容复制到末尾的新 space 中，并更新 rear 以指向该指针space.

（我认为如果它只复制元素到 rear 也是正确的。正如所写的那样，它正在复制陈旧的元素。）

使用动态数组调整循环队列的大小

Resizing of the circular queue using dynamic array

c

arrays

queue

dynamic-arrays