pythonlistclasscircular-queue

Python initialize a list in a class


I am trying to solve a leetcode question using list: Design Circular Queue.

But it throws an error:

IndexError: list assignment index out of range
self.queue[self.tail] = value 

My code:

class MyCircularQueue:

def __init__(self, k: int):
    self.size = k
    self.queue = []
    self.head = -1
    self.tail = -1
    

def enQueue(self, value: int) -> bool:
    if self.tail + 1 == self.head: #queue full
        return False

    elif self.tail + 1 == self.size:
        self.tail = 0
        self.queue[self.tail] = value
        return True
    
    else:
        self.tail += 1
        self.queue[self.tail] = value
        return True
    

def deQueue(self) -> bool:
    if len(self.queue) == 0: #queue empty
        return False
    
    elif self.tail + 1 == self.size:
        self.queue.pop(self.head)
        self.head = -1
        return True
    
    else:
        self.queue.pop(self.head)
        self.head += 1
        return True
    

def Front(self) -> int:
    if self.head == -1:
        return False
    
    return self.queue[self.head]
    

def Rear(self) -> int:
    if self.tail == -1:
        return False
    
    return self.queue[self.tail]
    

def isEmpty(self) -> bool:
    if len(self.queue) == 0:
        return True
    
    return False
    

def isFull(self) -> bool:
    if len(self.queue) == self.size:
        return True
    
    return False

Other similar posts say maybe the list is not initialized but I can't figure out what I did wrong here.

Question link: https://leetcode.com/problems/design-circular-queue/


Edit:

As pointed out below, append will be an organic way to do it in Python. However, I need index to implement circular queue so I took a different approach:

self.tail = (self.tail + 1) % self.size #example circular increment
  1. initialize list with None other than an empty list
  2. deQueue: replacing item with None other than pop

Updated code:

class MyCircularQueue:

def __init__(self, k: int):
    self.size = k
    self.queue = [None] * k #replace queue = [] -> add queue[idx] will throw a error
    self.head = -1
    self.tail = -1
    

def enQueue(self, value: int) -> bool:
    if self.isFull() == True: #queue full
        return False
    
    elif self.tail == -1: #add first item
        self.tail += 1
        self.head += 1
        self.queue[self.tail] = value
            
    else: 
        self.tail = (self.tail + 1) % self.size
        self.queue[self.tail] = value
 
    return True
    

def deQueue(self) -> bool:
    if self.isEmpty() == True: #queue empty
        return False
    
    elif self.head == self.tail: #at last item
        self.queue[self.head] = None
        self.head = -1
        self.tail = -1
    
    else:
        self.queue[self.head] = None #replace item with None other than pop, which will remove None from the list
        self.head = (self.head + 1) % self.size #not self.head += 1

    return True
    

def Front(self) -> int:
    if self.head == -1:
        return -1
    
    return self.queue[self.head]
    

def Rear(self) -> int:
    if self.tail == -1:
        return -1
    print(self.tail)
    return self.queue[self.tail]
    

def isEmpty(self) -> bool:
    if self.head == -1:
        return True
    
    return False
    

def isFull(self) -> bool:
    if (self.tail + 1) % self.size == self.head:
        return True
    
    return False

Reference: Circular Queue Structure Explanation


Solution

  • queue[index] refers to the indexth item in the list queue.

    If there are no items in the list, index 0 does not exist, so you can't access queue[0].

    The exception "list assignment index out of range" raises when index >= len(list). You initialize self.tail to be 0, and the length of the list is also 0.

    The Pythonic way to add an item to the last place of a list is to use list.append:

    self.queue.append(value)