环形缓冲区困难

Question

我试过在 C 中实现环 buffer/cyclical 队列。

它应该通过 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 个值，那么它就会下溢（或者这是环形缓冲区的正常行为？）。我该如何解决这个问题？

Answer 1

循环

for (int32_t i = 1; i < size; ++i)

如果argc = 2

不循环

然后，如果您将单个参数传递给您的应用程序，则不会在您的队列中插入任何数据，并且

if (queue->front == -1)

在 dequeue 函数中总是 true 由于 init_queue.

同样的事情，传递了更多的参数。由于 i=1.

的起始值，您总是会跳过参数

Answer 2

我认为您的某些索引有误。在您的实施中：

前面描述了下一个应该出队的项目；
后面描述了下一个项目入队的索引；
当front和rear都为特殊值-1时队列为空；这是区分空队列和满队列所必需的。

排队时，请按以下顺序进行：

检查溢出；
将enyuqueing到空队列时的特殊值-1调整为合理值；
将项目放在位置 rear;
增量 rear，可能环绕。

你先增加后面，然后存储值，然后调整前面。当您检查 overflow.Here 的更正版本时，您也会遇到一次性错误：

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 函数是个好主意。

环形缓冲区困难

Ring buffer difficulties

c

linux

queue

circular-buffer

data-structures