如何在C中实现循环列表（环形缓冲区）？

Question

如何实现一个循环列表，该列表在满的时候覆盖最早的条目？

为了一点背景，我想在GWT中使用循环列表;所以使用第三方库是而不是我想要的。

Answer 1

一个非常简单的实现，用C表示。实现一个循环缓冲式FIFO队列。可以通过创建包含队列大小，队列数据和队列索引（进入和退出）的结构来使其更加通用，这些结构将与数据一起传入以添加或从队列中删除。这些相同的例程可以处理几个队列。还要注意，这允许任意大小的队列，但是如果使用2的幂和进一步自定义代码，则可以使用加速。

/* Very simple queue 
* These are FIFO queues which discard the new data when full. 
* 
* Queue is empty when in == out. 
* If in != out, then 
* - items are placed into in before incrementing in 
* - items are removed from out before incrementing out 
* Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE; 
* 
* The queue will hold QUEUE_ELEMENTS number of items before the 
* calls to QueuePut fail. 
*/ 

/* Queue structure */ 
#define QUEUE_ELEMENTS 100 
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1) 
int Queue[QUEUE_SIZE]; 
int QueueIn, QueueOut; 

void QueueInit(void) 
{ 
    QueueIn = QueueOut = 0; 
} 

int QueuePut(int new) 
{ 
    if(QueueIn == ((QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE)) 
    { 
     return -1; /* Queue Full*/ 
    } 

    Queue[QueueIn] = new; 

    QueueIn = (QueueIn + 1) % QUEUE_SIZE; 

    return 0; // No errors 
} 

int QueueGet(int *old) 
{ 
    if(QueueIn == QueueOut) 
    { 
     return -1; /* Queue Empty - nothing to get*/ 
    } 

    *old = Queue[QueueOut]; 

    QueueOut = (QueueOut + 1) % QUEUE_SIZE; 

    return 0; // No errors 
} 

Answer 2

使用链接列表。维护头部和尾部的单独指针。从列表头开始流行，推到尾巴上。如果你想要它的循环，只要确保新的尾巴总是指向头部。

我可以理解为什么你可能想要使用链表实现一个FIFO，但为什么要把它作为一个循环列表？

Answer 3

使用数组并保留变量P与第一个可用位置。

每次添加新元素时增加P.

要知道数组中的P的等效索引do（P％n）其中n是数组的大小。

Answer 4

如果你想要一个固定长度的圆形列表。您可以使用（动态）数组。使用两个变量进行保管。一个用于下一个元素的位置，一个用于计算元素的数量。

把：把元素放在自由的地方。移动位置（模数长度）。除非计数等于列表的长度，否则加1。 获取：仅当计数> 0时才有效。将位置移动到左边（模数长度）。减少计数。

Answer 5

我用我的微控制器。 为了简化代码，一个字节将被填充。 Aka size - 1实际上是满容量。

fifo_t* createFifoToHeap(size_t size) 
{ 
    byte_t* buffer = (byte_t*)malloc(size); 

    if (buffer == NULL) 
     return NULL; 

    fifo_t* fifo = (fifo_t*)malloc(sizeof(fifo_t)); 

    if (fifo == NULL) 
    { 
     free(buffer); 
     return NULL; 
    } 

    fifo->buffer = buffer; 
    fifo->head = 0; 
    fifo->tail = 0; 
    fifo->size = size; 

    return fifo; 
} 

#define CHECK_FIFO_NULL(fifo) MAC_FUNC(if (fifo == NULL) return 0;) 

size_t fifoPushByte(fifo_t* fifo, byte_t byte) 
{ 
    CHECK_FIFO_NULL(fifo); 

    if (fifoIsFull(fifo) == true) 
     return 0; 

    fifo->buffer[fifo->head] = byte; 

    fifo->head++; 
    if (fifo->head == fifo->size) 
     fifo->head = 0; 

    return 1; 
} 

size_t fifoPushBytes(fifo_t* fifo, byte_t* bytes, size_t count) 
{ 
    CHECK_FIFO_NULL(fifo); 

    for (uint32_t i = 0; i < count; i++) 
    { 
     if (fifoPushByte(fifo, bytes[i]) == 0) 
      return i; 
    } 

    return count; 
} 

size_t fifoPopByte(fifo_t* fifo, byte_t* byte) 
{ 
    CHECK_FIFO_NULL(fifo); 

    if (fifoIsEmpty(fifo) == true) 
     return 0; 

    *byte = fifo->buffer[fifo->tail]; 

    fifo->tail++; 
    if (fifo->tail == fifo->size) 
     fifo->tail = 0; 

    return 1; 
} 

size_t fifoPopBytes(fifo_t* fifo, byte_t* bytes, size_t count) 
{ 
    CHECK_FIFO_NULL(fifo); 

    for (uint32_t i = 0; i < count; i++) 
    { 
     if (fifoPopByte(fifo, bytes + i) == 0) 
      return i; 
    } 

    return count; 
} 

bool fifoIsFull(fifo_t* fifo) 
{ 
    if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1))) 
     return true; 
    else 
     return false; 
} 

bool fifoIsEmpty(fifo_t* fifo) 
{ 
    if (fifo->head == fifo->tail) 
     return true; 
    else 
     return false; 
} 

size_t fifoBytesFilled(fifo_t* fifo) 
{ 
    if (fifo->head == fifo->tail) 
     return 0; 
    else if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1))) 
     return fifo->size; 
    else if (fifo->head < fifo->tail) 
     return (fifo->head) + (fifo->size - fifo->tail); 
    else 
     return fifo->head - fifo->tail; 
} 

Answer 6

