如何在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