Búfer circular en Java

  2. HowTo
  3. Howtos de Java
  4. Búfer circular en Java
Sheeraz Gul 15 febrero 2024
Java Java Buffer
Búfer circular en Java

Este tutorial demuestra el uso de matrices y listas vinculadas para generar un búfer circular en Java.

Búfer circular en Java

El búfer circular se conoce como una matriz que se utiliza como cola. Cuando constantemente movemos datos de un proceso a otro, no podemos almacenar esos datos en ubicaciones de memoria permanente porque tienen tiempo para recuperarlos.

Entonces, necesitamos almacenar este tipo de datos en ubicaciones temporales, conocidas como búferes, por ejemplo, la RAM. El Buffer Circular, también conocido como ring buffer, es una cola que permite el uso de la memoria de forma contigua.

El búfer circular funciona de la manera “primero en entrar, primero en salir” FIFO y se puede implementar utilizando una matriz o una lista enlazada. Entonces, comencemos a aprender con arreglos.

Use Array para crear un búfer circular en Java

Para crear el búfer circular usando una matriz, necesitamos inicializar una matriz vacía en el constructor donde se desconoce el tipo de elementos agregados a la matriz.

Se utilizan dos punteros, cabeza y cola, para la operación de inserción y eliminación, donde la cabeza es el primer elemento y la cola es el último, como se muestra en la imagen:

búfer circular en java - matriz circular buffer

Ahora hay dos operaciones principales, in y out significa inserción y eliminación:

Demostración de la operación de inserción

La inserción es una operación fácil con algunos puntos esenciales:

  1. Al principio, el tamaño de la matriz es 0, donde la posición de cabeza es 0 y la posición de cola es -1.

  2. Luego, usamos la siguiente fórmula para el índice en el que insertaremos el elemento:

    int index_position = (tail_pointer + 1) % buffer_capacity
array[index_position] = element;

  3. El tamaño de la matriz y el puntero de cola se incrementarán en 1 cuando insertemos un elemento en la matriz.

  4. Cuando el tamaño de la matriz es igual a su capacidad, no podemos agregar más elementos.

Demostración de la operación de eliminación

  1. Cuando se recupera un elemento en el puntero head, habrá un incremento de 1 en el puntero head y una disminución de 1 en el tamaño del búfer.

  2. La siguiente fórmula se utiliza para el índice en el que eliminaremos el elemento.

    int index_position = head_pointer % buffer_capacity;
Elem element = (Elem) array[index_position];

    Ahora, por ejemplo, la matriz de entrada para el búfer circular es:

    [7, 2, 5, 3, 4]

    Los elementos se imprimirán en orden utilizando el búfer circular:

    7
2
5
3
4

Intentemos implementar el método anterior para el búfer circular en Java:

package delftstack;

import java.io.*;
import java.lang.*;

class Circular_Buffer {
  // the initial capacity of the buffer
  private int buffer_capacity = 0;
  // the initial size of the buffer
  private int buffer_size = 0;
  // the head pointer
  private int head_pointer = 0;
  // the tail pointer
  private int tail_pointer = -1;
  // the array
  private Object[] demo_array;

  Circular_Buffer(int array_capacity) {
    // initialize the array capacity in the constructor
    this.buffer_capacity = array_capacity;

    // initialize the array
    demo_array = new Object[array_capacity];
  }

  // insertion
  public void Insert(Object array_element) throws Exception {
    // calculate the index to insert the element
    int index = (tail_pointer + 1) % buffer_capacity;

    // increment in the size of the array
    buffer_size++;

    if (buffer_size == buffer_capacity) {
      throw new Exception("Buffer is Overflowen");
    }

    // store the element in the array
    demo_array[index] = array_element;

    // increment the tail pointer
    tail_pointer++;
  }

  // deletion
  public Object Delete() throws Exception {
    // check if the array is empty
    if (buffer_size == 0) {
      throw new Exception("Buffer is empty");
    }

    // calculate the index of the element which is going to be deleted
    int element_index = head_pointer % buffer_capacity;

    // get the element
    Object array_element = demo_array[element_index];

    // increment the head pointer
    head_pointer++;

    // decrement the size of the array
    buffer_size--;

    // return the first element
    return array_element;
  }

  // retrieve the first element
  public Object Retrieve() throws Exception {
    // check if the array is empty
    if (buffer_size == 0) {
      throw new Exception("Buffer is empty");
    }

    // calculate the index of the element to be deleted
    int element_index = head_pointer % buffer_capacity;

    Object array_element = demo_array[element_index];

    return array_element;
  }

  // helper methods
  public boolean isEmpty() {
    return buffer_size == 0;
  }
  public int size() {
    return buffer_size;
  }
}

public class Example {
  public static void main(String[] args) throws Exception {
    // create the Circular Buffer using an array
    Circular_Buffer Array_CircularBuffer = new Circular_Buffer(10);

    // insert elements into the circular buffer
    Array_CircularBuffer.Insert(7);
    Array_CircularBuffer.Insert(2);
    Array_CircularBuffer.Insert(5);
    Array_CircularBuffer.Insert(3);
    Array_CircularBuffer.Insert(4);

    // print the elements with the delete method
    System.out.println("The elements were inserted and "
        + "now printed in the order by deletion:-");
    System.out.println(Array_CircularBuffer.Delete());
    System.out.println(Array_CircularBuffer.Delete());
    System.out.println(Array_CircularBuffer.Delete());
    System.out.println(Array_CircularBuffer.Delete());
    System.out.println(Array_CircularBuffer.Delete());
  }
}

