[medaa]

class CircularQueue:
    
    def __init__(self, capacity):
        if type(capacity) != int or capacity < 0:
            raise Expection("capacity")
        self.queue = []
        self.count = 0
        self.max = capacity
            
    def enqueue(self, item):
        if self.count == self.max:
            raise Expection("queue is full")
        self.queue.append(item)
        self.count += 1
        
    def dequeue(self):
        if self.count == 0:
            raise("empty!")      
        self.count -= 1
        return self.queue.pop(0)
         
    def peek(self):
        if self.count == 0:
            raise("empty!")
        return self.queue[0]
        
    def is_empty(self):
        return 0 == self.count 
        
    def is_full(self):
        return self.max == self.count
        
    def size(self):
        return self.count
        
    def capacity(self):
        return self.max
        
    def clear(self):
        self.queue = []
        self.count = 0
        
    def __str__(self):
        return " ".join([str(v) for v in self.queue])
        
# use this function to test your Circular Queue implementation    
def test():
  
    string_queue = CircularQueue(3)
    
    is_pass = (string_queue.size() == 0)
    assert is_pass == True, "fail the test"
    
    is_pass = (string_queue.capacity() == 3)
    assert is_pass == True, "fail the test" 
    
    is_pass = (string_queue.is_empty())
    assert is_pass == True, "fail the test"
    
    string_queue.enqueue("Hello")
    string_queue.enqueue("World")
    
    is_pass = (str(string_queue) == "Hello World")
    assert is_pass == True, "fail the test"
    
    is_pass = (string_queue.size() == 2)
    assert is_pass == True, "fail the test"
    
    is_pass = (string_queue.peek() == "Hello")
    assert is_pass == True, "fail the test"

    is_pass = (string_queue.capacity() == 3)
    assert is_pass == True, "fail the test"
    
    is_pass = (string_queue.peek() == "Hello" and string_queue.size() == 2)
    assert is_pass == True, "fail the test"
 
    string_queue.enqueue("python")
    
    is_pass = (string_queue.is_full())
    assert is_pass == True, "fail the test" 
    
    try:
        string_queue.enqueue("rules")
    except Exception as e:
        is_pass = True
    else:
        is_pass = False
    assert is_pass == True, "fail the test"
    
    string_queue.dequeue()
    is_pass = (string_queue.peek() == "World")
    assert is_pass == True, "fail the test" 

    string_queue.dequeue()
    is_pass = (string_queue.peek() == "python")
    assert is_pass == True, "fail the test"  

    string_queue.enqueue("apple") 
    string_queue.enqueue("google") 
    string_queue.dequeue()
    is_pass = (string_queue.peek() == "apple")
    assert is_pass == True, "fail the test"
    
    string_queue.clear()
    
    is_pass = (string_queue.capacity() == 3)
    assert is_pass == True, "fail the test" 
    
    is_pass = (string_queue.size() == 0)
    assert is_pass == True, "fail the test"
    
    try:
        string_queue.dequeue()
    except Exception as e:
        is_pass = True
    else:
        is_pass = False
    assert is_pass == True, "fail the test" 
        
    try:
        string_queue.peek()
    except Exception as e:
        is_pass = True
    else:
        is_pass = False
    assert is_pass == True, "fail the test"
    
    int_queue2 = CircularQueue(10)
    
    for i in range(0, 10):
        int_queue2.enqueue(i)      
    int_queue2.dequeue()
    int_queue2.dequeue()
    int_queue2.dequeue()
    int_queue2.dequeue()
    is_pass = (str(int_queue2) == "4 5 6 7 8 9")
    assert is_pass == True, "fail the test"

    for i in range(11, 13):
        int_queue2.enqueue(i)
    is_pass = (str(int_queue2) == "4 5 6 7 8 9 11 12")
    assert is_pass == True, "fail the test"

    for i in range(21, 23):
        int_queue2.enqueue(i)
    is_pass = (str(int_queue2) == "4 5 6 7 8 9 11 12 21 22")
    assert is_pass == True, "fail the test"

    
    int_queue = CircularQueue(1000)
    
    is_pass = (int_queue.is_empty())
    assert is_pass == True, "fail the test"
    
    is_pass = (int_queue.is_full())
    assert is_pass == False, "fail the test"
    
    for i in range(0, 1000):
        int_queue.enqueue(i)      
    correctOrder = True
    
    is_pass = (int_queue.is_empty())
    assert is_pass == False, "fail the test"
    
    is_pass = (int_queue.is_full())
    assert is_pass == True, "fail the test"
    
    for i in range(0, 200):
        if int_queue.dequeue() != i:
            correctOrder = False
            
    is_pass = correctOrder
    assert is_pass == True, "fail the test" 
    
    is_pass = (int_queue.size() == 800)
    assert is_pass == True, "fail the test" 
 
    is_pass = (int_queue.capacity() == 1000)
    assert is_pass == True, "fail the test"    

    is_pass = (int_queue.peek() == 200)
    assert is_pass == True, "fail the test"
    
    for i in range(0, 200):
        int_queue.enqueue(i)      
    
    is_pass = (int_queue.is_empty())
    assert is_pass == False, "fail the test"
    
    is_pass = (int_queue.is_full())
    assert is_pass == True, "fail the test"
    
    is_pass = (int_queue.peek() == 200)
    assert is_pass == True, "fail the test"
    
    if is_pass == True:
        print ("=========== Congratulations! Your have finished exercise 1! ============")

