Implementing a queue using a circular buffer

Question

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)

• Jaime: It is spelled "peek" (look quickly or furtively), not "peak" (the pointed top of a mountain).

Answer 1

Advice 1

QueueOnCirciularBuffer: you misspelled Circular

Advice 2

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

Advice 3

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.

Advice 4

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.

Advice 5

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.

Advice 6

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.head_index = 0
 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.')
 ret = self.buffer[self.head_index]
 self.head_index = (self.head_index + 1) % self.capacity
 self.size -= 1
 return ret
 def peek_head(self):
 if self.size == 0:
 raise Exception('Peeking into an empty circular buffer.')
 return self.buffer[self.head_index]

Hope that helps.

• coderodde: @LinMa I work on Mac, so hard to tell. For me it works by wave-underlining the expression that does not conform to PEP 8. Taking the mouse to that line gives me the feedback in form of a pop-up.
• coderodde: @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.
• coderodde: @LinMa I use the Community edition, which is free. Note, however, that I did not have to "enable" it or something; it worked out of the box.
• coderodde: @LinMa Try this link: dropbox.com/s/1anucvl8b73cd31/PyCharm.png?dl=0 If it ask you to sign in, press something like "Continue without signing in."
• coderodde: @LinMa Good. Now just don't stop writing that funky Python code! :)