c - 你如何在 C 中创建一个 FIFO 数组

Question

我需要一个大小有限的数组，我可以在其中压入整数。一旦阵列已满，阵列中的最后一个需要出去，所以前面有一个新点，这样我就可以继续添加数据。你怎么能在 C 中做到这一点？

Answer 1

这应该是一个合理的实现

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

struct int_queue{
    int *arr;
    size_t size;
    int len;
    int first_elem;
};

void init_int_queue(struct int_queue *queue, size_t nelems)
{
    queue->arr = malloc(nelems*sizeof(int));
    queue->first_elem = 0;
    queue->len = 0;
    queue->size = nelems;
}

void destroy_int_queue(struct int_queue *queue)
{
    free(queue->arr);
}

void push_int(struct int_queue *queue, int new_val)
{
    queue->arr[(queue->first_elem + (queue->len)++) % queue->size] = new_val;
    if (queue->len > queue->size){
        queue->len--;
        queue->first_elem++;
        queue->first_elem %= queue->size;
    }
}

int get_int(struct int_queue *queue, int index)
{
    // note does not handle the case for index out of bounds
    // wraps around for overflow
    return queue->arr[(queue->first_elem + index) % queue->size];
}

void print_int_queue(struct int_queue *queue)
{
    printf("[");
    for(int i = 0; i < queue->len; ++i){
        printf("%d", queue->arr[(queue->first_elem + i) % queue->size]);
        if(i < queue->len - 1)
            printf(", ");
    }
    printf("]\n");
}

int main(int argc, char *argv[])
{
    struct int_queue queue;
    init_int_queue(&queue, 100);
    for(int i = 0; i < 150; ++i){
        push_int(&queue, i);
    }
    print_int_queue(&queue);
    destroy_int_queue(&queue);
    return 0;
}

没有广泛测试，但它只是在每次添加新元素时环绕数组，如果长度超过大小，则跟踪第一个元素的移动。