Design Circular Queue — Array with Head and Tail Pointers
Advertisement
Problem 271 · Design Circular Queue
Difficulty: Medium · Pattern: Circular Array Design
Solutions
# Python
class MyCircularQueue:
def __init__(self, k):
self.data = [0]*k; self.head = 0; self.size = 0; self.cap = k
def enQueue(self, value):
if self.isFull(): return False
self.data[(self.head + self.size) % self.cap] = value
self.size += 1; return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head+1) % self.cap; self.size -= 1; return True
def Front(self): return -1 if self.isEmpty() else self.data[self.head]
def Rear(self): return -1 if self.isEmpty() else self.data[(self.head+self.size-1)%self.cap]
def isEmpty(self): return self.size == 0
def isFull(self): return self.size == self.cap
// Java
class MyCircularQueue {
int[] data; int head=0, size=0, cap;
public MyCircularQueue(int k) { cap=k; data=new int[k]; }
public boolean enQueue(int v) { if(isFull()) return false; data[(head+size)%cap]=v; size++; return true; }
public boolean deQueue() { if(isEmpty()) return false; head=(head+1)%cap; size--; return true; }
public int Front() { return isEmpty()?-1:data[head]; }
public int Rear() { return isEmpty()?-1:data[(head+size-1)%cap]; }
public boolean isEmpty() { return size==0; }
public boolean isFull() { return size==cap; }
}
Complexity
- All operations: O(1)
- Space: O(k)
Advertisement