¿Cómo implementar una lista circular que sobrescribe la entrada más antigua cuando está lleno?

Para un poco de fondo, quiero usar una lista circular dentro de GWT; por lo que se utiliza la 3ª parte de lib es no lo que yo quiero.

InformationsquelleAutor Miguel Ping | 2008-10-18

7 Comentarios

  1. 43

    Una implementación muy simple, expresada en C. Implementa un buffer circular de estilo cola FIFO. Podría ser más genérico mediante la creación de una estructura que contiene el tamaño de la cola, los datos de la cola, y la cola de los índices (in y out), que habría pasado con los datos para agregar o quitar de la cola. Estas mismas rutinas podrían luego de manejar varias colas. También tenga en cuenta que esto permite que las colas de cualquier tamaño, aunque la aceleración puede ser usado si se utilizan potencias de 2 y personalizar el código más.

    /* 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
    }
    • Corrígeme si me equivoco, pero ¿no te permiten almacenar sólo 99 entradas? La expresión (en == (out-1+TAMAÑO)%TAMAÑO) dice que si uno antes de salir. Pero todavía no ha sido escrita, por lo que el 100 irregular es nunca escrito.
    • Eso es correcto, y si bien es lo suficientemente evidente para los expertos, esto va dirigido a los principiantes, así que he modificado el código para hacer que sea más explícita. Gracias por la nota!
    • Este código no es correcto. Si usted mira el buffer, no sólo deja un «hueco», el agujero «arrastra» hacia atrás a través de la memoria intermedia. Se hizo servir como fuente de inspiración para el código que he publicado aquí, así que quería darte las gracias por publicar este código para ese fin. stackoverflow.com/questions/827691/…
    • el código es correcto. Se comercializa fuera un único espacio en el búfer para que un simple vacío/lleno de prueba.
    • lo siento, pero el código es incorrecto. En los enlaces de código de arriba, yo uso exactamente el mismo tamaño de búfer y sufrir ninguno de los efectos secundarios de su código de exposiciones. No hay trade-offs son necesarios. El código no está bien.
    • Código intuitivo no es lo mismo que ser incorrecto. Esta aplicación tiene el número indicado de QUEUE_ELEMENTS y genera resultados correctos en todos los casos de borde, así como tener un número menor de variables de contabilidad de su implementación. Simple y eficaz.
    • No estoy de acuerdo con usted. Mientras que hay otras maneras de implementar una lista circular con FIFO características, este código no es incorrecto, y funciona. Deja un agujero que se arrastra hacia atrás a través de la memoria, sino que es por el diseño, y es un tiempo de procesamiento/modo eficaz de implementar un FIFO. También he revisado brevemente el código que sugiero es mejor, y no están de acuerdo en ese punto, pero parece que otros han dejado comentarios hay que hacer muchos de los puntos que me gustaría hacer. La aplicación que he proporcionado en esta respuesta no es perfecto, pero es simple, comprensible, y funciona.

  2. 2

    Utilizar una lista enlazada. Mantener separados los punteros de la cabeza y la cola. Pop de la cabeza de la lista, empujar a la cola. Si usted lo desea circular, sólo asegúrese de que la nueva cola apunta siempre a la cabeza.

    Puedo entender por qué usted puede ser que desee implementar un sistema de uso de una lista enlazada, pero ¿por qué hacer una lista circular?

  3. 2

    Si quieres una longitud fija lista circular. Usted puede utilizar un (dinámica) de la matriz. El uso de dos variables para houskeeping. Uno para la posición del siguiente elemento, uno para contar el número de elementos.

    Poner: poner elemento en el espacio libre. mover la posición (modulo de longitud). Añadir 1 a la cuenta, a menos que el recuento es igual a la lengtht de la lista.
    Obtener: sólo si cuenta>0. mover la posición a la izquierda (modulo de longitud). Disminuir el recuento.

  4. 1

    Uso de una matriz, y mantener una variable P con la primera posición disponible.

    Aumento de P cada vez que agregue un nuevo elemento.

    Saber el equivalente al índice de P en su matriz de hacer (P % n), donde n es el tamaño de la matriz.

  5. 1

    Estoy usando esto para mi microcontrolador.
    Para el código de la simplicidad de un byte será vacantes.
    Aka tamaño – 1 es la capacidad plena realidad.

    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; 
    }
    • Hola, te olvidaste de agregar struct fifo_t en el código… 🙂
    • Yo creo que se puede derivar de la createFifoToHeap() función. Donde fifo->buffer = buffer; fifo->head = 0; fifo->tail = 0; fifo->size = size; buffer es byte_t, la cabeza y la cola uint32_t y el tamaño de la size_t
  6. 0

    No creo que la cola es la mejor manera de hacer una memoria caché. Quieres ser su caché para ser realmente rápido! Y haciendo una exploración lineal de su cola no es la manera de ir a menos que usted quiere que su caché a ser muy pequeño o su memoria es muy limitada.

    Suponiendo que usted no desea una muy pequeña memoria caché o de una lenta caché utilizando una Lista Enlazada con un Hash Mapa de valor al nodo de la lista enlazada es una buena manera de ir. Siempre se puede desalojar a la cabeza, y cada vez que un elemento se accede, se puede quitar y poner en la cabeza de la lista. Para acceder directamente se puede obtener o comprobar si es en la memoria caché O(1). Desalojo de un elemento es también O(1), de modo que la actualización de la lista.

    Por ejemplo, mire LinkedHashMap en java.

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

    • Si usted está usando esto como un verdadero FIFO y no necesita de acceso aleatorio, creo que es un buffer circular será más rápido que una lista enlazada en casi todos los casos. No hay necesidad de asignar/desasignar la memoria, y el desalojo de un elemento en la parte frontal es tan simple como el incremento/decremento de un índice.
    • estás en lo correcto. No creo que esa fue la pregunta a la que me respondió. Mirando en mi respuesta, parece que me estaba respondiendo a los detalles de la implementación de una memoria caché, y no una verdadera cola FIFO. Quizá la pregunta cambiado, o entendí mal cuando me respondió.
    • Ok, tiene sentido. Sólo quería aclarar para el futuro de la lectura que podría confundirse. 😉
  7. -2

    Aquí es una forma elegante para crear dinámicamente el aumento/disminución de la cola circular utilizando java.

    Me han comentado que la mayor parte del código para easy & fast comprensión. Espero que ayude 🙂

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

    De salida:

    –dinámica de cola circular–

    1=> Capacidad: 2

    1=>2=> Capacidad: 2

    1=>2=>3=> Capacidad: 4

    1=>2=>3=>4=> Capacidad: 4

    4=>5=> Capacidad: 2

Dejar respuesta

Please enter your comment!
Please enter your name here