# Implementing a queue using a circular buffer

I'm working on implementing a queue using a circular buffer problem. Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated.

class QueueOnCirciularBuffer:
def __init__(self, max_size):
self.buffer = [0]*max_size
self.index = 0 # element to write
self.size = 0
self.max_size = max_size
def push_element(self, value):
if self.size == self.max_size:
raise Exception('queue full')
self.buffer[self.index] = value
self.index += 1
self.size += 1
self.index = self.index % self.max_size
def pop_element(self):
if self.size > 0:
value = self.buffer[(self.index - self.size+self.max_size)%self.max_size]
self.size -= 1
return value
else:
raise Exception('empty queue')
def peak_element(self):
if self.size > 0:
return self.buffer[(self.index-1+self.max_size)%self.max_size]
else:
raise Exception('empty queue')
if __name__ == "__main__":
q = QueueOnCirciularBuffer(16)
q.push_element(1)
q.push_element(2)
print q.peak_element() # output 2
q.pop_element()
print q.peak_element() # output 2

q2 = QueueOnCirciularBuffer(3)
for i in range(3):
print i
q2.push_element(i)
for i in range(10):
print q2.pop_element()
q2.push_element(i)

• It is spelled "peek" (look quickly or furtively), not "peak" (the pointed top of a mountain). Commented Dec 15, 2016 at 14:37

QueueOnCirciularBuffer: you misspelled Circular

Wikipedia gives more canonic names for the data structure. Why not choose, say, CircularBuffer?

Instead of having a single index self.index, why not take two: self.head_index is the index in the underlying storage array holding the head element of the buffer; self.tail_index points into the array location at which next element is inserted. If not efficiency, this adds to maintainability in my opinion.

value = self.buffer[(self.index - self.size+self.max_size)%self.max_size]
self.buffer[(self.index-1+self.max_size)%self.max_size]


Adding self.max_size has not effect since you take the modulo of it.

PEP 8 complains about some aspects of your code layout. Consider using a Python IDE (I use PyCharm); it gives you instant feedback if your code does not adhere to rules in PEP 8.

Its funny that your peak_element returns the tail element of the queue; why not rename it to, say, peak_tail. (And possibly provide peak_head.)

Summa summarum

All in all, I had this in mind:

class CircularBuffer:
def __init__(self, capacity):
self.buffer = [0] * capacity
self.size = 0
self.capacity = capacity
self.tail_index = 0

def push_element(self, value):
if self.size == self.capacity:
raise Exception('The circular buffer is full.')
self.buffer[self.tail_index] = value
self.tail_index = (self.tail_index + 1) % self.capacity
self.size += 1

def pop_element(self):
if self.size == 0:
raise Exception('Popping from an empty circular buffer.')
self.size -= 1
return ret


• @LinMa No, no plug-ins whatsoever. Once again, if you have an expression that does not conform to PEP 8 (try, for example, i+=1), PyCharm will underline that expression with a wavy line. Move the cursor to that wavy line and PyCharm will tell you what's wrong. Commented Dec 17, 2016 at 6:24