时间戳

首页 > 解决方案 > 使用动态数组调整循环队列的大小

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

问题描述

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

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

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

标签： carraysqueuedynamic-arrays

解决方案

原因是因为它是一个循环缓冲区。假设一个缓冲区长度为 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

推荐阅读