CODEWITHSUNDEEP
pythonerror-handlingqueuecircular-bufferindex-error
Charlotte Lee
Charlotte Lee

Reputation: 11

implementing a circular queue in python - a level standard

i am trying to implement a circular queue in python and my current program keeps giving me error, and I would like to know the problem and solve it.

my current program is :

# circular queue

class circularQueue:
   def __init__(self, maxsize):
        self.front = 0
        self.rear = -1
        self.queue = []
        self.size = 0 # elements in the queue
        self.maxsize = maxsize #size of the array(queue)

   def isEmpty(self):
       if self.size == 0:
            return True
       else:
           return False

   def isFull(self):
       if self.size == self.maxsize:
          return True
       else:
          return False

   def enQueue(self, newItem):
       if self.size == self.maxsize:
           print('Queue Full')
       else:
           self.rear = (self.rear + 1) % self.maxsize # mod = remainder
           self.queue[self.rear] = newItem
           self.size += self.size

   def deQueue(self):
       if self.size == 0:
           print('Queue Empty')
           item = null
       else:
           item = self.queue[self.front]
           self.front = (self.front + 1) % self.maxsize
           self.size = self.size - 1

       return item

and if i try to operate 

q = circularQueue(6)
q.enQueue('k')

it says 

self.queue[self.rear] = newItem
IndexError: list assignment index out of range

Please help me ......

Upvotes: 0

Views: 1739

Answers (2)

abarnert
abarnert

Reputation: 366003

You start off with queue=[], size=0, rear=-1, and maxsize=6. So, what happens in enQueue the first time you call it?

if self.size == self.maxsize:

Nope, 0 != 6.

self.rear = (self.rear + 1) % self.maxsize # mod = remainder

OK, so self.rear = 0

self.queue[self.rear] = newItem

Now you're trying to assign to self.queue[0]. But you created an empty queue; you can't assign to the first element of it.

The simplest fix here is to start off with self.queue = [None for _ in range(maxsize)]. Then the queue always has maxsize elements.

Or, if None could be a reasonable value to store in the queue, it'll probably be easier to debug if you create a special _sentinel = object() in your initializer and store that _sentinel in the empty slots. (You seem to have some special null value in your code that you return on deQueue when empty. If that's not an error, it may be even more helpful to have a _sentinel that's neither null nor anything that can be inserted—basically, if your unit tests ever get _sentinel back, you know you counted the circle wrong somewhere.)

You can get fancier and grow until maxsize and only then start going around the circle, but you only need that optimization if you're going to be creating lots of queues with large maxsizes but most of them never get near the maxsize. So just keep it simple.

Finally:

self.size += self.size

What? Doubling the maxsize might make sense for an unbounded queue, but this is a bounded queue. And doubling the in-use size never makes sense. You probably just wanted += 1 here.

Upvotes: 0

Prune
Prune

Reputation: 77880

You're trying to fill in a list element that doesn't exist. Instead, when you're extending the existing list, you have to use append:

self.queue.append(newItem)

Also, I don't think that you want to double self.size each time you do this -- look at that next line:

self.size += self.size

Try

self.size += 1

Upvotes: 0

Related Questions