Ring Buffer also is known as Circular Queue is a type of linear data structure. It following the FIFO rule of Queue, but it doesn't have an ending position. The last inserted item can overwrite the existing items, the front and rear are connected together like a ring and often used as Buffer in the software industry. That's why we call it Ring Buffer.
Question
4.3.41 Ring buffer. A ring buffer (or circular queue) is a FIFO collection that stores a sequence of items, up to a prespecified limit. If you insert an item into a ring buffer that is full, the new item replaces the least recently inserted item. Ring buffers are useful for transferring data between asynchronous processes and for storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. Develop an API for a ring buffer and an implementation that uses a fixed-length array.
Computer Science An Interdisciplinary Approach (2016, page 260).
Implementing Steps
In this solution, we are going to use a fixed-length array as the element's container. Using the Enqueue and Dequeue methods to manage the elements. The differences between this implementation and a normal queue are the size of the elements are not incrementable and elements can be overwritten.
Here goes the key points:
- Fixed-length array.
- Using two variable to track the read-position and write-position of the queue. Initializing the value of two positions to -1.
- if a position beyond the end of the array's length, reset the position to zero.
- if the write-positon cached up with the front position, increase the read-position by 1.
- if the read-position cached up with the write-position, reset positions to -1.
- Be aware of the starting value of the two positions.
Solution
/******************************************************************************
* Compilation: javac CircularQueue.java
* Execution: java CircularQueue
*
* Using a fixed-length array to implement a FIFO queue.
*
* % java CircularQueue
* Print out the queue.
* [a, b, c, d, e, f]
*
* Add a new element to the full circle queue.
* [g, b, c, d, e, f]
*
* Read elements from the cilcle queue.
* b
* c
* d
* e
* f
*
* Add a new element X to the circle queue.
* [g, X, null, null, null, null]
* Continue reading elements from the circle queue.
* g
* [null, X, null, null, null, null]
* X
* [null, null, null, null, null, null]
*
* Add new elements to the circle queue.
* [Y, Z, null, null, null, null]
* Read one more element from the circle queue.
* Y
* [null, Z, null, null, null, null]
*
******************************************************************************/
import java.util.Arrays;
class CircularQueue<Item> {
private int capacity;
public int readPos = -1;
public int writePos = -1;
private Item[] elements;
public static void main(String[] args) {
CircularQueue<String> circle = new CircularQueue<String>(6);
circle.enqueue("a");
circle.enqueue("b");
circle.enqueue("c");
circle.enqueue("d");
circle.enqueue("e");
circle.enqueue("f");
System.out.println("Print out the queue.");
System.out.println(circle.toString());
System.out.println("\nAdd a new element to the full circle queue.");
circle.enqueue("g");
System.out.println(circle.toString());
System.out.println("\nRead elements from the cilcle queue.");
System.out.println(circle.dequeue());
System.out.println(circle.dequeue());
System.out.println(circle.dequeue());
System.out.println(circle.dequeue());
System.out.println(circle.dequeue());
System.out.println("\nAdd a new element X to the circle queue.");
circle.enqueue("X");
System.out.println(circle.toString());
System.out.println("Continue reading elements from the circle queue.");
System.out.println(circle.dequeue());
System.out.println(circle.toString());
System.out.println(circle.dequeue());
System.out.println(circle.toString());
System.out.println("\nAdd new elements to the circle queue.");
circle.enqueue("Y");
circle.enqueue("Z");
System.out.println(circle.toString());
System.out.println("Read one more element from the circle queue.");
System.out.println(circle.dequeue());
System.out.println(circle.toString());
}
public CircularQueue(int capacity) {
this.capacity = capacity;
elements = (Item[])new Object[capacity];
}
public void enqueue(Item item) {
incrementWritePos();
elements[writePos] = item;
}
public Item dequeue() {
incrementReadPos();
Item element = elements[readPos];
elements[readPos] = null;
// Rest the reading and writing postions if the circle is empty.
if (readPos == writePos) {
readPos = -1;
writePos = -1;
}
return element;
}
public void incrementWritePos() {
writePos++;
// Write-postion reached the bottom of the array.
if (writePos == capacity) {
writePos = 0;
if (readPos == -1) {
readPos = 0;
}
return;
}
if (writePos == readPos) {
incrementReadPos();
}
}
public void incrementReadPos() {
readPos++;
// Read-postion reached the bottom of the array.
if (readPos == capacity) {
readPos = 0;
}
}
public String toString() {
return Arrays.toString(elements);
}
}Output
-> javac CircularQueue.java
Note: CircularQueue.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
-> java CircularQueue
Print out the queue.
[a, b, c, d, e, f]
Add a new element to the full circle queue.
[g, b, c, d, e, f]
Read elements from the cilcle queue.
b
c
d
e
f
Add a new element X to the circle queue.
[g, X, null, null, null, null]
Continue reading elements from the circle queue.
g
[null, X, null, null, null, null]
X
[null, null, null, null, null, null]
Add new elements to the circle queue.
[Y, Z, null, null, null, null]
Read one more element from the circle queue.
Y
[null, Z, null, null, null, null]The time complexity of enqueue and dequeue in this implementation are the same Θ(1).