if __name__ == '__main__':
    test()
 

I have completed this program and it works fine but need create a private attribute (internal data object) to record how many items are currently stored in the queue. Thus when the start and end pointer both point to the same element I can check this counter to know whether the queue is empty or full.

Can I get some help?

[lisperati]

Python doesnt have a truely private class member, what is has is to prefix your property or method with a double underscore. This will tell programmers that this method or property should be kept as a private property or method and should not be accessed directly but there is no mechanism to stop them from doing so if they decide to.

Regards
Lisperati

[medaa]

Yes, I know, I guess I should say

I need help recording how many items are currently stored in the queue. So when the start and end pointer both point to the same element I can check this counter to know whether the queue is empty or full.

[Mekire]

I'm not sure quite what you are asking for here. You are already keeping track of the number of items in your queue as I'm sure you are aware with your size.count variable (which is also, strictly speaking, pointless as you can always use len() but I think it is probably one of your requirements.)

If you are required to make it "private" then add a single underscore in front of it. A single underscore lets other python programmers know that you don't intend for this variable to be directly accessed. If you want to make it slightly more private then use the double underscore. Double underscores again don't technically make it private either, but it does something called name-mangling which means that a programmer has to very intentionally try to access that variable.

With a single underscore:

>>> C = CircularQueue(3)
>>> C._count
0

Obviously here we can still access the value if we want to. We just shouldn't.
One more thing to note is a single underscore has another side effect. Any variables using single underscore names will not be imported if you do a from module import * in another module.

With a double underscore:

>>> C = CircularQueue(3)
>>> C.__count
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
AttributeError: CircularQueue instance has no attribute '__count'
>>> C._CircularQueue__count
0

In order to access the data we must use the name _<classname>__<valuename>. And we really shouldn't.

What I suspect you are trying to do as your next step here however, privacy aside, is create a true circular queue in which trying to add past capacity doesn't raise an exception but instead overwrites the oldest value. If this is the case you will have to change your enqueue function to something like this:

def enqueue(self, item):
        self.queue.append(item)
        if self._count == self.max:
            self.queue.pop(0)
        else:
            self._count += 1

Here we always add a new item with append, but if the queue is full we also remove the first member in the list.

Now one last thing I would like to note. All of your raise statements are written incorrectly. Ironically this doesn't affect the test that your instructor gave you because the error with the statements actually raises an exception. In your init and queue you actually misspelled Exception. Correct that and it is fine, however they should really raise a specific type of Exception (in the case of init TypeError would probably be appropriate). In your dequeue and peek however you forgot to put an exception type altogether and just put a string in parenthesis after the raise.

Anyway, hopefully some of this helped. If not please clarify your question and what your next goal/task is.
-Mek

[medaa]

Hey Mek, so I realized I need to do this:

When dequeue()/clear(), JUST move the start/end
pointer(index), DO NOT physically delete any
item from your memory (do not use pop()!).

And Im not getting it, its frustrating

[baavgai]

So, basically, write a queue implementation as if you were a C programmer without any benefits of the Python language.

You'd want something like:

class CircularQueue:
	def __init__(self, capacity):
		self.storage = [ None for i in range(capacity) ]
		# storage is now allocated with capacity elements
		# we will use only one list function []
		self.capacity = capacity # so we don't have to call len, let's be silly about this
		self.top = 0 # this is where the elements of your queue start
		self.size = 0 # this is how many you currently have
	
		# as you enqueue and dequeue, top will move around
		# and elements will wrap around the bottom and into the top
		# another way to do this is have self.bottom instead of size

I expect this is what your instructor is after. Read up on the queue ADT and look more at array implementations than good, sane, python code.

[Mekire]

Your instructor seems to be trying to convince you that you can control the amount of memory a list will use in python as long as you don't alter its length. This is bull. It is not a list of ints or a list of floats or a list of chars; it is a list of whatever the user decides to put in it. The amount of memory can't be controlled like it can in C.

But whatever...
If you initialize the queue as Baavgai suggested and keep track of an insertion index and a removal index, and increment them using a modulus of the capacity you can make something that passes your instructors test with out using pop or ever changing the size of the queue. It is just bad python code though.

I past his precious test using these (other changes to the code are necessary as well though):

def enqueue(self, item):
    if self._count == self._cap:
        raise IndexError("queue is full")
    self.queue[self._insert_ind] = item
    self._insert_ind = (self._insert_ind+1)%self._cap
    self._count += 1

def dequeue(self):
    if not self._count:
        raise IndexError("Queue is empty.")
    give = self.queue[self._remove_ind]
    self._remove_ind = (self._remove_ind+1)%self._cap
    self._count -= 1
    return give

Bleh. I feel dirty.
-Mek

[medaa]

I talked to a grad student who said the same thing, apparently this will never be asked for in a real work field, I personally feel its a little beyond a first yr course.

[baavgai]

The fact is, python already does a number of the things that a first year programmer would be asked to write. So does almost any other language, really. The "write common ADT X" exercise is always redundant.

In C and C++, dynamic allocation is a big deal. In C, linked lists are very important and teach a number of concepts. In Python, these things are like shoes for fish.

So why constantly reinvent the wheel, or even ignore the available car? Because there are fundamental elements to programming and understanding them, even if someone already wrote them for you, is important.

The game with your queue is to impose absurd limitations and work from there. You will learn something from doing this, even if it's practicality isn't immediately apparent.

This post has been edited by baavgai: 23 February 2013 - 06:27 AM