1class CircularQueue:
2 def __init__(self, k):
3 self.SCALING_FACTOR = 2
4 self.queue = [0 for _ in range(k)]
5 self.k = k
6 self.head = self.tail = self.count = 0
7
8 def enqueue(self, val):
9 if self.count == self.k:
10 self.queue = self.queue[self.head:] + self.queue[:self.head]
11 self.queue += [0] * (self.k * self.SCALING_FACTOR) - self.k
12 self.k *= self.SCALING_FACTOR
13 self.head, self.tail = 0, self.count
14
15 self.count += 1
16 self.queue[self.tail % self.k] = val
17 self.tail = (self.tail + 1) % self.k
18
19 def dequeue(self):
20 res = self.queue[self.head]
21 self.head = (self.head + 1) % self.k
22 self.count -= 1
23 return res
24
25 def size(self):
26 return self.count