Design Circular Queue — Ring Buffer Implementation
Advertisement
Problem
Design a circular queue with operations:
enQueue(value)— insert at rear, return false if fulldeQueue()— delete from front, return false if emptyFront()/Rear()— peek front/rear, return -1 if emptyisEmpty()/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
| Operation | Time | Space |
|---|---|---|
| All ops | O(1) | O(k) |
Advertisement