c - 环形缓冲区的困难

我尝试在C语言中实现一个环形缓冲区/循环队列。
它应该通过argv获取所有参数，逐个将它们推到队列上，然后以相同的方式将它们从队列中弹出，并在退出时打印出来。
代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>

struct buffer
{
    int32_t front, rear, capacity, *array;
};

__attribute__ ((noreturn)) void prog_error(const char* str)
{
    perror(str);
    exit(1);
}

struct buffer *init_queue(int32_t size)
{
    struct buffer *queue = malloc(sizeof(struct buffer));

    if (!queue)
        return NULL;

    queue->capacity = size;
    queue->front = -1;
    queue->rear = -1;
    queue->array = malloc(queue->capacity * sizeof(int32_t));

    if (!queue->array)
        return NULL;

    return queue;
}


void enqueue(struct buffer *queue, int32_t x)
{
    if (((queue->rear + 1) % queue->capacity == queue->rear))
        prog_error("Queue overflow");

    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = x;

    if (queue->front == -1)
        queue->front = queue->rear;
}

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->front == -1)
        prog_error("Queue underflow");

    data = queue->array[queue->front];

    if (queue->front == queue->rear)
        queue->front = queue->rear = -1;

    queue->front = (queue->front + 1) % queue->capacity;

    return data;
}

int main(int argc, char **argv)
{
    if (argc < 2)
        prog_error("Too few arguments");

    int32_t size = (int32_t) argc - 1;

    struct buffer *queue;

    if (!(queue = init_queue(size)))
        prog_error("Allocation error");

    for (int32_t i = 1; i < size; ++i)
        enqueue(queue, (int32_t) atoi(argv[i]));

    for (int32_t i = 0; i < size; ++i)
        printf("%" PRId32 "\n", dequeue(queue));

    free(queue);
}

但最后一个值总是替换为1。
而且，如果我精确地给它1个值，那么它就会下溢（或者这是环形缓冲区的正常行为？）是的。
我该怎么解决？

最佳答案

我想你的索引有些错误。在您的实现中：
前面描述了下一个应该退出队列的项；
后面描述了下一个项目排队的索引；
当前面和后面都有特殊值-1时，队列为空；这是区分空队列和满队列所必需的。
排队时，应按以下顺序执行步骤：
检查是否溢出；
当进入空队列时，将特殊值-1调整为合理值；
将项目放置在rear位置；
增量rear，可能环绕。
先增大后部，然后存储值，然后调整前部。检查溢出时也会出现一次性错误。下面是更正的版本：

void enqueue(struct buffer *queue, int32_t x)
{
    if (queue->rear >= 0 && (queue->rear) % queue->capacity == queue->front)
        prog_error("Queue overflow");

    if (queue->front == -1)
        queue->front = queue->rear = 0;

    queue->array[queue->rear] = x;
    queue->rear = (queue->rear + 1) % queue->capacity;
}

同样，对于出列：
检查底流；
结果保存当前前端的数据；
增加正面，注意包裹和；
当前部和后部相遇时，将前部和后部调整到特殊值-1。
你把最后两点搞混了。（队列只能在移除项目后为空。）因此：

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->front == -1)
        prog_error("Queue underflow");

    data = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;

    if (queue->front == queue->rear)
        queue->front = queue->rear = -1;

    return data;
}

你排队很尴尬。通常，东西在某处排队，在其他地方排队。出列的代码通常不知道队列中有多少项。因此，队列有一种判断它是否为空的方法。使空队列出列会导致下溢。
您可以直接检查(queue->front，但这里有一个包装函数：

int isempty(struct buffer *queue)
{
    return (queue->front < 0);
}

这导致客户端代码如下：

int main(int argc, char **argv)
{
    if (argc < 2)
        prog_error("Too few arguments");

    int32_t size = (int32_t) argc - 1;
    struct buffer *queue = init_queue(size);

    if (queue == NULL)
        prog_error("Allocation error");

    for (int32_t i = 0; i < size; ++i)
        enqueue(queue, (int32_t) atoi(argv[i + 1]));

    while (!isempty(queue))
        printf("%" PRId32 "\n", dequeue(queue));

    free(queue);
}

最后，他与-1的业务导致一些代码混乱。也许队列最好用front和length表示：

struct buffer
{
    int32_t front;
    int32_t length;
    int32_t capacity;
    int32_t *array;
};

struct buffer *init_queue(int32_t size)
{
    struct buffer *queue = malloc(sizeof(struct buffer));

    if (!queue) return NULL;

    queue->capacity = size;
    queue->front = 0;
    queue->length = 0;
    queue->array = malloc(queue->capacity * sizeof(*queue->array));

    if (!queue->array) return NULL;

    return queue;
}

int isempty(struct buffer *queue)
{
    return (queue->length == 0);
}

void enqueue(struct buffer *queue, int32_t x)
{
    if (queue->length == queue->capacity) prog_error("Queue overflow");

    queue->array[queue->front + queue->length++] = x;
}

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->length == 0) prog_error("Queue underflow");

    data = queue->array[queue->front++];
    if (queue->front > queue->capacity) queue->front = 0;
    queue->length--;

    return data;
}

然后，我将停止:)，您不仅应该为队列结构本身释放内存，还应该为array成员释放内存。最好为此创建一个queue_destroy函数。