El código anterior contiene dos clases, una para los métodos y otra para la clase principal para ejecutar las operaciones.

La primera clase incluye los métodos para la inserción, eliminación y recuperación de los elementos; el código imprimirá el elemento uno por uno aplicando la operación de inserción y eliminación del búfer circular; ver la salida:

The elements were inserted and now printed in the order by deletion:-
7
2
5
3
4

Use la lista enlazada para crear un búfer circular en Java

Para crear un búfer circular usando una lista enlazada en Java, necesitamos crear una clase auxiliar que usaremos para crear los nodos genéricos. Similar a la matriz, mantendremos la cabeza y la cola para la inserción y eliminación; el proceso se muestra en la imagen:

búfer circular en java - búfer circular de lista enlazada

Demostración de la operación de inserción

Los pasos para la inserción para crear un búfer circular usando una lista enlazada son:

  1. Al principio, el tamaño es 0, y la cabeza y la cola son nula.
  2. Luego, los elementos se agregan a la cola de la lista enlazada.
  3. La referencia de la cola se cambia entonces al puntero cabeza.
  4. Cuando los elementos se agregan a la lista enlazada, el tamaño del búfer también aumenta.
  5. Cuando el tamaño de la matriz es igual a su capacidad, no podemos agregar más elementos.

Demostración de la operación de eliminación

Los pasos para la eliminación son:

  1. Primero, recuperaremos el elemento en el puntero cabeza.

  2. En segundo lugar, cambiaremos la referencia del puntero cabeza al siguiente elemento.

  3. El tamaño del buffer tendrá un decremento de 1.

    Ahora, por ejemplo, la matriz de entrada para un búfer circular usando una lista enlazada es:

    [7, 2, 5, 3, 4]

    Los elementos se imprimirán en orden utilizando el búfer circular con una lista enlazada:

    7
2
5
3
4

Intentemos implementar el búfer circular usando la lista enlazada en código Java:

package delftstack;

class Node<Elem> {
  // the data which will be stored in the linked list
  Elem Node_Data;
  // pointer to the next node
  Node<Elem> next_pointer;

  // the constructor will initialize the data in each node
  Node(Elem Node_data) {
    this.Node_Data = Node_data;
  }
}

class LinkedList_CircularBuffer<Elem> {
  // the head node
  Node<Elem> head_element;

  // the tail node
  Node<Elem> tail_element;
  int list_size = 0;
  int list_capacity = 0;

  // the constructor for circular buffer class
  LinkedList_CircularBuffer(int list_capacity) {
    this.list_capacity = list_capacity;
  }

  // insertion
  public void Insert(Elem element) throws Exception {
    // increment in the size when elements
    // are added to the linked list
    list_size++;

    // check the buffer
    if (list_size == list_capacity) {
      throw new Exception("Buffer is Overflowen");
    }

    if (head_element == null) {
      head_element = new Node<>(element);
      tail_element = head_element;
      return;
    }

    // The node element which will be linked
    Node<Elem> temp_element = new Node<>(element);

    // reference the last element to the head node
    temp_element.next_pointer = head_element;

    // update the tail reference to the latest node.
    tail_element.next_pointer = temp_element;

    // update the tail to the latest node, which is added now
    tail_element = temp_element;
  }

  // deletion
  public Elem Delete() throws Exception {
    // check the buffer
    if (list_size == 0) {
      throw new Exception("The Buffer is empty");
    }
    // get the element
    Elem element = head_element.Node_Data;

    // update the head pointer
    head_element = head_element.next_pointer;

    // update the tail reference to the head pointer
    tail_element.next_pointer = head_element;

    // decrement in the size
    list_size--;
    if (list_size == 0) {
      // remove any references present when the buffer is null
      head_element = tail_element = null;
    }
    return element;
  }

  // retrieve the head element without deleting it
  public Elem Retrieve() throws Exception {
    // check the buffer
    if (list_size == 0) {
      throw new Exception("Empty Buffer");
    }
    // get the element
    Elem element = head_element.Node_Data;
    return element;
  }

  // helper methods
  public boolean isEmpty() {
    return list_size == 0;
  }
  public int size() {
    return list_size;
  }
}

public class Example {
  public static void main(String[] args) throws Exception {
    // create the Circular Buffer using Linked List
    LinkedList_CircularBuffer<Integer> LL_CircularBuffer = new LinkedList_CircularBuffer<>(10);

    // insert elements to the circular Buffer
    LL_CircularBuffer.Insert(7);
    LL_CircularBuffer.Insert(2);
    LL_CircularBuffer.Insert(5);
    LL_CircularBuffer.Insert(3);
    LL_CircularBuffer.Insert(4);

    // printing the elements with the method delete
    System.out.println("The elements were inserted and "
        + "now printed in the order by deletion:-");
    System.out.println(LL_CircularBuffer.Delete());
    System.out.println(LL_CircularBuffer.Delete());
    System.out.println(LL_CircularBuffer.Delete());
    System.out.println(LL_CircularBuffer.Delete());
    System.out.println(LL_CircularBuffer.Delete());
  }
}

El código anterior crea una clase genérica de nodo para realizar operaciones de lista enlazada y crea métodos para realizar operaciones de inserción, eliminación y recuperación.

El código creará un búfer circular utilizando la lista vinculada e imprimirá los elementos de la lista de entrada uno por uno, vea el resultado a continuación:

The elements were inserted and now printed in the order by deletion:-
7
2
5
3
4
Autor: Sheeraz Gul
Sheeraz Gul avatar Sheeraz Gul avatar

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook

Artículo relacionado - Java Buffer