up vote 1 down vote favorite
2

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)
share|improve this question
1  
It is spelled "peek" (look quickly or furtively), not "peak" (the pointed top of a mountain). – Jaime Dec 15 '16 at 14:37
up vote 4 down vote accepted

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.

share|improve this answer
1  
@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 Dec 16 '16 at 8:35
1  
@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 Dec 17 '16 at 6:24
1  
@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 Dec 17 '16 at 7:07
1  
Let me try, thanks for all the hints. – Lin Ma Dec 17 '16 at 7:09
1  
@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 Dec 17 '16 at 7:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.