मैं सी में एक परिपत्र सूची (रिंग बफर) कैसे कार्यान्वित करूं?

Question

मैं एक परिपत्र सूची कैसे कार्यान्वित करूं जो पूर्ण होने पर सबसे पुरानी प्रविष्टि को ओवरराइट करता है?

थोड़ी सी पृष्ठभूमि के लिए, मैं जीडब्ल्यूटी के भीतर एक परिपत्र सूची का उपयोग करना चाहता हूं; तो एक तृतीय पक्ष lib का उपयोग नहीं है जो मैं चाहता हूं।

Answer 1

सी में व्यक्त एक बहुत ही सरल कार्यान्वयन, एक गोलाकार बफर शैली फीफो कतार लागू करता है। कतार आकार, कतार डेटा, और कतार सूचकांक (इन और आउट) युक्त संरचना बनाकर अधिक सामान्य बनाया जा सकता है, जो कतार से जोड़ने या निकालने के लिए डेटा के साथ पारित किया जाएगा। ये वही दिनचर्या तब कई कतारों को संभालने में सक्षम हो सकती हैं। यह भी ध्यान रखें कि यह किसी भी आकार की कतारों की अनुमति देता है, हालांकि यदि आप 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

एक लिंक्ड सूची का उपयोग करें। सिर और पूंछ के लिए अलग पॉइंटर्स बनाए रखें। सूची के सिर से पॉप, पूंछ पर धक्का। यदि आप इसे गोलाकार करना चाहते हैं, तो बस सुनिश्चित करें कि नई पूंछ हमेशा सिर पर इंगित करती है।

मैं समझ सकता हूं कि आप एक लिंक्ड सूची का उपयोग करके फीफो को क्यों लागू करना चाहते हैं, लेकिन इसे एक परिपत्र सूची क्यों बनाते हैं?

Answer 3

एक सरणी का उपयोग करें और पहले चर स्थिति के साथ एक चर पी रखें।

प्रत्येक बार जब आप कोई नया तत्व जोड़ते हैं तो पी बढ़ाएं।

अपने सरणी में पी के बराबर सूचकांक को जानने के लिए (पी% एन) जहां n आपके सरणी का आकार है।

Answer 4

यदि आप एक निश्चित लंबाई परिपत्र सूची चाहते हैं। आप एक (गतिशील) सरणी का उपयोग कर सकते हैं। हाउसिंग के लिए दो चर का प्रयोग करें। अगले तत्व की स्थिति के लिए, तत्वों की संख्या गिनने के लिए एक।

रखो: मुक्त जगह पर तत्व डालें। स्थिति (मॉड्यूल लंबाई) ले जाएँ। गिनती में 1 जोड़ें जब तक कि सूची की लंबाई बराबर न हो। प्राप्त करें: केवल तभी गिनें> 0। स्थिति को बाईं ओर ले जाएं (मॉड्यूल लंबाई)। गिनती घटाएं।

Answer 5

मैं इसे अपने माइक्रोकंट्रोलर के लिए उपयोग कर रहा हूं। कोड सादगी के लिए एक बाइट निष्कासित हो जाएगा। उर्फ ​​आकार - 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

मुझे नहीं लगता कि कतार बनाने का सबसे अच्छा तरीका कतार है। आप वास्तव में तेज़ होने के लिए अपना कैश बनना चाहते हैं! और अपनी कतार का रैखिक स्कैन करना तब तक नहीं है जब तक कि आप अपने कैश को वास्तव में छोटा न करें या आपकी याददाश्त वास्तव में सीमित हो।

मान लीजिए कि आप एक बहुत छोटा कैश या धीमी कैश नहीं चाहते हैं, एक लिंक्ड सूची का उपयोग करके एक लिंक्ड सूची का उपयोग करके लिंक किए गए सूची में नोड करने के लिए मूल्य का एक अच्छा तरीका है। आप हमेशा सिर को बेदखल कर सकते हैं, और जब भी कोई तत्व एक्सेस किया जाता है, तो आप इसे हटा सकते हैं और इसे सूची के प्रमुख में डाल सकते हैं। एक्सेस करने के लिए आप इसे सीधे प्राप्त कर सकते हैं या जांच सकते हैं कि यह ओ (1) में कैश में है या नहीं। तत्व का निष्पादन भी ओ (1) है और इसलिए सूची अद्यतन कर रहा है।

उदाहरण के लिए, जावा में LinkedHashMap को देखें।

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

Answer 7

यहाँ एक सुंदर तरीका गतिशील बढ़ती/परिपत्र कतार घटते जावा का उपयोग कर बनाने के लिए है।

मैंने आसान & तेज़ समझ के लिए कोड के अधिकांश भाग पर टिप्पणी की है। आशा है कि यह मदद करता है :)

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