Circular Buffer Queue
Problem
The first line is the capacity c of a queue. The next lines are commands: enqueue X (prints ok, or full if the queue already has c elements), dequeue (prints the oldest element, or empty) and print (prints the elements from oldest to newest separated by spaces, or empty). Build the queue on a fixed size array, where the end of the array connects to its start.
Constraints
- 1 <= c <= 10^5
- 1 <= commands <= 10^5
Examples
Input
2 enqueue 1 enqueue 2 enqueue 3 dequeue print
Output
ok ok full 1 2
Solutions
No elements move when we remove the oldest one: only the head index moves. The modulo operator makes the end of the array continue at the start, so each operation costs O(1) and memory is reused.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One answer per command.
* Approach: An array with wrap around.
* Time : O(1) per command
* Space : O(c)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: A circular buffer has a fixed size array. "head" is the index of the oldest element. "size" is the number of stored elements.
static class CircularBuffer {
private final long[] data;
private int head = 0;
private int size = 0;
CircularBuffer(int capacity) {
data = new long[capacity];
}
// Step 2: The new element goes to index (head + size) % capacity. The % makes the index wrap around to the start.
boolean enqueue(long value) {
if (size == data.length) {
return false;
}
data[(head + size) % data.length] = value;
size++;
return true;
}
// Step 3: Remove the oldest element. The head moves one step forward (with wrap around).
Long dequeue() {
if (size == 0) {
return null;
}
long value = data[head];
head = (head + 1) % data.length;
size--;
return value;
}
String show() {
if (size == 0) {
return "empty";
}
StringBuilder text = new StringBuilder();
for (int i = 0; i < size; i++) {
text.append(i == 0 ? "" : " ").append(data[(head + i) % data.length]);
}
return text.toString();
}
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
CircularBuffer buffer = new CircularBuffer(Integer.parseInt(lines[0]));
String[] output = new String[lines.length - 1];
for (int i = 1; i < lines.length; i++) {
String[] part = lines[i].split(" ");
// Step 4: Run the command. A full buffer or an empty buffer gives a text answer.
if (part[0].equals("enqueue")) {
output[i - 1] = buffer.enqueue(Long.parseLong(part[1])) ? "ok" : "full";
} else if (part[0].equals("dequeue")) {
Long value = buffer.dequeue();
output[i - 1] = value == null ? "empty" : String.valueOf(value);
} else {
output[i - 1] = buffer.show();
}
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- What does % capacity do to an index that goes past the end?