Kreispuffer in Java

  2. How-To's
  3. Java-Howtos
  4. Kreispuffer in Java
Sheeraz Gul 15 Februar 2024
Java Java Buffer
Kreispuffer in Java

Dieses Tutorial demonstriert die Verwendung von Arrays und verknüpften Listen zum Generieren eines Ringpuffers in Java.

Kreispuffer in Java

Der Ringpuffer ist als Array bekannt, das als Warteschlange verwendet wird. Wenn wir ständig Daten von einem Prozess zu einem anderen verschieben, können wir diese Daten nicht an permanenten Speicherorten speichern, weil sie Zeit haben, sie abzurufen.

Daher müssen wir diese Art von Daten an temporären Orten speichern, die als Puffer bekannt sind, z. B. im RAM. Der Ringpuffer, auch als Ringpuffer bekannt, ist eine Warteschlange, die eine zusammenhängende Speichernutzung ermöglicht.

Der Ringpuffer arbeitet nach dem First-In-First-Out-Prinzip FIFO und kann entweder mit einem Array oder einer verketteten Liste implementiert werden. Fangen wir also an, mit Arrays zu lernen.

Verwenden Sie Array, um einen Ringpuffer in Java zu erstellen

Um den Ringpuffer mithilfe eines Arrays zu erstellen, müssen wir im Konstruktor ein leeres Array initialisieren, bei dem der Typ der dem Array hinzugefügten Elemente unbekannt ist.

Zwei Zeiger, head und tail, werden für die Einfüge- und Löschoperation verwendet, wobei head das erste Element und tail das letzte ist, wie im Bild gezeigt:

Ringpuffer in Java - Array Circular Buffer

Jetzt gibt es zwei Hauptoperationen, in und out bedeutet Einfügen und Löschen:

Demonstration des Einfügevorgangs

Das Einfügen ist ein einfacher Vorgang mit einigen wesentlichen Punkten:

  1. Am Anfang ist die Array-Größe 0, wobei die head-Position 0 und die tail-Position -1 ist.

  2. Dann verwenden wir die folgende Formel für den Index, an dem wir das Element einfügen:

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

  3. Die Größe des Arrays und der tail-Zeiger werden um 1 erhöht, wenn wir ein Element in das Array einfügen.

  4. Wenn die Größe des Arrays seiner Kapazität entspricht, können wir keine weiteren Elemente hinzufügen.

Demonstration des Löschvorgangs

  1. Wenn ein Element am head-Zeiger abgerufen wird, wird der head-Zeiger um 1 erhöht und die Puffergröße um 1 verringert.

  2. Die folgende Formel wird für den Index verwendet, an dem wir das Element löschen werden.

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

    Das Eingabearray für den Ringpuffer lautet nun beispielsweise:

    [7, 2, 5, 3, 4]

    Die Elemente werden der Reihe nach unter Verwendung des Ringpuffers gedruckt:

    7
2
5
3
4

Versuchen wir, die obige Methode für den Ringpuffer in Java zu implementieren:

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

Der obige Code enthält zwei Klassen, eine für die Methoden und die andere für die Hauptklasse zum Ausführen der Operationen.

Die erste Klasse umfasst die Methoden zum Einfügen, Löschen und Abrufen der Elemente; Der Code druckt die Elemente einzeln, indem er die Operation zum Einfügen und Löschen des Ringpuffers anwendet. siehe Ausgabe:

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

Verwenden Sie eine verknüpfte Liste, um einen Ringpuffer in Java zu erstellen

Um einen Ringpuffer mit einer verknüpften Liste in Java zu erstellen, müssen wir eine Hilfsklasse erstellen, mit der wir die generischen Knoten erstellen. Ähnlich wie beim Array werden wir head und tail für das Einfügen und Löschen beibehalten; Der Vorgang ist im Bild dargestellt:

Zirkularpuffer in Java - Ringpuffer für verknüpfte Listen

Demonstration des Einfügevorgangs

Die Schritte zum Einfügen zum Erstellen eines Ringpuffers mithilfe einer verknüpften Liste sind:

  1. Am Anfang ist die Größe 0 und head und tail sind null.
  2. Dann werden die Elemente dem Schwanz der verknüpften Liste hinzugefügt.
  3. Die Referenz des tail-Zeigers wird dann auf den head-Zeiger geändert.
  4. Wenn die Elemente der verknüpften Liste hinzugefügt werden, erhöht sich auch die Puffergröße.
  5. Wenn die Größe des Arrays seiner Kapazität entspricht, können wir keine weiteren Elemente hinzufügen.

Demonstration des Löschvorgangs

Die Schritte zum Löschen sind:

  1. Zuerst rufen wir das Element am head-Zeiger ab.

  2. Zweitens ändern wir die Referenz des head-Zeigers auf das nächste Element.

  3. Die Größe des Puffers wird um 1 verringert.

    Nun ist beispielsweise das Eingabe-Array für einen Ringpuffer, der eine verkettete Liste verwendet, wie folgt:

    [7, 2, 5, 3, 4]

    Die Elemente werden der Reihe nach unter Verwendung des Ringpuffers mit einer verknüpften Liste gedruckt:

    7
2
5
3
4

Versuchen wir, den Circular-Puffer mithilfe der verknüpften Liste im Java-Code zu implementieren:

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

Der obige Code erstellt eine generische Knoten-Klasse zum Ausführen von verknüpften Listenoperationen und erstellt Methoden zum Ausführen von Einfüge-, Lösch- und Abrufoperationen.

Der Code erstellt mithilfe der verknüpften Liste einen Ringpuffer und druckt die Elemente der Eingabeliste nacheinander, siehe die Ausgabe unten:

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

Verwandter Artikel - Java Buffer