如何在C语言中创建一个FIFO数组

Question

我需要一个有限大小的数组，可以在其中推入整数。一旦数组满了，最后一个将从数组中删除以便腾出新的位置放置新数据。如何用C语言实现这个功能？

- Gambit12

---

只需创建一个常规数组，并维护两个指针，分别指向数组的第一个和最后一个位置。当您添加元素时，请将其添加到最后指针的位置。当您删除元素时，请从前面删除并增加第一个指针。 - thisisjaymehta

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

虽然没有经过广泛测试，但它只是在每次添加新元素时围绕数组进行包装，并跟踪第一个元素的移位，如果长度超过大小。

- Seamus