Кольцевые трудности буферные

Question

Я попытался реализации кольцевого буфера/циклической очереди в С.

он должен принять все аргументы с помощью 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

Я думаю, что вы неправильно указали свою индексацию. В вашей реализации:

• фронт описывает следующий элемент, который должен быть удален;
• задняя часть описывает индекс, на котором находится следующий элемент;
• очередь пуста, когда передняя и задняя часть имеют специальное значение − 1; это необходимо, чтобы отличить пустую очередь от полной очереди.

Когда вы епдиеие, вы должны сделать шаги в следующем порядке:

• Проверка на переполнение;
• Отрегулируйте значения − 1 до разумных значений, когда enyuqueing в пустую очередь;
• позиция в позиции 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); 
} 

Наконец, он бизнес с − 1s приводит к некоторый кодовый беспорядок. Может быть, очередь лучше представлена ​​как 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.

Answer 2

Петля

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

не петля, если argc = 2

Затем, если вы проходите один ARG к вашему приложению данные не вставляется в очереди, и

if (queue->front == -1) 

в dequeue функция всегда true из-за init_queue.

То же самое, что и больше аргументов. Вы всегда пропускаете аргумент из-за стартового значения i=1.