我不认为队列是制作缓存的最佳方式。你想成为你的缓存真的很快！除非你想让你的缓存非常小或者你的内存非常有限，否则对队列进行线性扫描并不是一种好的方法。

假设您不想要一个非常小的缓存或缓存缓存，那么在链表中使用具有值的哈希映射表的节点链接列表是一个好方法。您始终可以驱逐头部，并且只要访问了某个元素，就可以将其移除并放入列表的头部。对于访问，您可以直接获取它或检查它是否在O（1）中的缓存中。退出元素也是O（1），所以更新列表。

例如，查看java中的LinkedHashMap。

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

Answer 7

下面是创建动态增加/使用的java降低循环队列一种优雅的方式。

我已经评论了大部分代码，以便于快速了解&。希望它有助于:)

public class CircularQueueDemo { 
    public static void main(String[] args) throws Exception { 

     CircularQueue queue = new CircularQueue(2); 
     /* dynamically increasing/decreasing circular queue */ 
     System.out.println("--dynamic circular queue--"); 
     queue.enQueue(1); 
     queue.display(); 
     queue.enQueue(2); 
     queue.display(); 
     queue.enQueue(3); 
     queue.display(); 
     queue.enQueue(4); 
     queue.display(); 
     queue.deQueue(); 
     queue.deQueue(); 
     queue.enQueue(5); 
     queue.deQueue();  
     queue.display(); 

    } 
} 

class CircularQueue { 
    private int[] queue; 
    public int front; 
    public int rear; 
    private int capacity; 

    public CircularQueue(int cap) { 
     front = -1; 
     rear = -1; 
     capacity = cap; 
     queue = new int[capacity]; 
    } 

    public boolean isEmpty() { 
     return (rear == -1); 
    } 

    public boolean isFull() { 
     if ((front == 0 && rear == capacity - 1) || (front == rear + 1)) 
      return true; 
     else 
      return false; 
    } 

    public void enQueue(int data) { 
     if (isFull()) {   //if queue is full then expand it dynamically 
      reSize();      
      enQueue(data); 
     } else {         //else add the data to the queue 
      if (rear == -1)      //if queue is empty 
       rear = front = 0; 
      else if (rear == capacity)   //else if rear reached the end of array then place rear to start (circular array) 
       rear = 0; 
      else 
       rear++;       //else just incement the rear 
      queue[rear] = data;     //add the data to rear position 
     } 
    } 

    public void reSize() { 
     int new_capacity = 2 * capacity;     //create new array of double the prev size 
     int[] new_array = new int[new_capacity];   

     int prev_size = getSize();      //get prev no of elements present 
     int i = 0;          //place index to starting of new array 

     while (prev_size >= 0) {       //while elements are present in prev queue 
      if (i == 0) {         //if i==0 place the first element to the array 
       new_array[i] = queue[front++]; 
      } else if (front == capacity) {    //else if front reached the end of array then place rear to start (circular array) 
       front = 0; 
       new_array[i] = queue[front++]; 
      } else          //else just increment the array 
       new_array[i] = queue[front++]; 
      prev_size--;         //keep decreasing no of element as you add the elements to the new array 
      i++;           //increase the index of new array 
     } 
     front = 0;          //assign front to 0 
     rear = i-1;          //assign rear to the last index of added element 
     capacity=new_capacity;       //assign the new capacity 
     queue=new_array;         //now queue will point to new array (bigger circular array) 
    } 

    public int getSize() { 
     return (capacity - front + rear) % capacity;     //formula to get no of elements present in circular queue 
    } 

    public int deQueue() throws Exception { 
     if (isEmpty())          //if queue is empty 
      throw new Exception("Queue is empty"); 
     else { 
      int item = queue[front];      //get item from front 
      if (front == rear)        //if only one element 
       front = rear = -1; 
      else if (front == capacity)      //front reached the end of array then place rear to start (circular array) 
       front = 0; 
      else 
       front++;         //increment front by one 
      decreaseSize();         //check if size of the queue can be reduced to half 
      return item;         //return item from front 
     } 

    } 

    public void decreaseSize(){       //function to decrement size of circular array dynamically 
     int prev_size = getSize(); 
     if(prev_size<capacity/2){       //if size is less than half of the capacity 
      int[] new_array=new int[capacity/2];   //create new array of half of its size 
      int index=front;        //get front index 
      int i=0;          //place an index to starting of new array (half the size) 
      while(prev_size>=0){       //while no of elements are present in the queue 
       if(i==0)         //if index==0 place the first element 
        new_array[i]=queue[front++]; 
       else if(front==capacity){     //front reached the end of array then place rear to start (circular array)  
        front=0; 
        new_array[i]=queue[front++]; 
       } 
       else 
        new_array[i]=queue[front++];   //else just add the element present in index of front 
       prev_size--;        //decrease the no of elements after putting to new array 
       i++;          //increase the index of i 
      } 
      front=0;          //assign front to 0 
      rear=i-1;         //assign rear to index of last element present in new array(queue) 
      capacity=capacity/2;       //assign new capacity (half the size of prev) 
      queue=new_array;        //now queue will point to new array (or new queue) 
     } 
    } 

    public void display() {       //function to display queue 
     int size = getSize(); 
     int index = front; 

     while (size >= 0) { 
      if (isEmpty()) 
       System.out.println("Empty queue"); 
      else if (index == capacity) 
       index = 0; 
      System.out.print(queue[index++] + "=>"); 
      size--; 
     } 
     System.out.println(" Capacity: "+capacity); 

    } 

} 

输出：

--dynamic圆形queue--

1 =>容量：2

1 => 2 =>容量：2

1 => 2 => 3 =>容量：4

1 => 2 => 3 => 4 =>容量：4

4 => 5 =>容量：2