Design Circular Queue — Ring Buffer Implementation

Sanjeev SharmaSanjeev Sharma
2 min read

Advertisement

Problem

Design a circular queue with operations:

  • enQueue(value) — insert at rear, return false if full
  • deQueue() — delete from front, return false if empty
  • Front() / Rear() — peek front/rear, return -1 if empty
  • isEmpty() / isFull()

Solutions

Python

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [0] * k
        self.head = self.tail = -1
        self.size = 0
        self.k = k

    def enQueue(self, value: int) -> bool:
        if self.isFull(): return False
        if self.isEmpty():
            self.head = self.tail = 0
        else:
            self.tail = (self.tail + 1) % self.k
        self.q[self.tail] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty(): return False
        self.size -= 1
        if self.size == 0:
            self.head = self.tail = -1
        else:
            self.head = (self.head + 1) % self.k
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.q[self.head]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.q[self.tail]

    def isEmpty(self) -> bool: return self.size == 0
    def isFull(self) -> bool: return self.size == self.k

JavaScript

class MyCircularQueue {
    constructor(k) { this.q=new Array(k); this.h=this.t=-1; this.sz=0; this.k=k; }
    enQueue(v) {
        if(this.isFull()) return false;
        if(this.isEmpty()) this.h=this.t=0; else this.t=(this.t+1)%this.k;
        this.q[this.t]=v; this.sz++; return true;
    }
    deQueue() {
        if(this.isEmpty()) return false; this.sz--;
        if(this.sz===0) this.h=this.t=-1; else this.h=(this.h+1)%this.k; return true;
    }
    Front() { return this.isEmpty()?-1:this.q[this.h]; }
    Rear() { return this.isEmpty()?-1:this.q[this.t]; }
    isEmpty() { return this.sz===0; }
    isFull() { return this.sz===this.k; }
}

Java

class MyCircularQueue {
    int[] q; int h=-1,t=-1,sz=0,k;
    public MyCircularQueue(int k) { this.k=k; q=new int[k]; }
    public boolean enQueue(int v) {
        if(isFull()) return false;
        if(isEmpty()) h=t=0; else t=(t+1)%k;
        q[t]=v; sz++; return true;
    }
    public boolean deQueue() {
        if(isEmpty()) return false; sz--;
        if(sz==0) h=t=-1; else h=(h+1)%k; return true;
    }
    public int Front(){ return isEmpty()?-1:q[h]; }
    public int Rear(){ return isEmpty()?-1:q[t]; }
    public boolean isEmpty(){ return sz==0; }
    public boolean isFull(){ return sz==k; }
}

C++

class MyCircularQueue {
    vector<int> q; int h=-1,t=-1,sz=0,k;
public:
    MyCircularQueue(int k):q(k),k(k){}
    bool enQueue(int v){if(isFull())return false;if(isEmpty())h=t=0;else t=(t+1)%k;q[t]=v;sz++;return true;}
    bool deQueue(){if(isEmpty())return false;sz--;if(sz==0)h=t=-1;else h=(h+1)%k;return true;}
    int Front(){return isEmpty()?-1:q[h];}
    int Rear(){return isEmpty()?-1:q[t];}
    bool isEmpty(){return sz==0;}
    bool isFull(){return sz==k;}
};

C

int cq[1001]; int H=-1,T=-1,SZ=0,K;
void init(int k){K=k;}
int enQ(int v){if(SZ==K)return 0;if(SZ==0)H=T=0;else T=(T+1)%K;cq[T]=v;SZ++;return 1;}
int deQ(){if(SZ==0)return 0;SZ--;if(SZ==0){H=T=-1;}else H=(H+1)%K;return 1;}
int front(){return SZ==0?-1:cq[H];}
int rear(){return SZ==0?-1:cq[T];}

Complexity

OperationTimeSpace
All opsO(1)O(k)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro