SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Circular Queue (Ring Buffer) Visualizer

An array of k slots, a head index for the front, and a count. Enqueue writes at (head + count) % k; dequeue reads at head and moves head forward. The % wraps both around the end.

Start the Circular Queue (Ring Buffer) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(1)
Worst timeO(1)
Extra spaceO(k)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. 4 empty slots. head = 0, count = 0. tail, the next free slot, is (head + count) % 4.
  2. enQueue(1) writes slot (0 + 0) % 4 = 0.
  3. enQueue(2) writes slot (0 + 1) % 4 = 1.
  4. enQueue(3) writes slot (0 + 2) % 4 = 2.
  5. deQueue() takes 1 from slot 0.
  6. head moves to 1. count = 2.
  7. deQueue() takes 2 from slot 1.
  8. head moves to 2. count = 1.
  9. enQueue(4) writes slot (2 + 1) % 4 = 3.
  10. enQueue(5) writes slot (2 + 2) % 4 = 0.
  11. enQueue(6) writes slot (2 + 3) % 4 = 1.
  12. enQueue(7): the queue is full (count = 4). Rejected.
  13. deQueue() takes 3 from slot 2.
  14. head moves to 3. count = 3.
  15. enQueue(8) writes slot (3 + 3) % 4 = 2.
  16. Done. No value was ever shifted; only head and count changed.

Try it with your own input →

Circular queue (ring buffer) in Java, Python, C++, C and JavaScript

class MyCircularQueue {
  int[] q; int head = 0, count = 0;
  MyCircularQueue(int k) { q = new int[k]; }
  boolean enQueue(int x) {
    if (count == q.length) return false;
    q[(head + count) % q.length] = x; count++; return true;
  }
  boolean deQueue() {
    if (count == 0) return false;
    head = (head + 1) % q.length; count--; return true;
  }
}
class MyCircularQueue:
    def __init__(self, k):
        self.q = [0] * k
        self.head = self.count = 0
    def en_queue(self, x):
        if self.count == len(self.q):
            return False
        self.q[(self.head + self.count) % len(self.q)] = x
        self.count += 1
        return True
    def de_queue(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % len(self.q)
        self.count -= 1
        return True
class MyCircularQueue {
  vector<int> q; int head = 0, count = 0;
public:
  MyCircularQueue(int k) : q(k) {}
  bool enQueue(int x) {
    if (count == (int)q.size()) return false;
    q[(head + count) % q.size()] = x; count++; return true;
  }
  bool deQueue() {
    if (count == 0) return false;
    head = (head + 1) % q.size(); count--; return true;
  }
};
#include <stdlib.h>

typedef struct {
  int *q, size, head, count;
} MyCircularQueue;

MyCircularQueue* create(int k) {
  MyCircularQueue* c = malloc(sizeof *c);
  c->q = malloc(k * sizeof(int)); c->size = k; c->head = c->count = 0;
  return c;
}
int enQueue(MyCircularQueue* c, int x) {
  if (c->count == c->size) return 0;
  c->q[(c->head + c->count) % c->size] = x; c->count++; return 1;
}
int deQueue(MyCircularQueue* c) {
  if (c->count == 0) return 0;
  c->head = (c->head + 1) % c->size; c->count--; return 1;
}
class MyCircularQueue {
  head = 0; count = 0;
  constructor(k) { this.q = new Array(k); }
  enQueue(x) {
    if (this.count === this.q.length) return false;
    this.q[(this.head + this.count) % this.q.length] = x; this.count++; return true;
  }
  deQueue() {
    if (this.count === 0) return false;
    this.head = (this.head + 1) % this.q.length; this.count--; return true;
  }
}

In an interview

LeetCode 622, Design Circular Queue: a fixed-size queue that reuses its slots.

Keeping a count (or one empty slot) is what tells "full" apart from "empty", since head and tail meet in both cases.

More lists, stacks & queues