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

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

我对这个环形队列的动态数组实现中有一个疑问，就是在什么时候前端指针会超过后端指针？

- vinodkumar wagh

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

- Weather Vane

---

讲解得非常清楚，我明白了，非常感谢！ - vinodkumar wagh

好的，但在OP的代码中，移动循环是for(int i = 0 ; i<q->front ; i++) - 第一部分，而不是for (i=q-<front;i<size;i++)，后者会移动第二部分。我想一个高效的实现会选择这两个范围中较小的一个。 - AShelly

@AShelly，0到5没有数据，数据最初是从6到1的。 - Weather Vane

@WeatherVane 但是for循环正在从索引0复制到最后一个索引。我不理解你的最后一张图。 - vinodkumar wagh

@AShelly，现在的编辑显示缓冲区的相同部分已移动，就像OP的代码一样：有两种方法可以进行调整。 - Weather Vane

Answer 2

所谓的“前端”是读指针，下一个要读取的元素。 “后端”是写指针，最后插入的元素。

任何时候，当循环队列中插入的元素超过capacity时，rear会回到开头，并且front > rear成立。这个机制使得它成为了一个循环缓冲区。

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

（我认为，如果只复制rear之前的元素，也是正确的。如所述，它正在复制陈旧的元素。）

- AShelly